Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 728 977 9982 9992
Условие
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых различные остатки от деления на d = 160 и хотя бы одно из чисел делится на p = 7. Среди таких пар необходимо найти и вывести пару с максимальной суммой элементов.
Входные данные.
Файл A
Файл B
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если таких пар нет, то вывести два нуля.
Пример организации исходных данных во входном файле:
4
168
7
320
328
Пример выходных данных для приведённого выше примера входных данных:
168 320 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел по возрастанию), затем для файла B (два числа через пробел по возрастанию).
Подсказки — как подойти к решению
- Читай файл программой: важно не хранить всю последовательность, а помнить лучших представителей каждого остатка от деления на d.
- Пара допустима, только если остатки её чисел от деления на d различны и при этом хотя бы одно число делится на p. Поэтому для каждого остатка полезно отдельно помнить максимум среди кратных p и максимум среди всех остальных.
- В конце перебери пары остатков, сложи подходящие максимумы и выбери наибольшую сумму, не забыв, что элементы должны иметь разные номера, а числа пары в ответе записывают по возрастанию.
Решение
Отметим:
m71 — самое большое число, кратное 7;
m72 — второе по величине число, кратное 7, и остаток от деления на 160 не равен остатку от деления m71 на 160;
m1 — самое большое число, не кратное 7;
m2 — второе по величине число, не кратное 7, и остаток от деления на 160 не равен остатку от деления m71 на 160.
Приведём решение задачи на языке Pascal.
var
n, i, m71, m72, m1, m2, max1, max2, x: integer;
f: text;
begin
m71:=0;
m72:=0;
m1:=0;
m2:=0;
max1:=0;
max2:=0;
assign(f,'28129_A.txt');
reset(f);
readln(f, N);
while not eof(f) do begin
readln(f, 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.
Приведём решение Ивана Корниенко на языке Pascal.
var
s, n, x, x1, k7, n7, t: integer;
a: array[0..159, 0..1] of integer;
f: text;
begin
for var j := 0 to 159 do
for var l := 0 to 1 do
a[j][l] := 0;
s := 0;
assign(f, 'C:\28129_A.txt');
reset(f);
readln(f, n);
readln(f, x);
for var i := 2 to n do
begin
t := 1;
if x mod 7 = 0 then
t := 0;
if x >= a[x mod 160][t] then
a[x mod 160][t] := x;
readln(f, x);
for var k := 0 to 159 do
for var r := 0 to 1 do
if ((x + a[k][r]) > s) and (x mod 160 <> k) and
((x * a[k][r]) mod 7 = 0) then
begin
s := x + a[k][r];
x1 := x;
end;
end;
if s = 0 then
writeln('00')
else
if (s - x1) < x1 then writeln(s - x1, ' ', x1)
else writeln(x1, ' ', s - x1)
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 728 977, из файла B — 9982 9992.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("28129_B.txt")
s = f.readlines()
m71 = 0
m72 = 0
m1 = 0
m2 = 0
max1 = 0
max2 = 0
for i in range(len(s)):
x = int(s[i])
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
if (((m72 + m1) > (max1 + max2)) and ((m72 % 160) != (m1 % 160))):
max1 = m72
max2 = m1
print(max1, max2)
Приведём решение Юрия Лысакова на языке Python.
f = open('28129_B.txt')
f.readline()
s = 0
b1 = 0
b2 = 0
a = [int(i) for i in f]
for i in range(len(a) - 1):
for j in range(i+1, len(a)):
if a[i] % 160 != a[j] % 160 and (a[i] % 7 == 0 or a[j] % 7 == 0):
if a[i] + a[j] > s:
s = a[i] + a[j]
b1 = a[i]
b2 = a[j]
print(b1,b2)
Приведём решение Юрия Красильникова на языке Python.
a = sorted([int(s) for s in open('28129_B.txt')][1:],reverse=True)
r=[[] for _ in range(160)]
for x in a: r[x%160].append(x) # распределяем по остаткам
ans = [[0,0]] # если не найдем других решений
for i in range(160):
m7 = [x for x in r[i] if x%7==0]
if m7:
dop=[r[j][0] for j in range(160) if j!=i and r[j]]
if dop: ans.append(sorted([m7[0],max(dop)]))
print(*max(ans,key=lambda x: sum(x)))
Типичные ошибки
- Ответы для файлов перепутаны местами: сначала всегда записывают результат для файла A, затем для файла B.
- Не проверено условие делимости на p: в паре оказались числа, ни одно из которых не кратно p, а такие пары в ответ попадать не должны.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике