В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих
В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.
Пример входного файла:
6
3
8
14
11
2
17 В данном случае есть две подходящие пары:
Ответ:
Считаем числа из файла в массив, после чего отсортируем его. Для поиска среднего значения двух чётных чисел из массива будем использовать бинарный поиск. Для этого создадим специальную функцию, которая будет возвращать
Приведём решение на языке 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.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 15 976339247.
Ответ: 15 976339247.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open('26 (1).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] % 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.
f = open('26.txt')
n = int(f.readline())
a = []
for i in range(n):
x = int(f.readline())
a.append(x)
a.sort()
t = 0
mx = 0
for i in range(len(a)-1):
for j in range(i+1, len(a)):
if a[i] % 2 == 0 and a[j] % 2 == 0:
sr = (a[i] + a[j]) // 2
l = -1
r = len(a) + 1
while r - l > 1:
mid = (r + l) // 2
if a[mid] > sr:
r = mid
else:
l = mid
if a[l] == sr:
t += 1
mx = max(mx, sr)
print(t, mx)
Приведём решение Дмитрия Ржевского на языке Python.
f = open('26.txt')
d = set()
c = []
q = set()
for x in f:
x = int(x)
if x % 2 == 0:
c.append(x)
d.add(x)
for i in range(len(c)):
for j in range(i + 1, len(c)):
a = (c[i] + c[j]) // 2
if a in d:
q.add(a)
print(len(q), max(q))
Приведём решение Юрия Красильникова на языке Python.
a = [int(s) for s in open('26.txt')][1:]
sa = set(a)
evens = [x for x in a if x%2==0]
r = [(evens[i]+evens[j])//2 for i in range(len(evens)-1) for j in range(i+1,len(evens)) if ((evens[i]+evens[j])//2) in sa]
print(len(r),max(r))