Отправлено: 08.12.20 09:01. Заголовок: Тренировочная работа от 22 октября 2020 года Вариант ИН2010101

Добрый день! Задача 27. Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 3 и при этом была максимально возможной.
Входные данные
Первая строка входного файла содержит число N – общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла
6
1 3
5 10
6 9
5 4
3 3
1 1
Для указанных данных искомая сумма равна 30.

Код программы:
Fin = open("27-B.txt")
N = int( Fin.readline() )
D = 3
s, d1 = 0, 10001
d2=10001
for i in range(N):
a, b = map( int, Fin.readline().split() )
s += max( a, b )
d = abs( a-b )
if d1>d and d%D==1:
d1=d
elif d2>d and d%D==2:
d2=d
if s % D == 0:
print( s )
elif s%D==1:
print(s-d1)
else:
print(s-d2)
Fin.close()

Теперь вопрос. У меня получается правильный ответ на тестовом задании и из файла А, При решении из файла В получается расхождение с ответом, Ответ составителей 399759471, у меня 399758468. Может ли быть ошибка в ответе? И как быть в таком случае на экзамене? Ведь на это задание нельзя подать апелляцию.

Прилагаю ссылку на файл с данными https://yadi.sk/d/Hw1VJDRuYAoWPQ

 Отправлено: 09.12.20 08:12. Заголовок: Специально проверил ..

Специально проверил дельту, для всех пар чисел, остаток от деления разности которых равен 1, минимальное число 10. Откуда составители задачи взяли разность 7? Непонятно. И очень актуален вопрос, что делать на экзамене? Задание получается тестовым и подать апелляцию на него не получится.

 Отправлено: 09.12.20 08:20. Заголовок: dkonyashkin пишет: ..

dkonyashkin пишет:

цитата:

Может ли быть ошибка в ответе?

Вы не учитываете, что минимальная подходящая сумма может получиться при замене чисел в нескольких парах.

 Отправлено: 09.12.20 14:52. Заголовок: Константин Юрьевич, ..

Константин Юрьевич, спасибо. Кажется, что понял.

 Отправлено: 23.12.20 10:55. Заголовок: Константин Юрьевич, ..

Константин Юрьевич, здравствуйте.
Видимо должен расписаться в своей профнепригодности.
Как я понимаю эту задачу.
Пояснения по переменным
d1, d12 - минимальная и вторая по значению дельта, остаток от деления на 3 которой равен 1
d2, d22 - минимальная и вторая по значению дельта, остаток от деления на 3 которой равен 2
1. Выбираем наибольшее число из пары и добавляем к сумме
2. Смотрим разницу между числами пары и ее остаток от деления на 3, в зависимости от значения происходит изменение значений дельта
3. Смотрим делится ли сумма на 3, если нет, то вычитаем из нее дельту, которая убирает из суммы остаток от деления на 3.
Возможные варианты. Предположим, что остаток от деления суммы на 3 =1, убрать эту единицу мы можем либо вычитая d1, либо вычитая d2+d22. Я просто не вижу других вариантов, учитывая что одно из чисел пары обязательно должно быть задействовано.
Читаю разбор аналогичной задачи Р-00 (Демо-2021). Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что иско-мую сумму получить можно. Программа должна напечатать одно число – максимально возможную
сумму, соответствующую условиям задачи.
Отличие только в отсутствии кратности трем.
Решение:
6) если полученная сумма не делится на 3, то всё хорошо, а если делится? в этом случае нужно заменить число в одной из пар, вместо максимального взять второе, минимальное;
7) при этом для того чтобы сумма получилась максимальной нужно выбрать пару, в которой разница между числами минимальная и не делится на 3 (иначе делимость новой суммы на 3 сохранится)
8) будем искать значение dMin – минимальную разницу между числами одной из пар, не де-лящаяся на 3; тогда при выводе в случае делимости суммы s на 3 выводим s-dMin, что со-ответствует замене числа в одной паре:
Отличие только в том, что в нашей задаче будет 4 дельты, а в разобранной одна
Что делает эта часть кода в авторском решении
if r > 0:
for k in range(1, D):
r0 = (r + k) % D
dMin[r0] = min( d+dMin[k], dMin[r0] )
dMin[r] = min( d, dMin[r] )

Помогите пожалуйста.

 Отправлено: 23.12.20 11:05. Заголовок: konyashkind пишет: П..

konyashkind пишет:

цитата:

Предположим, что остаток от деления суммы на 3 =1, убрать эту единицу мы можем либо вычитая d1, либо вычитая d2+d22.

Вот это неверно. Получить максимальную сумму, которая делится на 3, можно и за счет обмена в 2-3-4-... парах, а не в одной. Как раз это учитывается с помощью массива dMin.

цитата:

Помогите пожалуйста.

Поскольку вопрос популярный и проблема общая, давайте сделаем так: я в ближайшие дни разберу подобную задачу и выложу на сайт.

 Отправлено: 23.12.20 14:44. Заголовок: Большое спасибо!..

Большое спасибо!

 Отправлено: 23.12.20 22:44. Заголовок: Выложено на сайт. См..

Выложено на сайт. См. разбор Р-01 здесь.