Задание №17 ЕГЭ Информатика с ответом и решением
Ответ: 625876 9920
Условие
В файле содержится последовательность из 10 000 целых положительных чисел. Каждое число не превышает 10 000. Определите и запишите в ответе сначала количество пар элементов последовательности, у которых разность элементов кратна 80, затем максимальную из разностей элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.
Подсказки — как подойти к решению
- Читай числа из файла программой: 10 000 значений по одному в строке. Здесь важна разность элементов, поэтому бери её модуль, чтобы результат не зависел от того, в каком порядке числа стоят в паре.
- Полезный приём — разложить числа по остаткам от деления на 80: у чисел с одинаковым остатком разность всегда кратна 80, поэтому пары удобно считать группами, а не полным перебором.
Решение
Сначала считаем все числа из файла в массив. Для каждой пары будем проверять, кратна ли 80 разность элементов пары. Если разность элементов кратна 80, будем увеличивать значения счётчика count и проверять, больше ли разность элементов пары текущей максимальной разности. Если разность элементов пары больше текущей максимальной разности, будем обновлять значение переменной maxdif.
Приведём решение задачи на языке Pascal.
var
i, j: integer;
count: longint;
maxdif: integer;
arr: array[1..10000] of integer;
f: text;
begin
assign(f,'C:\17.txt');
reset(f);
maxdif := 0;
count := 0;
for i := 1 to 10000 do readln(f, arr[i]);
for i := 1 to 10000 - 1 do
for j := i + 1 to 10000 do begin
if (abs(arr[i] - arr[j]) mod 80 = 0) then begin
count := count + 1;
if abs(arr[i] - arr[j]) > maxdif then maxdif := abs(arr[i] - arr[j]);
end;
end;
writeln(count, ' ', maxdif);
end.
Приведём решение Николая Чуркина (Тимашевск) на языке Python.
count = m = 0
f = open('17.txt')
l = [int(i) for i in f]
for i in range(len(l) - 1):
for j in range(i+1, len(l)):
if (l[i] - l[j]) % 80 == 0:
count += 1
m = max(m, abs(l[i] - l[j]))
print(count, m)
В результате работы данного алгоритма при вводе данных из файла ответ — 625876 9920.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Валерия Григорьева на языке Python.
f = open('137.txt')
mx = [-1]*80
mn = [100000]*80
dvs = [0]*80
for i in f:
a = int(i)
b = a % 80
dvs[b] += 1
if mn[b] > a:
mn[b] = a
if mx[b] < a:
mx[b] = a
sm = 0
smmx = 0
for i in range(80):
sm += dvs[i]*(dvs[i]-1)//2
if (mx[i]-mn[i]) > smmx:
smmx = mx[i]-mn[i]
print(sm, smmx)
Приведём программу Сергея Донец на PascalABC.NET:
begin
var p:=ReadAllLines('17.txt').Select(x->x.ToInteger);
var m:=p.Combinations(2)
.Where(\(a,b)->(a-b).divs(80)).ToArray;
m.Length.print;
m.Max(\(a,b)->a-b).Print;
end.
Типичные ошибки
- Максимальная разность берётся только среди пар с разностью, кратной 80: разница между наибольшим и наименьшим числом файла этому условию, скорее всего, не удовлетворяет.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №17 по информатике