Форум » Обработка числовых последовательностей » Ошибка в ответе в задаче N3699 » Ответить
Ошибка в ответе в задаче N3699
Нечитайло: Отбой. Ложная тревога. Это мы с учениками не в ту сторону изменили в последней строке программы число нечетных компонентов, глядя на простую и ясную строчку. Прошу прощения. Пусть код остается в качестве примера. Он рабочий. Нужно только внимательно на последнюю строку смотреть. Здравствуйте. Есть страшные на первый взгляд 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 Вот мой код на Питоне: [pre2] #открываем файл на чтение 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) #это проще и быстрее, чем отлаживать и тестировать на ЕГЭ код для этого последнего шага #еще проще и короче вместо трех минимальных хранить в списке все нечетные разности #и печатать их в конце после сортировки, но это не так эффективно [/pre2] Вот вывод правильной программы с ответом в конце и числом нечетных и четных компонентов: [pre2] 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 [/pre2] А если вместо правильной последней строчки: [pre2] print(sum_a - 1213 - 1151, count_odd + 1 + 1, num - count_odd - 1 - 1) [/pre2] поставить неполную: [pre2] print(sum_a - 1213, count_odd + 1, num - count_odd - 1) [/pre2] То получим неверный ответ как в генераторе на сайте: [pre2] 117046 10 9 [/pre2] Видно, что четность ответа не совпадает с четностью большинства выбранных чисел. Нечетных 10, четных 8, а сумма четная. К сожалению, похожие недочеты в ответах есть и у 27-х задач с тройками чисел. Но я не могу вспомнить точно в какой именно задаче получилось, что одно и то же число из третьей группы одновременно обменивали и с первой, и со второй. В результате ответ тоже был неправильным.
Ответов - 2
Поляков: Чем плохо вот такое решение: Желтым выделена строка, где в сумму включено меньшее число из пары (в остальных случаях - большее).
Нечитайло: Упс! Простите. Это мы вручную, глядя на подобную табличку, не в ту сторону изменили количество нечетных в последней строке программы. Нечетных становится 8, четных 11, сумма четная. Все сошлось. Премного благодарен вам за сайт и ваши учебники.
полная версия страницы