C. Улыбающиеся числа

Ограничение времени: 2 с
Ограничение памяти: 256 M

Я не забуду никогда твои глаза, твою улыбку
Леонид Нерушенко

Ни для кого не секрет, что студенты ОНУ пишут самые оригинальные дипломные работы. Так, например, Иннокентий Неструйко, студент кафедры Продуктового Обеспечения Тоталитарных Систем, посвятил свою работу исследованию свойств так называемых «улыбающихся чисел». Он рассматривает последовательности натуральных чисел и ищет в них «улыбающиеся пары». Согласно теории улыбчивости, это такие пары чисел a, b, что b > a и при этом b расположено в последовательности позже, чем a. Кроме того, между a и b должно располагаться число c, такое что a > c и сумма a + b + c делится на 3. Поскольку студент Неструйко с лёгкостью находит все такие пары в уме, а страницы дипломной работы нужно чем-то заполнять, он просит Вас написать программу, которая бы искала количество «улыбающихся пар». Иннокентий обещал не остаться в долгу и поспособствовать вашему зачислению на его кафедру.

Ввод. В первой строке ввода содержится натуральное число N (1 ≤ N ≤ 100000) – длина последовательности. Вторая строка содержит элементы последовательности, разделённые пробелами. Все элементы – натуральные числа, не превосходящие 300000.

Вывод. Выведите единственное число – количество искомых «улыбающихся пар».

Идея – Олег Александрович Петров

Примеры

Входные данные Результат работы
4
5 4 6 3
1
About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий