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