В текстовом файле записан набор натуральных чисел, не превышающих 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 = 1) 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.
Приведём решение на языке 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)
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 15 954387771.
Ответ: 15 954387771.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
a = set([int(s) for s in open('inf_26_04_21_26.txt')])
even = [x for x in a if x%2==0]
odd = [x for x in a if x%2==1]
sums = [x+y for x in even for y in odd if x+y in a]
print(len(sums),max(sums))