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

Варианты заданий

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие, что i < j и a_i > a_j (первый элемент пары больше второго; i и j  — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m  =  120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Входные данные.

Файл A

Файл B

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).

В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример организации исходных данных во входном файле:

140

100

300

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

140 100 В ответе укажите четыре числа: сначала искомую пару чисел для файла А (два числа через пробел), затем для файла B (два числа через пробел).

Ответ:

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Решение. Сумма a_i и a_j делится на 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

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)

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом), такие, что a_i > a_j при i < j ≤ N. Среди пар, удовлетворяющих этому условию, необходимо найти и вывести пару с максимальной суммой элементов, которая делится на 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если пар заданным условием нет, то программа должна вывести 00.

Входные данные.

Файл A

Файл B

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

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

Пример организации исходных данных во входном файле:

119

118

237

123

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

237 123 В ответе укажите четыре числа: сначала значение искомой суммы для файла А (два числа через пробел), затем для файла B (два числа через пробел).

Ответ:

Пояснение. Из 7 чисел можно составить 14 пар. В данном случае условиям удовлетворяет пара: 237 и 123. Сумма 360 делится на 120, a_i > a_j, а i < j. У всех остальных пар как минимум одно из этих условий не выполняется.

Решение. Заметим, что сумма двух элементов кратна 120 тогда, когда сумма их остатков от деления на 120 будет равна 120 (или равна 0, если оба числа кратны 120). Необходимо хранить в массиве максимальные числа с остатками от 0 до 119, а каждое новое введённое число складывать с числами из массива и искать наибольшую сумму, кратную 120.

Приведём решение задачи на языке Pascal.

var

a: array[0..119] of integer;

i, j, n, x, t, n1, n2: integer;

f: text;

begin

assign(f,'28133_A.txt');

reset(f);

readln(f, n);

for i := 0 to 119 do

a[i] := 0;

n1 := 0;

n2 := 0;

for i := 1 to n do begin

readln(f, x);

t := x mod 120;

if t = 0 then t := 120;

if (a[120-t] > x) and (a[120-t] + x > n1 + n2) then begin

n1 := a[120-t];

n2 := x;

end;

if t < 120 then begin

if a[t] < x then a[t] := x;

end

else if (x > a[0]) then

a[0] := x;

end;

if n1 + n2 <> 0 then writeln(n1, ' ', n2)

else writeln('00');

end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 00, из файла B  — 9991 9689 или 9971 9709.

Примечание.

Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Петра Полякова на языке Python.

def f(x,dict):

for key,keybord in dict.items():

if key==x:

return keybord

g=open('27.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('28133_B.txt')

n=int(f.readline())

a = [int(i.strip()) for i in f]

x = 0

y = 0

max_xy = 0

for i in range (len(a)-1):

for k in range(i+1,len(a)):

if(a[i]+a[k])%120==0 and max_xy < a[i]+a[k] and a[i] > a[k]:

x =a[i]

y = a[k]

max_xy=a[i]+a[k]

print(x,y)

№ п/п	№ задания	Ответ
1	28131	8096 6544 9977 9943\|8096 6544 9982 9938\|8096 6544 9967 9953\|8096 6544 9990 9930\|8096 6544 9987 9933\|8096 6544 9978 9942\|8096 6544 9998 9922\|8096 6544 9982 9938\|8096 6544 9979 9941\|8096 6544 9966 9954\|8096 6544 9993 9927\|8096 6544 9999 9921\|8096 6544 9981 9939\|8096 6544 9975 9945\|8096 6544 9964 9956
2	28133	00 9991 9689\|00 9971 9709

Ключ