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