Задание 27
Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 и являющимся произведением двух элементов последовательности с различными номерами. Гарантируется, что хотя бы одно такое произведение в последовательности есть.
Входные данные (два файла):
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример организации исходных данных во входном файле:
5
40
1000
7
28
55
Пример выходных данных для приведённого выше примера входных данных: 28000
В ответе укажите два числа: сначала значение искомого произведения для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение:
Обратите внимание, что метод перебора всех пар чисел, а затем подсчета их произведения и проверка его кратности 14, является плохим способом. Это будет работать на небольших файлах. Но файл из 50 000 элементов повесит нашу программу. К примеру, для файла из 5 элементов нужно сделать 20 инструкций сравнения:
Для больших N количество сравнений растет квадратично, что сильно замедлит наш алгоритм полного перебора.
Количество пар, которые мы на самом деле должны проверить, будет заметно меньше 20, если мы сразу выберем только те пары, которые будут делиться на нужное нам число. Произведение двух чисел будет делиться на 14, если:
1. Первый множитель делится на 2, а второй множитель делится на 7
2. Первый множитель делится на 14, а второй любое число
3. Оба множителя делятся на 14.
Отсюда следует, что проще всего будет один раз пройтись по файлу, считывая каждый элемент отдельно, а затем исследовав его, решать куда его положить:
max_2 - переменная для максимального числа, кратного 2;
max_7 - переменная для максимального числа, кратного 7;
max_14 - переменная для максимального числа, кратного14;
max - переменная для максимального числа из всего файла;
Далее необходимо будет сравнить между собой только два произведения и выбрать из них максимальное: max_2 * max_7 > max_14 * max ?
Код реализации программы на Pascal:
Код реализации программы на Python:
Считаете ли Вы сложными задачи из ЕГЭ по информатике? Поделитесь своим мнением в комментариях
Если Вам нужна помощь или репетитор по физике, математике или информатике/программированию, Вы можете написать в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram