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

Задания

В текстовом файле записан набор натуральных чисел, не превышающих 10⁹. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют одинаковую чётность, а их сумма тоже присутствует в файле, и чему равна наибольшая из сумм таких пар.

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

Задание 26

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.

В ответе запишите два целых числа: сначала количество пар, затем наибольшую сумму.

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

17 В данном случае есть две подходящие пары: 3 и 11 (сумма 14), 8 и 14 (сумма 22). В ответе надо записать числа 2 и 22.

Ответ:

Решение. Считаем числа из файла в массив, после чего отсортируем его. Для поиска суммы двух чисел одинаковой чётности из массива будем использовать бинарный поиск. Для этого создадим специальную функцию, которая будет возвращать значение True, если в массиве будет найдено искомое значение. В этом случае в переменной count будем накапливать единицу. Также в переменную maxSum будем записывать максимальное найденное значение, удовлетворяющее условиям.

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

type mt = array [1..5000] of integer;

var

n, i, j, t, sum, count, maxSum: integer;

arr: mt;

f: text;

function binSearch(left, right, num: integer; arr: mt):boolean;

var mid: integer;

begin

while right > left + 1 do begin

mid := (left + right) div 2;

if arr[mid] > num then right := mid

else if arr[mid] < num then left := mid

else begin

binSearch := true;

exit;

end;

binSearch := false;

end;

begin

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

reset(f);

readln(f, n);

for i := 1 to n do readln(f, arr[i]);

for i := 1 to n do

for j := i + 1 to n do

if arr[i] > arr[j] then begin

t := arr[i];

arr[i] := arr[j];

arr[j] := t;

end;

count := 0;

maxSum := 0;

for i := 1 to n - 1 do begin

for j := i + 1 to n do begin

if ((arr[i] + arr[j]) mod 2 = 0) then begin

sum := arr[i] + arr[j];

if binSearch(i, n, sum, arr) then begin

count := count + 1;

if sum > maxSum then maxSum := sum;

end;

writeln(count, ' ', maxSum);

end.

В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ  — 10 933100556.

Ответ: 10 933100556.

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

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

f = open('inf_26_04_21_26.txt')

k = f.readlines()

n = list(map(int, k))

m = 0

s = 0

c = 0

ns = set(n)

for i in range(1, len(n) - 1):

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

if ((n[i] + n[j]) % 2 != 1):

s = n[i] + n[j]

if (s in ns):

c += 1

if s > m:

m = s

print(c, m)

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

from itertools import combinations

f = open('inf_26_04_21_26.txt')

f.readline()

a = list(map(int,f))

c = set(a)

b = list(filter(lambda x: sum(x) % 2 == 0 and sum(x) in c, combinations(a,2)))

print(len(b), sum(max(b, key = lambda i: sum(i))))

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

a = [int(s) for s in open('inf_26_04_21_26.txt')][1:]

sa = set(a)

r = [a[i] + a[j] for i in range(len(a) - 1) for j in range(i + 1,len(a)) if a[i]%2 == a[j]%2 and (a[i] + a[j]) in sa]

print(len(r),max(r))

№ п/п	№ задания	Ответ
1	36881	10 933100556

Ключ