Отправлено: 25.05.21 20:46. Заголовок: Задание № 27. Задача 2664

Условие:
(№ 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

Мое решение:

 
 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) 
 

Мои ответы:
файл А 123430
файл В 402332230

Мой ответ не сходится с ответом для файла А. Ошибся я в коде или опечатка в ответе к заданию?

 Отправлено: 25.05.21 20:52. Заголовок: Вы не учитываете, чт..

Вы не учитываете, что оптимальное решение может быть получено несколькими заменами. Посмотрите разбор задачи 27.Р-01 или авторское решение задачи 4 из основного сборника.

 Отправлено: 25.05.21 20:59. Заголовок: Понял, спасибо)..

Понял, спасибо)

 Отправлено: 25.05.21 21:21. Заголовок: А где можно скачать ..

А где можно скачать основной сборник?

 Отправлено: 25.05.21 21:24. Заголовок: nikolya29 пишет: А г..

nikolya29 пишет:

цитата:

А где можно скачать основной сборник?

Здесь. Файл с материалами по заданию 27.

 Отправлено: 26.05.21 11:47. Заголовок: Спасибо! А вот тако..

Спасибо!

А вот такой алгоритм учитывает все возможные варианты входных данных?

 
 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) 
  
 

 Отправлено: 26.05.21 11:54. Заголовок: Думаю, что нет. ИМХО..

Думаю, что нет. ИМХО возможность множественной замены нужно "вести" в цикле, в вашем решении этого нет.

 Отправлено: 15.06.21 06:47. Заголовок: Пишу чисто для того, кто задал эту тему

Моё решение задачи с учётом бесконечного множества замен на основе массива разниц :S https://egekp.unoforum.pro/?1-16-0-00000256-000-0-0-1623728180
Конечно в реальных условиях можно на дурачка найти ответ, просто вывев сортированный массив разниц и там будет видно, что САМЫЕ первые 2 числа разниц и будут давать верный ответ (но не по отдельности), но мой вариант круче XD