Поиск

Задача из ЕГЭ


Ограничение времени - 1 секунда

Ввод - стандартный ввод или input.txt

Ограничение памяти - 256Mb

Вывод - стандартный вывод или output.txt

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Входные данные

Первая строка ввода содержит одно целое число $$$N (2 \le N \le 100000)$$$. Вторая строка ввода содержит N целых чисел в диапазоне от 1 до $$$10^9$$$, разделенных пробелами.

Выходные данные

Вывести два целых числа — количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует — выведите одно число –1.

Примеры

Входные данные
6
1 2 701000 299000 1000 999000
Выходные данные
2 3
Входные данные
3
1 2 3
Выходные данные
-1
  • Tutorials MathJax.Hub.Config({ tex2jax: {inlineMath: [['$$$','$$$']], displayMath: [['$$$$$$','$$$$$$']]} });

    Для маленьких $$$N$$$, переберем начало последовательности, и будем складывать пока сумма не будет кратна $$$10^6$$$. Среди всех таких последовательностей выберем с наименьшей длиной и минимальным индексом. Но такое решение будет работать за $$$O(N^2)$$$, что при таких ограничения приводит к превышению времени работы.

    Давайте решим задачу при наших ограничениях. Рассмотрим частичные суммы элементов последовательности от ее начала до i-го элемента включительно. Так как нас интересуют остатки от деления суммы на 1000000 и из свойства остатков известно, что $$$(X+Y) mod M= ((X mod M) + (Y mod M)) mod M$$$, можно рассмотреть не сами суммы, а их остатки от деления. Так как нас интересует остаток равный 0, мы должны найти в последовательности остатков частичных сумм ближайшие одинаковые значения (если остатки одинаковы, значит остаток для суммы элементов подпоследовательности между ними равен 0). Для этого для каждого остатка нужно запоминать позицию, когда этот остаток встречался и находить минимальный вариант для разницы позиций.

    • Для отправки решения задачи необходимо авторизоваться!

    Разбор задачи