Однопроходные алгоритмы
 

Доброго времени суток. Необходимо найти задачи олимпиадные по программированию. При решении которых если решать в лоб нужно использовать циклы, а если посидеть и подумать можно решить в один проход. Желательно с решениями. Спасибо.

Имеется в виду задачи сложности O(N), сводимые к сложности O(1)?
Хинт: Часто под однопроходным алгоритмом понимают одинарный проход по входному потоку.
Варнинг: Это часто бывает можно сделать, в ущерб компактности и/или производительности кода (например раскручивание циклов, поиск по оптимизированной хеш-таблице)