Найти количество произведений пар чисел, которое кратно 10

#алгоритм #любой_язык #олимпиада

Добрый день, задача по олимпиадному программированию из егэ этого года. 

На вход подается целое положительное число N, не превышающее 10000, и последовательность
из N целых положительных чисел, не превышающих 1000. Программа должна выводить число
пар чисел, произведение чисел в которых кратно 10. При этом числа, произведение которых
мы проверяем на кратность, не обязаны стоять рядом: пара может составляться и из чисел,
взятых с разных концов последовательности. 
Пример входных данных: 

4
2 5 7 4 


Пример выходных данных: 

2 


Здесь подходят пары (2;5) и (5;4).

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


  Программа считается эффективной по времени, если время работы программы пропорционально
количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно
увеличиваться не более чем в k раз.
  Программа считается эффективной по памяти, если размер памяти, использованной в
программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.


Очень интересно разобраться с этой задачей, буду благодарен за любую помощь. Язык
программирования не важен, я хочу понять сам алгоритм. 
    

Ответы

Ответ 1

Заводим массив a на 10 элементов - по остаткам от деления на 10.
Для каждого считанного числа x увеличиваем a[x%10].
Считаем сумму:


Умножаем a[0] на сумму всех остальных элементов
Умножаем a[5] на значения по чётным индексам кроме 0
т. к. произведение двух кратных 10 чисел тоже делится на 10, a[0] * (a[0]-1)



Бррр... А теперь упрощаем:


a0 - количество чисел, которые делятся на 10
b0 - количество чисел, которые не делятся на 10
a2 - количество чисел, которые делятся на 2, но не на 10
a5 - количество чисел, которые делятся на 5, но не на 10


Обращаю внимание, что в b0 входят a2 и a5.

Ответ: a0*(a0-1+b0) + a2*a5.

И ещё упрощаем: a0-1+b0 - это n-1.

PS: В соответствии с требованиями, надо не держать массив в памяти, а обрабатывать
по мере чтения.