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

Задания

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

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

Задание 26

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

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

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

11 В данном случае есть две подходящие пары: 9 и 13 (среднее арифметическое 11), 9 и 11 (среднее арифметическое 10). В ответе надо записать числа 2 и 11.

Ответ:

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

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

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

var

n, i, j, t, sredn, count, maxSredn: 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:\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;

maxSredn := 0;

for i := 1 to n - 1 do begin

if (arr[i] mod 2 <> 0) then

for j := i + 1 to n do begin

if (arr[j] mod 2 <> 0) then begin

sredn := (arr[i] + arr[j]) div 2;

if binSearch(i, j, sredn, arr) then begin

count := count + 1;

if sredn > maxSredn then maxSredn := sredn;

end;

writeln(count, ' ', maxSredn);

end.

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

Ответ: 14 679730035.

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

with open('26.txt') as f:

kol = f.readline()

numbers=[int(x) for x in f]

numbers4=[int(x) for x in numbers if int(x)%2!=0]

i=0

k=0

sr=0

maxsr=0

while i != len(numbers4):

for h in range(i+1,len(numbers4)):

if ((numbers4[i] + numbers4[h])//2) in numbers:

k=k+1

sr = ((numbers4[i] + numbers4[h])//2)

maxsr = max(sr,maxsr)

i=i+1

print(k,maxsr)

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

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

f = open('26.txt')

kol = f.readline()

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] % 2 != 0 and n[j] % 2 != 0:

s = (n[i] + n[j]) // 2

if s in ns:

c += 1

if s > m:

m = s

print(c, m)

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

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

sa = set(a)

odds = [x for x in a if x%2==1]

r = [(odds[i]+odds[j])//2 for i in range(len(odds)-1) for j in range(i+1,len(odds)) if ((odds[i]+odds[j])//2) in sa]

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

№ п/п	№ задания	Ответ
1	35915	14 679730035

Ключ