ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1262. Псевдоримское число

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Нельзя сказать, что программисты — рассеянный народ, но многие его отдельные представители страдают этим недугом… Однажды Артемий Сидорович тестировал заготовку своей программы. В частности, она должна была уметь определять день недели по введённой дате. Артемий Сидорович ввёл 11 октября 2003 года и получил в ответ: «Суббота». «Ага!» — обрадовался Артемий Сидорович и стал искать ошибку. Дело в том, что календарь, который висел на стене его кабинета, гласил, что 11 октября — понедельник.
После часа убитого впустую времени Артемий Сидорович поднял голову и увидел на календаре большие цифры: 1999. Выругавшись про себя и пообещав снять старый календарь, Артемий Сидорович взглянул на часы. Часовая стрелка подходила к отметке IIII. Рабочий день постепенно шёл к концу.
— Интересно, — подумал Артемий Сидорович, — ведь я много раз видел, что число 4 записывается римскими цифрами IV. Выходит, что десятичное число неоднозначно представляется в римской записи. Он вновь бросил взгляд на злосчастный календарь и подумал так:
— Пусть числа 1, 5, 10, 50, 100, 500, 1000 обозначаются римскими цифрами I, V, X, L, C, D, M. Тогда число 1999 можно записать как MDCCCCLXXXXVIIII или просто MIM. А может — MCMXCIX. Понятно, что самая короткая запись — MIM, но какая из них — правильная?
Желая устранить эту несправедливость, Артемий Сидорович решил:
— Назовём псевдоримским числом следующую последовательность цифр: A1A2An, где:
  1. Каждая цифра означает одно из чисел 1, 5, 10, 50, 100, 500, 1000, … Различные цифры обозначают различные числа. Будем обозначать числовое значение цифры A следующим образом: [A].
  2. В записи не может встречаться четырёх одинаковых цифр подряд, если эти цифры обозначают степени 10, и не может встречаться подряд двух одинаковых цифр, не являющихся степенями 10.
  3. В числе A1A2An в отношении двух соседних цифр верно следующее:
    • [Ai] ≥ [Ai+1] либо
    • ([Ai] < [Ai+1] ≤ 10[Ai] и [Ai] = 10k), где i < n.
  4. Перед цифрой не может стоять более одной цифры, меньшей её; после цифры не может стоять более одной цифры, большей её.
  5. [Ai] ≥ [Ai+1] ≥ [Ai+2], либо [Ai+2] < [Ai] < [Ai+1], либо [Аi+1] < [Ai+2] ≤ [Ai], где i < n − 1
  6. A1 = [A1].
         A1A2An = A2An − [A1], если [A1] < [A2].
         A1A2An = A2An + [A1], если [A1] > [A2].
Тогда число 4 запишется IV, а не IIII (по правилу 2). Число 1999 запишется MCMXCIX. Пусть получается не самый короткий способ записи, но зато, кажется, каждое число записывается единственным образом.

Исходные данные

В единственной строке расположено десятичное целое число N, 1 ≤ N ≤ 102003.

Результат

Выведите единственное число K — количество цифр в псевдоримской записи числа N.

Пример

исходные данныерезультат
1939
8

Замечания

1939 = MCMXXXIX
Автор задачи: Александр Ипатов
Источник задачи: Открытое командное соревнование школьников Свердловской области по программированию, 11 октября 2003 года