Задача G. Рисунки инопланетян

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — количество дней, когда все рисунки состоят из одинаковых геометрических фигур.

Ограничения

1 ≤ N ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
2
18
2
3
25
3

Разбор

Заметим, что комбинация рисунков на полях повторяется периодично с периодом 18 дней, при этом все три рисунка состоят из одинаковых геометрических фигур тогда и только тогда, когда остаток от деления i на 18 равен 0 или 1, где i — номер дня. Поэтому ответ в задаче равен a0(N) + a1(N), где ak(N) равно количеству чисел от 1 до N, дающих остаток k при делении на 18.

Справедливы формулы: a0(N) = N div 18, a1(N) = (N − 1)div 18 + 1.

Скачать файл с подробным разбором


0.153s 0.012s 15