Форум » Обработка числовых последовательностей » Задание № 27. Задача 2664 » Ответить
Задание № 27. Задача 2664
nikolya29: Условие: (№ 2664) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000. Пример входного файла: 6 1 3 5 11 6 9 5 4 3 3 1 1 Для указанных входных данных значением искомой суммы должно быть число 30. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Ответы: 123720 402332230 Мое решение: [pre2] f = open('1.txt') n = int(f.readline()) list_2 = [10001]*4 sum1 = 0 for i in range(n): e, z = map(int, f.readline().split()) if 5 > (abs(e - z)) % 5 > 0: if (abs(e - z)) % 5 == 1: if list_2[0] > abs(e - z): list_2[0] = abs(e - z) if (abs(e - z)) % 5 == 2: if list_2[1] > abs(e - z): list_2[1] = abs(e - z) if (abs(e - z)) % 5 == 3: if list_2[2] > abs(e - z): list_2[2] = abs(e - z) if (abs(e - z)) % 5 == 4: if list_2[3] > abs(e - z): list_2[3] = abs(e - z) sum1 += max(e, z) if sum1 % 5 != 0: sum1 -= list_2[(sum1 % 5) - 1] print(sum1) else: print(sum1) [/pre2] Мои ответы: файл А 123430 файл В 402332230 Мой ответ не сходится с ответом для файла А. Ошибся я в коде или опечатка в ответе к заданию?
Ответов - 7
Поляков: Вы не учитываете, что оптимальное решение может быть получено несколькими заменами. Посмотрите разбор задачи 27.Р-01 или авторское решение задачи 4 из основного сборника.
nikolya29: Понял, спасибо)
nikolya29: А где можно скачать основной сборник?
Поляков: nikolya29 пишет: А где можно скачать основной сборник? Здесь. Файл с материалами по заданию 27.
nikolya29: Спасибо! А вот такой алгоритм учитывает все возможные варианты входных данных? [pre2] f = open('1.txt') n = int(f.readline()) list_2 = [0] + [10001] * 4 sum1 = 0 for i in range(n): e, z = map(int, f.readline().split()) if 5 > (abs(e - z)) % 5 > 0: if (abs(e - z)) % 5 == 1: if list_2[1] > abs(e - z): list_2[1] = abs(e - z) if (abs(e - z)) % 5 == 2: if list_2[2] > abs(e - z): list_2[2] = abs(e - z) if (abs(e - z)) % 5 == 3: if list_2[3] > abs(e - z): list_2[3] = abs(e - z) if (abs(e - z)) % 5 == 4: if list_2[4] > abs(e - z): list_2[4] = abs(e - z) sum1 += max(e, z) if sum1 % 5 == 4: if list_2[4] > (list_2[1] + list_2[3]): print(sum1 - list_2[1] - list_2[3]) else: print(sum1 - list_2[4]) elif sum1 % 5 == 3: if list_2[3] > (list_2[1] + list_2[2]): print(sum1 - list_2[1] - list_2[2]) else: print(sum1 - list_2[3]) elif sum1 % 5 == 2: print(sum1 - list_2[2]) elif sum1 % 5 == 1: print(sum1 - list_2[1]) else: print(sum1) [/pre2]
Поляков: Думаю, что нет. ИМХО возможность множественной замены нужно "вести" в цикле, в вашем решении этого нет.
VectorASD: Моё решение задачи с учётом бесконечного множества замен на основе массива разниц :S https://egekp.unoforum.pro/?1-16-0-00000256-000-0-0-1623728180 Конечно в реальных условиях можно на дурачка найти ответ, просто вывев сортированный массив разниц и там будет видно, что САМЫЕ первые 2 числа разниц и будут давать верный ответ (но не по отдельности), но мой вариант круче XD
полная версия страницы