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

Задания

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

Файл A

Файл B

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

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

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

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

Ответ:

Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.

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

var

N: integer;

a: integer;

i: integer;

max: array [0..1] of integer;

max17: array [0..1] of integer;

f: text;

begin

max[0] := 0;

max[1] := 0;

max17[0] := 0;

max17[1] := 0;

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

reset(f);

readln(f, n);

for i := 1 to n do begin

readln(f, a);

if (a mod 17 = 0) and (a mod 2 = 0) and (a >= max17[0]) then begin

if max17[0] > max[0] then max[0] := max17[0];

max17[0] := a;

end

else if (a mod 17 = 0) and (a mod 2 = 1) and (a >= max17[1]) then begin

if max17[1] > max[1] then max[1] := max17[1];

max17[1] := a;

end

else if (a mod 17 > 0) and (a mod 2 = 0) and (a > max[0]) then max[0] := a

else if (a mod 17 > 0) and (a mod 2 = 1) and (a > max[1]) then max[1] := a;

end;

if (max[0] = 0) or (max17[0] = 0) then begin

max[0] := 0;

max17[0] := 0;

end;

if (max[1] = 0) or (max17[1] = 0) then begin

max[1] := 0;

max17[1] := 0;

end;

if (max[0] + max17[0]) > (max[1] + max17[1]) then begin

if max[0] > max17[0] then writeln(max[0], ' ', max17[0])

else writeln(max17[0], ' ', max[0])

end

else then begin

if max[1] > max17[1] then writeln(max[1], ' ', max17[1])

else writeln(max17[1], ' ', max[1])

end;

end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 8759 3077, из файла B  — 10000 9996.

Примечание.

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

Приведём решение Юрия Красильникова на языке Pascal.

var

nums: array [0..3] of integer;

n, ctg, p1, p2, i, x, second: integer;

f: text;

begin

assign(f,'27991_B.txt');

reset(f);

readln(f, n);

p1 := 0; p2 := 0;

for i := 0 to 3 do nums[i] := 0;

for i := 1 to n do begin

readln(f, x);

ctg := x mod 2;

if (x mod 17) = 0 then ctg := ctg+2;

if ctg > 1 then second := nums[ctg-2]

else if nums[ctg] > nums[ctg+2] then second := nums[ctg] else second := nums[ctg+2];

if (second>0) and (x+second > p1+p2) then

begin

p1 := x; p2 := second

end;

if x > nums[ctg] then nums[ctg] := x

end;

if p1 > p2 then writeln(p1,' ',p2) else writeln(p2,' ',p1)

end.

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

f = open("27991_B.txt") # для файла A укажите его название

s = f.readlines()

n = int(s[0])

max_ch = 0

max_n = 0

max_ch17 = 0

max_n17 = 0

for i in range(1, n + 1):

s[i] = int(s[i])

if s[i] % 2 == 0:

if s[i] % 17 == 0 and s[i] > max_ch17:

max_ch17 = s[i]

elif s[i] % 17 == 0 and s[i] <= max_ch17: # поиск второго максимума

if s[i] > max_ch:

max_ch = s[i]

elif s[i] > max_ch:

max_ch = s[i]

elif s[i] % 2 != 0:

if s[i] % 17 == 0 and s[i] > max_n17:

max_n17 = s[i]

elif s[i] % 17 == 0 and s[i] <= max_n17:

if s[i] > max_n:

max_n = s[i]

elif s[i] > max_n:

max_n = s[i]

if max_n17 + max_n == 0 and max_ch17 + max_ch == 0:

print(0, 0)

elif max_n17 + max_n > max_ch17 + max_ch:

print(max_n17, max_n)

else:

print(max_ch17, max_ch)

Приведём решение Юрия Красильникова на языке Python.

f = open('27991_A.txt')

n = int(f.readline())

nums = [0]*4 # максимальное число в каждой из категорий (см. ниже)

pair = [0,0] # наилучшая пара

for s in f:

x=int(s)

ctg = (x%17!=0)*2 + x % 2 # ctg - категория (0-3):

# 0 - четное, делится на 17; 2 - четное, не делится на 17;

# 1 - нечетное, делится на 17; 3 - нечетное, не делится на 17;

second = max(nums[ctg],nums[ctg+2]) if ctg < 2 else nums[ctg-2]

if second > 0 and x + second > sum(pair):

pair = sorted([x,second],reverse=True)

nums[ctg] = max(nums[ctg],x)

print(*pair)

Приведём решение Арсения Пышнного на языке Python.

def func(x, y):

if len(x)>=2:

for i in y:

if (x[0]+i)%2==0 and (x[0]+i)>(x[0]+x[1]):

return (i, x[0])

elif (x[0]+i)<(x[0]+x[1]):

return (x[0], x[1])

elif len(x)==1:

for i in y:

if (x[0]+i)%2==0:

return (i, x[0])

with open("27991_B.txt") as f:

sp = sorted(map(int, f.readlines()[1:]),reverse=True)

sp_17 = [i for i in sp if i%17==0]

sp.sort(key=lambda x: x%17==0)

print(sp[:10], sp_17[:10])

print(func(sp_17, sp))

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

file = open('27991_A.txt')

a = sorted([int(i) for i in file][1:], reverse=True)

flag = True

for j in range(len(a)):

m = a[j]

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

if (a[i] % 17) == 0 and (a[i] - m) % 2 == 0:

print(m, a[i])

flag = False

break

if flag == False:

break

№ п/п	№ задания	Ответ
1	27991	8759 3077 10000 9996\|3077 8759 10000 9996\|3077 8759 9996 10000\|8759 3077 9996 10000

Ключ