Добрый день, задача по олимпиадному программированию из егэ этого года.
На вход подается целое положительное число N, не превышающее 10000, и последовательность из N целых положительных чисел, не превышающих 1000. Программа должна выводить число пар чисел, произведение чисел в которых кратно 10. При этом числа, произведение которых мы проверяем на кратность, не обязаны стоять рядом: пара может составляться и из чисел, взятых с разных концов последовательности. Пример входных данных:
4
2 5 7 4
Пример выходных данных:
2
Здесь подходят пары (2;5) и (5;4).
Решение перебором очевидно, но меня интересует решение эффективное по памяти и по времени. Под эффективностью по времени и по памяти в егэ подразумевают следующее:
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Очень интересно разобраться с этой задачей, буду благодарен за любую помощь. Язык программирования не важен, я хочу понять сам алгоритм.