Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Валерий Брюсов, "Треугольник", 1918 г.
"Всё-таки поздний Брюсов с одной стороны — молодец, вон "Краткий курс науки о стихе" написал. Привёл примеры на все существующие размеры, ритмы, рифмы, строфы, работал в редких жанрах, таких как рубаи, сапфические строфы и даже стихи в форме треугольника. Зато с другой — в них нет ни капли поэзии. Какой-то аппарат для деланья стихов", — печально размышляет Тимофей.
То ли дело — математические треугольники! Какая мощь в треугольнике Паскаля! Какая красота в треугольнике Серпинского! А невозможный треугольник Пенроуза! Нет, нужно работать в этом направлении.
В результате получасовых размышлений, Тимофей описал правила построения треугольника Тимофея.
1) В его первой строке единственная цифра 0.
2) Каждая следующая строка начинается с цифры, с которой начинается предыдущая строка, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая строка начинается с 9, то следующая начнётся с 0).
3) Каждая следующая цифра строки равна предыдущей цифре, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая цифра — 9, то следующая — 0).
4) В каждой новой строке на 2 цифры больше, чем в предыдущей.
На рисунке ниже вы можете видеть треугольник Тимофея с первыми 7 строками.
Теперь Тимофей хочет узнать, сколько цифр каждого вида находится в треугольнике с первыми n строками.
Единственная строка входного файла содержит натуральное число n.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.
Выведите через пробел десять чисел — количество цифр от 0 до 9 в треугольнике.
1 ≤ n ≤ 109
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 103, получат не менее 30 баллов.
Решения, верно работающие при n ≤ 105, получат не менее 60 баллов.
Смотри рисунок.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|