Отбой. Ложная тревога. Это мы с учениками не в ту сторону изменили в последней строке программы число нечетных компонентов, глядя на простую и ясную строчку. Прошу прощения. Пусть код остается в качестве примера. Он рабочий. Нужно только внимательно на последнюю строку смотреть.
Здравствуйте. Есть страшные на первый взгляд 27-е задачи вида: набрать из пар чисел минимальную/максимальную сумму так, чтобы ее четность совпадала/отличалась с четностью большинства компонентов искомой компонентов суммы. И для них есть соблазнительно простое решение:
Просматривая входной файл, накопить минимальную/максимальную сумму и запомнить попутно одну пару с нечетной минимальной разностью между элементами и подсчитать количество четных и нечетных ее компонентов. Понятно, что если вычисленная сумма окажется не той четности, то ее четность изменится при добавлении/вычитани запомненной нечетной разности в паре. И это будут минимально необходимые изменения искомой суммы.
Этот метод отлично вычисляет правильный ответ когда количество четных и нечетных компонент отличается на два и более. Однако, он не учитывает, что при меньшем отличии разность количества четных и нечетных изменится так, что ответ больше не будет соответствовать условию задачи и потребуется изменить выбор компонентов в других парах. Похоже, что именно такое неполное решение служит в для вычисления ответов к задачам этого типа в генераторе вариантов.
Например. (№ 3699) Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма выбранных чисел была максимальной при условии, что чётность этой суммы совпадает с чётностью большинства выбранных чисел. Определите максимальную сумму, которую можно получить при таком условии. Гарантируется, что удовлетворяющий условиям выбор возможен.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
Пример входного файла:
5
13 8
5 11
6 9
7 2
9 14
Для указанных данных надо выбрать числа 13, 11, 6, 7 и 14. Большинство из них нечётны, их сумма 51 тоже нечётна.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Спрятать ответ
117046 411037387
--------------------------------------------------------------------------
Второй ответ, для большого файла B правильный, а первый, для коротенького файла A -- неверный.
Вот входные данные:
19
1649 98
637 3009
1947 240
4341 1499
7042 8462
7796 8932
9651 3703
6372 232
6825 9205
622 6200
9244 5155
3388 4601
4123 8192
121 3084
6669 111
8008 1652
5246 3732
3457 133
9990 7604
Вот мой код на Питоне:
#открываем файл на чтение
f = open('27-48a.txt', 'r')
#читаем число пар
num = int(f.readline())
print(num)
#так мы читаем очередную пару с упорядочиванием по возрастанию
def get():
return sorted(
( int(i) for i in f.readline().split() )
)
#обнуляем сумму максимальных
#количество нечетных в этой сумме
sum_a = 0
count_odd = 0
#максимизизум начальную минимальную разность в парах,
#которую нам, скорее всего, придется прибавлять к сумме
#для приведения ее в соответствие с заданием
min_delta = (10**10,0,0)
#сумму мы меняем ради изменения ее четности
#поэтому прибавлять к сумме четные дельты бессмысленно
#будем сохранять три меньшие нечетные дельты
#в начале кортежа дельта, потом два числа из пары
old_min_delta = (10**10,0,0)
very_old_min_delta = (10**10,0,0)
#рассмотрим оставшиеся пары
for i in range(num):
#получаем очередную пару
a,b = get()
#накапливаем сумму максимальных
sum_a += b
#считаем нечетные
count_odd += b % 2
delta = (b - a, a,b)
if delta[0] % 2 == 1 and delta[0] < min_delta[0]:
very_old_min_delta = old_min_delta
old_min_delta = min_delta
min_delta = delta
#печатаем для отладки,
#понятно, что (i - count_odd + 1) это число четных
print(a, b, '\t', sum_a, count_odd, i - count_odd + 1, b-a)
print('-----------------')
# сумма нечетных кол-во четных разность1 разность2 разность3
print(sum_a, count_odd, num - count_odd, min_delta, old_min_delta, very_old_min_delta)
#смотрим на строчку выше и ручками добавляем дельты к сумме,
#не забывая правильно уменьшать кол-во четных/нечетных
print(sum_a - 1213 - 1151, count_odd + 1 + 1, num - count_odd - 1 - 1)
#это проще и быстрее, чем отлаживать и тестировать на ЕГЭ код для этого последнего шага
#еще проще и короче вместо трех минимальных хранить в списке все нечетные разности
#и печатать их в конце после сортировки, но это не так эффективно
Вот вывод правильной программы с ответом в конце и числом нечетных и четных компонентов:
19
98 1649 1649 1 0 1551
637 3009 4658 2 0 2372
240 1947 6605 3 0 1707
1499 4341 10946 4 0 2842
7042 8462 19408 4 1 1420
7796 8932 28340 4 2 1136
3703 9651 37991 5 2 5948
232 6372 44363 5 3 6140
6825 9205 53568 6 3 2380
622 6200 59768 6 4 5578
5155 9244 69012 6 5 4089
3388 4601 73613 7 5 1213
4123 8192 81805 7 6 4069
121 3084 84889 7 7 2963
111 6669 91558 8 7 6558
1652 8008 99566 8 8 6356
3732 5246 104812 8 9 1514
133 3457 108269 9 9 3324
7604 9990 118259 9 10 2386
-----------------
118259 9 10 (1213, 3388, 4601) (1551, 98, 1649) (10000000000, 0, 0)
115895 11 8
А если вместо правильной последней строчки:
print(sum_a - 1213 - 1151, count_odd + 1 + 1, num - count_odd - 1 - 1)
поставить неполную:
print(sum_a - 1213, count_odd + 1, num - count_odd - 1)
То получим неверный ответ как в генераторе на сайте:
117046 10 9
Видно, что четность ответа не совпадает с четностью большинства выбранных чисел. Нечетных 10, четных 8, а сумма четная.
К сожалению, похожие недочеты в ответах есть и у 27-х задач с тройками чисел. Но я не могу вспомнить точно в какой именно задаче получилось, что одно и то же число из третьей группы одновременно обменивали и с первой, и со второй. В результате ответ тоже был неправильным.
- участник сейчас на форуме
- участник вне форума