В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют одинаковую чётность, а их сумма тоже присутствует в файле, и чему равна наибольшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих
В ответе запишите два целых числа: сначала количество пар, затем наибольшую сумму.
Пример входного файла:
6
3
8
14
11
22
17 В данном случае есть две подходящие пары:
Ответ:
Считаем числа из файла в массив, после чего отсортируем его. Для поиска суммы двух чисел одинаковой чётности из массива будем использовать бинарный поиск. Для этого создадим специальную функцию, которая будет возвращать
Приведём решение на языке 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;
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;
end;
end;
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))