Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 8096 6544 9977 9943
Условие
На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие, что i < j и ai > aj (первый элемент пары больше второго; i и j — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
Входные данные.
Файл A
Файл B
В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).
В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Пример организации исходных данных во входном файле:
6
60
140
61
100
300
59
Пример выходных данных для приведённого выше примера входных данных:
140 100 В ответе укажите четыре числа: сначала искомую пару чисел для файла А (два числа через пробел), затем для файла B (два числа через пробел).
Подсказки — как подойти к решению
- В первой строке файла — количество чисел, дальше по одному числу в строке. Пара берётся там, где первый элемент стоит раньше и больше второго, поэтому порядок просмотра последовательности важен.
- Не перебирай все пары: храни для каждого остатка от деления на модуль максимальное из уже просмотренных чисел и проверяй пару с текущим. В ответе четыре числа — пары для файлов A и B по отдельности.
Решение
Сумма ai и aj делится на m, если сумма остатков этих чисел от деления на m равна 0 или m. Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив r длиной m, изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.
Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если r[m – p] > 0, то сумма a и r[m – p] делится на m, и при условии r[m – p] > a эта пара — кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и r[0].
По окончании обработки элемента a необходимо обновить элемент r[p] значением a, если a > r[p].
Приведём решение задачи на языке Pascal.
const m = 120; {количество различных остатков}
var
{хранение максимального значения для каждого из остатков}
r: array[0..m-1] of integer;
n, a, i, p, left, right: integer;
f: text;
begin
assign(f,'28131_B.txt');
reset(f);
readln(f, n);
{обнуление массива r}
for i := 0 to m - 1 do
r[i] := 0;
{обнуление переменных для записи ответа}
left := 0; right := 0;
{ввод значений, поиск искомой пары}
for i := 1 to n do
begin
readln(f,a); {считываем очередное значение}
p := a mod m;
if p = 0 then
begin
if (r[0] > a) and (r[0] + a > left + right) then
begin
left := r[0]; right := a {обновление ответа}
end
end
else
begin
if (r[m - p] > a) and (r[m - p] + a > left + right) then
begin
left := r[m - p]; right := a {обновление ответа}
end
end;
{обновление элемента r для соответствующего остатка}
if a > r[p] then r[p] := a
end;
writeln(left, ' ',right)
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 8096 6544, из файла B — 9993 9927.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Петра Полякова на языке Python.
def f(x,dict):
for key,keybord in dict.items():
if key==x:
return keybord
g=open('28131_B.txt')
n=int(g.readline())
numbers=[int(x) for x in g]
i=0
dict={}
k=0
maxk=0
while i!=n:
for h in range(i+1,n):
if ((numbers[h]+numbers[i]) % 120 ==0) and (numbers[h] < numbers[i]) and (numbers.index(numbers[h]) > numbers.index(numbers[i])):
dict[numbers[h]+numbers[i]]=numbers[i],numbers[h]
k=numbers[h]+numbers[i]
maxk=max(k,maxk)
i=i+1
if maxk==0:
print('00')
else:print('максимальная сумма:',maxk,'.Искомые элементы:',f(maxk,dict))
Приведём решение Галины Неспятиной на языке Python.
f = open('28131_B.txt')
s = [int(i) for i in f]
r = s[0]
m=0
i1=0
j1=0
for i in range(1,r-1):
for j in range(i+1,r):
if s[i]>s[j] and (s[i]+s[j])%120==0 and (s[i]+s[j])>=m:
m=s[i]+s[j]
i1=i
j1=j
print(m,s[i1],s[j1]
Приведём решение Софьи Литвиной на языке Python.
f = open('28131_B.txt').read().split('\n')[1:]
f = list(map(int, f))
maxs = 0
maxs_l = []
for i in range(len(f)):
ostf = f[i] % 120
f1 = [j for j in f[1:] if j < f[i] and (j%120 + ostf) % 120 == 0]
if len(f1):
s = f[i] + max(f1)
if s > maxs:
maxs_l.append([f[i], max(f1), s])
maxs = s
print(*max(maxs_l, key=lambda e: e[2]))
Приведём решение Юрия Красильникова на языке Python.
d = {}
params = (0,0)
a = [int(s) for s in open('28131_B.txt')][1:]
for x in a:
res = x%120
dop = 0 if res == 0 else 120 - res
if dop in d and d[dop] > x and d[dop] + x > sum(params):
params = (d[dop],x)
d[res] = max(d.get(res,0),x)
print(*params)
Типичные ошибки
- Для второго файла использован ответ первого: массив максимумов по остаткам и накопленный результат нужно обнулять перед каждым файлом.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике