Задание №17 ЕГЭ Информатика с ответом и решением
Ответ: 12749665 19989
Условие
В файле содержится последовательность из 10 000 натуральных чисел. Каждое число не превышает 10 000. Определите и запишите в ответе сначала количество пар элементов последовательности, у которых различные остатки от деления на d = 160 и хотя бы одно из чисел делится на p = 7, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.
Пример входных данных:
168
7
320
328
Пример выходных данных для приведённого выше примера входных данных:
4 488
Пояснение. Из 4 чисел можно составить 6 пар. В данном случае условиям удовлетворяют пары: 168 и 320, 168 и 7, 320 и 7, 328 и 7. Максимальную сумму дает пара 168 и 320 — 488.
Подсказки — как подойти к решению
- Считай числа из файла в список: значений 10 000, по одному в строке, поэтому удобно хранить их в массиве и перебирать по индексам.
- Пара — любые два различных элемента, не обязательно соседних, и порядок в паре не важен, поэтому организуй перебор с i < j, чтобы каждая пара учитывалась один раз.
- Проверяй оба условия сразу: остатки от деления на 160 должны различаться, и хотя бы одно число должно делиться на 7; счётчик и максимум суммы обновляй только для пар, прошедших обе проверки.
Решение
Сначала считаем все числа из файла в массив. Для каждой пары будем проверять, делится ли хотя бы одно число из пары на 7, а также то, имеют ли элементы пары различные остатки от деления на 160. При успешном выполнении условия будем увеличивать значения счётчика count и проверять, больше ли сумма элементов пары текущей максимальной суммы. Если сумма элементов пары больше текущей максимальной суммы, будем обновлять значение переменной maxsum.
Приведём решение задачи на языке Pascal.
var
i, j: integer;
count: longint;
maxsum: integer;
arr: array[1..10000] of integer;
f: text;
begin
assign(f,'C:\17.txt');
reset(f);
maxsum := 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 (arr[i] mod 7 = 0) or (arr[j] mod 7 = 0) then
if (arr[i] mod 160 <> arr[j] mod 160) then begin
count := count + 1;
if arr[i] + arr[j] > maxsum then maxsum := arr[i] + arr[j];
end;
end;
writeln(count, ' ', maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла ответ — 12749665 19989.
Приведём решение задачи на языке Python.
f = open('17.txt')
a = [int(i) for i in f]
s = 0
mx = 0
for i in range(len(a) - 1):
for j in range(i + 1, len(a)):
if (a[i] % 160 != a[j] % 160) and ((a[i] % 7 == 0) or (a[j] % 7 == 0)):
s += 1
mx = max(mx, a[i] + a[j])
print(s, mx)
В результате работы данного алгоритма при вводе данных из файла ответ — 12749665 19989.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Артёма Гридина на языке Python.
from itertools import combinations
f = open('17.txt')
numbers = map(int, f.readlines())
cnt = 0
maxsum = 0
for para in combinations(numbers, 2):
if (para[0]%7 == 0 or para[1]%7 == 0) and para[0]%160 != para[1]%160:
cnt+=1
maxsum = max(maxsum, para[0]+para[1])
print(cnt, maxsum)
В результате работы данного алгоритма при вводе данных из файла ответ — 12749665 19989.
Приведём решение Сергея Донец на языке PascalABC.NET.
begin
var (d,p) := (160,7);
var t := ReadAllText('17.txt').ToIntegers
.Combinations(2)
.Where(\(a,b)->((a mod d)<>(b mod d)))
.Where(\(a,b)->(a mod p=0)or(b mod p=0));
Print(t.Count, t.Select(\(a,b)->a+b).Max);
end.
Типичные ошибки
- Числа записаны в обратном порядке: сначала идёт количество найденных пар, а затем максимальная сумма. Проверь порядок в условии.
- Каждая пара посчитана дважды: перебор шёл по всем i ≠ j, хотя порядок элементов в паре не важен. Ограничься парами с i < j.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №17 по информатике