РЕШУ ЕГЭ — информатика

Задания

На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых различные остатки от деления на d  =  160 и хотя бы одно из чисел делится на p  =  7. Среди таких пар, необходимо найти и вывести пару с максимальной суммой элементов.

Описание входных и выходных данных.

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата программа должна напечатать элементы искомой пары. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если таких пар нет, то вывести два нуля.

Пример входных данных:

168

320

328

Пример выходных данных для приведённого выше примера входных данных:

168 320

Пояснение: Из 4 чисел можно составить 6 пар. В данном случае условиям удовлетворяют пары: 168 и 320, 168 и 7, 320 и 7, 328 и 7. Максимальную сумму дает пара 168 и 320.

Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,  — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени  — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

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

Решение. Отметим:

m71 самое большое число кратное 7;

m72 второе по величине число кратное 7 и остаток от деления на 160 не равен остатку от деления m71 на 160;

m1 самое большое число не кратное 7;

m2 второе по величине число не кратное 7 и остаток от деления на 160 не равен остатку от деления m71 на 160.

Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.

var 
    n, i, m71, m72, m1, m2, max1, max2, x: integer;
begin
    readln(N);
    m71:=0;
    m72:=0;
    m1:=0;
    m2:=0;
    max1:=0;
    max2:=0;
for i:= 1 to n do begin
    readln(x);
    if (x mod 7 = 0) and (x mod 160 = m71 mod 160) and (x > m71) then
        m71 := x
    else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m71) then
    begin
        m72 := m71;
        m71 := x;
    end
    else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m72) then
        m72 := x
    else if (x mod 7 <> 0) and (x mod 160 = m1 mod 160) and (x > m1) then
        m1 := x  
    else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m1) then
    begin
        m2 := m1;
        m1 := x;
    end
    else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m2) then
        m2 := x;   
end;
if (m71 = 0) and (m72 = 0) then
    writeln(0, ' ', 0)
else if (m72 = 0) and (m2 = 0) and (m71 mod 160 = m1 mod 160) then
    writeln(0, ' ', 0)
else
begin
    if (m71+m72)>(max1+max2) then
    begin
        max1 := m71;
        max2 := m72;
    end;
    if ((m71+m1)>(max1+max2)) and (m71 mod 160 <> m1 mod 160) then
    begin
        max1 := m71;
        max2 := m1;
    end;
    if ((m71+m2)>(max1+max2)) and (m71 mod 160 <> m2 mod 160) then
    begin
        max1 := m71;
        max2 := m2;
    end;
    if (((m72 + m1) > (max1 + max2)) and ((m72 mod 160) <> (m1 mod 160))) then
    begin
        max1 := m72;
        max2 := m1;
    end;
    writeln(max1, ' ', max2);
end;
end.

Пример 2. Программа на языке Python 3. Программа эффективна по времени и памяти.

n = int(input())
m71=0
m72=0
m1=0
m2=0
max1=0
max2=0
for i in range (n):
    x = int(input())
    if (x % 7 == 0) and (x % 160 == m71 % 160) and (x > m71):
        m71 = x
    elif (x % 7 == 0) and (x % 160 != m71 % 160) and (x > m71):
        m72 = m71
        m71 = x
    elif (x % 7 == 0) and (x % 160 != m71 % 160) and (x > m72):
        m72 = x
    elif (x % 7 != 0) and (x % 160 == m1 % 160) and (x > m1):
        m1 = x  
    elif (x % 7 != 0) and (x % 160 != m1 % 160) and (x > m1):
        m2 = m1
        m1 = x
    elif (x % 7 != 0) and (x % 160 != m1 % 160) and (x > m2):
        m2 = x    
if (m71 == 0) and (m72 == 0):
    print(0,0)
elif (m72 == 0) and (m2 == 0) and (m71 % 160 == m1 % 160):
    print(0,0)
else:
    if (m71+m72)>(max1+max2):
        max1 = m71
        max2 = m72
    if (m71+m1)>(max1+max2) and (m71 % 160 != m1 % 160):
        max1 = m71
        max2 = m1
    if (m71+m2)>(max1+max2) and (m71 % 160 != m2 % 160):
        max1 = m71
        max2 = m2
    print(max1,max2)

Критерии проверки:

Пояснения для проверяющих.

1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.

2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения.

3. Каждая из программ, представленных экзаменуемым (но не более двух), оценивается по нижеследующим критериям. В качестве итоговой оценки берётся наибольшая из двух оценок.

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку.	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок (описок) указанных выше видов — не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок: 1) ошибка при инициализации минимумов; 2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены; 3) допущен выход за границу массива; 4) используется знак < вместо <=, or вместо and и т. п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности: min := 2001; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i]+a[j]) mod 2 = 1) and (a[i]+a[j] < min) then min := a[i]+a[j]; end end;	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок.	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

Ключ