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

Задания

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k  =  109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число  — максимально возможную сумму, соответствующую условиям задачи.

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

Файл A

Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 20 000.

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

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для указанных входных данных, в случае, если k  =  5, значением искомой суммы является число 44.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Ответ:

Решение. Будем последовательно считывать тройки чисел из файла и прибавлять к переменной sum максимальное число в тройке. Также будем находить минимальную разницу между максимальным числом в тройке и минимальным числом в тройке, между максимальным числом в тройке и средним по значению числом в тройке. Разница между числами при этом не должна делиться на 109 без остатка. В конце выполнения программы будем проверять, делится ли найденная сумма на 109 без остатка, и если не делится  — будем выводить найденную сумму, иначе будем выводить найденную сумму, вычтя из неё найденную минимальную разницу между числами.

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

var

x, y, z: integer;

n: integer;

sum: int64;

minDif: integer;

f: text;

begin

assign(f,'C:\27_B.txt');

reset(f);

readln(f, n);

sum := 0;

minDif := 40001;

while not eof(f) do begin

readln(f, x, y, z);

if (x >= y) and (x >= z) then begin

sum := sum + x;

if (((abs(x - y)) mod 109 <> 0) and (abs(x - y) < minDif)) then

minDif := abs(x - y);

if (((abs(x - z)) mod 109 <> 0) and (abs(x - z) < minDif)) then

minDif := abs(x - z);

end

else if (y >= z) and (y >= x) then begin

sum := sum + y;

if (((abs(y - x)) mod 109 <> 0) and (abs(y - x) < minDif)) then

minDif := abs(y - x);

if (((abs(y - z)) mod 109 <> 0) and (abs(y - z) < minDif)) then

minDif := abs(y - z);

end

else if (z >= x) and (z >= y) then begin

sum := sum + z;

if (((abs(z - y)) mod 109 <> 0) and (abs(z - y) < minDif)) then

minDif := abs(z - y);

if (((abs(z - x)) mod 109 <> 0) and (abs(z - x) < minDif)) then

minDif := abs(z - x);

end;

if sum mod 109 <> 0 then

writeln(sum)

else writeln(sum - minDif);

end.

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

Примечание.

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

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

f = open('27a.txt')

n = int(f.readline())

summ = 0

nekr109 = 10000000000000

for i in range(n):

a,b,c = f.readline().split()

a = int(a)

b = int(b)

c = int(c)

summ += max(a, b, c)

n1 = max(a, b, c) - min(a, b, c)

sr = a+b+c-max(a, b, c) - min(a, b, c)

n2 = max(a, b, c) - sr

if n1%109!=0:

nekr109 = min(nekr109, n1)

if n2%109!=0:

nekr109 = min(nekr109, n2)

if summ%109!=0:

print(summ)

else:

print(summ-nekr109)

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

a = [sorted(map(int,s.split())) for s in open('27.txt')][1:]

s = sum(x[2] for x in a)

difs = [x[2]-x[0] for x in a if (x[2]-x[0])%109 !=0 ] + [x[2]-x[1] for x in a if (x[2]-x[1])%109 !=0 ]

print(s if s%109 != 0 else s-min(difs))

№ п/п	№ задания	Ответ
1	36040	784594 8819088760

Ключ