Задание 27 ЕГЭ по информатике

1. 1. Заводим best[r] — наибольшее встреченное число с остатком r (r = 0,1,2). Изначально пусто.
2. 2. Читаем очередное x, r = x % 3. Партнёр нужен с остатком (3 − r) % 3, чтобы сумма делилась на 3.
3. 3. Если такой партнёр уже встречался — кандидат на ответ x + best[партнёр]; обновляем общий максимум.
4. 4. Затем обновляем best[r], если x больше сохранённого.
5. 5. После потока общий максимум — ответ. Один проход, память — три ячейки.

Ответ: Максимальная сумма пары, кратная 3, за один проход

1. 1. Начинаем с пустого словаря best и ответа ans = −1. Остатки считаем по модулю 3.
2. 2. x = 5: остаток 2, нужен партнёр с остатком 1 — таких ещё нет. Запоминаем best[2] = 5.
3. 3. x = 9: остаток 0, нужен партнёр с остатком 0 — таких ещё нет. Запоминаем best[0] = 9.
4. 4. x = 4: остаток 1, нужен партнёр с остатком 2 — есть, best[2] = 5. Кандидат: 4 + 5 = 9, это больше −1, значит, ans = 9. Запоминаем best[1] = 4.
5. 5. x = 7: остаток 1, нужен партнёр с остатком 2 — есть, best[2] = 5. Кандидат: 7 + 5 = 12, больше 9, значит, ans = 12. Обновляем best[1] = 7, потому что 7 больше 4.
6. 6. x = 2: остаток 2, нужен партнёр с остатком 1 — есть, best[1] = 7. Кандидат: 2 + 7 = 9, это меньше 12, ответ не меняется. Обновлять best[2] не нужно: 2 меньше 5.
7. 7. Ответ: 12 (пара 5 и 7). Проверим перебором: суммы, кратные 3, — это 5 + 4 = 9, 5 + 7 = 12, 9 + 9 не годится (один элемент), 4 + 2 = 6, 7 + 2 = 9. Наибольшая действительно 12.
8. 8. Сколько операций мы сделали. Пять — по числу элементов. Перебор всех пар потребовал бы десяти. На пяти числах разница незаметна, на миллионе — решающая.

Ответ: 12

1. 1. Шаг 1. Приём тот же, что и для максимума, но корзины хранят минимум, а не максимум. Логика симметрична: чтобы сумма была наименьшей, оба слагаемых должны быть наименьшими в своих корзинах остатков.
2. 2.

   BESKONECHNOST = 10**18
   lucshiy = [BESKONECHNOST] * 3      # минимум в каждой корзине остатка
   otvet = BESKONECHNOST

   for line in open('27.txt'):
       x = int(line)
       r = x % 3
       nuzhen = (3 - r) % 3
       if lucshiy[nuzhen] < BESKONECHNOST:
           s = x + lucshiy[nuzhen]
           if s < otvet:
               otvet = s
       if x < lucshiy[r]:
           lucshiy[r] = x
   print(otvet)

3. 3. Шаг 2. Разложим числа по остаткам от деления на 3: 14 даёт 2, 7 даёт 1, 22 даёт 1, 9 даёт 0, 30 даёт 0, 3 даёт 0, 18 даёт 0, 25 даёт 1.
4. 4. Шаг 3. Трассировка. x = 14 (остаток 2). Нужен остаток 1, корзина пуста — пары нет. Кладём 14 в корзину 2.
5. 5. x = 7 (остаток 1). Нужен остаток 2, там лежит 14 → сумма 21, кратна трём ✔ Ответ пока 21. Кладём 7 в корзину 1.
6. 6. x = 22 (остаток 1). Нужен остаток 2, там 14 → сумма 36, больше 21 — ответ не меняется. В корзине 1 лежит 7, а 22 больше — не заменяем: нам нужен минимум.
7. 7. x = 9 (остаток 0). Нужен остаток 0, корзина нулевых пуста — пары нет. Кладём 9 в корзину 0.
8. 8. x = 30 (остаток 0). Нужен остаток 0, там 9 → сумма 39, больше 21. В корзине 0 остаётся 9.
9. 9. x = 3 (остаток 0). Нужен остаток 0, там 9 → сумма 12, меньше 21 → ответ 12. Теперь 3 меньше 9 → корзина 0 становится равна 3.
10. 10. x = 18 (остаток 0). Нужен остаток 0, там 3 → сумма 21, больше 12. Корзина 0 остаётся 3.
11. 11. x = 25 (остаток 1). Нужен остаток 2, там 14 → сумма 39, больше 12.
12. 12. Шаг 4. Ответ: 12 (пара 9 и 3). Проверка перебором всех 28 пар даёт тот же результат ✔
13. 13. Шаг 5. Две вещи, которые надо поменять по сравнению с версией для максимума: стартовое значение корзин (бесконечность вместо нуля) и направление сравнений (меньше вместо больше). Всё остальное, включая порядок «сначала ищем пару, потом кладём число», остаётся прежним.
14. 14. Шаг 6. Зачем бесконечность, а не ноль. Ноль был бы меньше любого числа файла, и программа решила бы, что в каждой корзине уже лежит нулевой элемент. Для максимума ноль годился, потому что числа положительны; для минимума нужна заведомо большая величина — либо 10**18, либо float('inf'), либо None с проверкой.

Ответ: 12

1. 1. Шаг 1. Наивное решение перебирает все пары — O(n²), и на файле линии 27 это неприемлемо.
2. 2. Шаг 2. Идея одного прохода. Зафиксируем правый элемент a[j] и спросим: какое вычитаемое даст наибольшую разность? Наименьшее из всех, стоящих левее. Его можно держать в одной переменной и обновлять по ходу.
3. 3.

   minimum_sleva = a[0]
   lucshee = 0
   for j in range(1, len(a)):
       if a[j] - minimum_sleva > lucshee:
           lucshee = a[j] - minimum_sleva
       if a[j] < minimum_sleva:
           minimum_sleva = a[j]
   print(lucshee)

4. 4. Шаг 3. Трассировка. Начало: минимум слева = 7, лучшее = 0.
5. 5. j = 1, a[j] = 2. Разность 2 − 7 = −5, меньше нуля — рекорд не меняется. Но 2 < 7 → минимум слева становится 2.
6. 6. j = 2, a[j] = 9. Разность 9 − 2 = 7 > 0 → лучшее 7. Минимум не меняется.
7. 7. j = 3, a[j] = 4. Разность 4 − 2 = 2, меньше 7 — без изменений.
8. 8. j = 4, a[j] = 11. Разность 11 − 2 = 9 > 7 → лучшее 9.
9. 9. j = 5, a[j] = 5. Разность 3, меньше 9 — без изменений.
10. 10. Шаг 4. Ответ: 9 (это 11 − 2). Перебор всех пятнадцати пар даёт то же число ✔
11. 11. Шаг 5. Обратите внимание на порядок двух условий: сначала считается разность, и только потом обновляется минимум. Поменяй их местами — и элемент вычтется сам из себя, дав ноль там, где ответа быть не должно.
12. 12. Шаг 6. Почему стартовое значение рекорда ноль, а не минус бесконечность. В этой формулировке разность берут неотрицательной по смыслу: если последовательность убывает, ответ 0 (пара не найдена). Если же условие допускает отрицательный ответ, стартовать надо с None и проверять — иначе ноль выиграет у настоящего ответа.
13. 13. Шаг 7. Приём общий и стоит отдельного запоминания: если внутренний цикл ищет минимум, максимум или сумму по всем предыдущим элементам, он заменяется одной переменной. Так квадратичное решение превращается в линейное, и именно за это в линии 27 дают баллы.

Ответ: 9