Утро – самое продуктивное время. По итогу, на сегодня цель такова: взять второе 17ое задание егэ по информатике и, никуда не заглядывая, решить его. После этого – взять что-то новое и разобраться, как оно внутри устроено. Девиз на сегодня: Нет такой фигни в этом мире, в которой нельзя разобраться. Вопрос только в сроках.

В файле содержится последовательность из 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.

Блин, выглядит как реальная засада: “В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.”. Получается, тут придется внутри цикла делать еще один цикл, в котором проходить по всем элементам массива. Вчера было достаточно брать текущий и последующий элементы. Еще одно усложнение – как в питоне получить остаток от деления? Ок, гугл.. Так, с этим ясность: "Для получения остатка от деления в Python 3 используется операция, обозначающаяся символом процента «%»."

Ну, понеслась. File-New-New python file – ege-17-3.py

Заводим переменные-счетчик и максимальную сумму. Открываем файл и загоняем содержимое в массив. А вот синтаксис цикла for в питоне придется-таки погуглить ((( По итогу – два вложенных цикла, один по массиву до предпоследнего значения, внутри – от следуще-текущего до последнего. Коряво, но в коде оно будет понятнее.

count = 0
maxVal = -20000
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)):

Так, а внутри условие выглядит зубодробительным: “у которых различные остатки от деления на d  =  160 и хотя бы одно из чисел делится на p  =  7″

        if(((l[i]%160) != (l[j]%160)) and ((l[i]%7 == 0) or (l[j]%7 == 0))):

На круглых скобочках я не экономлю. А вот 160 и 7 надо бы определить как переменные, но мне ведь ехать, а не шашечки.. Скачиваем файл, запускаем.. И офигеваем от времени ожидания. Несколько секунд на два вложенных цикла, серьезно?? Еще не хватало задумываться об оптимизации алгоритма. По итогу получился вот такой код (картинкой, да, из вредности):

Даже отлаживаться почти не пришлось, пора похвалить себя и искать следующую жертву среди всех заданий егэ по информатике. Пожалуй, даже вынесу ее в отдельную часть, и это будет: День второй. Рекурсия.