Решение задачи C4 из диагностической работы ЕГЭ 2015

Для большинства учеников самой сложной и нерешаемой задачей в ЕГЭ по информатике является задача C4.

Поэтому я разберу одну из них, и покажу, как такие задачи можно решать на языке Python.

Условие

По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел равно N (N>2), но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям:

R – сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа; суммы различных, но равных по величине допускаются);
При делении на 3 число R даёт остаток 1;
Если такого числа R нет, то контрольное значение полагается равным 1.

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

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения.

Мы не последуем их совету (не будем писать программу на Pascal), а напишем её на Python.

Вы увидите, насколько это легче и быстрее.

Решение

При делении на 3 число R даёт остаток 1. Из этого следует, что R может быть суммой или числа, дающего при делении на 3 остаток 0 с числом, дающим остаток 1, или двух чисел, дающих остаток 2.

Поэтому для вычисления R достаточно запоминать не все числа (их может быть много), а только 4: максимальное, делящееся на 3; максимальное, дающее остаток 1; и два наибольших числа, дающих остаток 2.

Решение, в общем-то, теперь очевидно. Далее я привожу программу с комментариями (без комментариев она заняла всего 25 строк).

# Язык программирования - Python 3

R_0 = R_1 = R_2_1 = R_2_2 = -2000
# Переменные, в которых мы будем хранить числа

N = int(input())
# Не будем проверять входные данные на корректность
# В ЕГЭ (но не в реальной жизни!) это не нужно

for i in range(N):
    num = int(input())
    if num % 3 == 0:
        R_0 = max(R_0, num)
        # Перезаписываем число на большее, если возможно
    elif num % 3 == 1:
        R_1 = max(R_1, num)
    elif num % 3 == 2:
        # Можно и else, но так более понятно
        if num > R_2_1:
            R_2_1, R_2_2 = num, R_2_1
            # Нужно хранить 2 наибольших числа, причём R_2_1 >= R_2_2
        elif num > R_2_2:
            R_2_2 = num

R = max(R_0 + R_1, R_2_1 + R_2_2)
# Это - вычисленное контрольное значение
if R < 0:
    # Если такого числа нет, R будет отрицательно
    # Так как все числа не превышают 1000
    R = 1
print("Вычисленное контрольное значение: {}".format(R))

# Осталось проверить пришедшее число
result = int(input())
if R == result:
    print("Контроль пройден")
else:
    print("Контроль не пройден")

Такое решение набирает максимальный балл.

Для тех, кто хочет ещё лучше подготовиться к ЕГЭ по информатике, рекомендую экспресс-курс подготовки к ЕГЭ по информатике от Фоксфорд.

Там также есть курсы для подготовки к ЕГЭ и по другим предметам.