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

Чемпионат Урала 2015

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Физкультура

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Раз в неделю андроид Вася посещает занятия по физической подготовке. Преподаватель, который проводит эти занятия, считает, что тренировать нужно не только физические навыки, но и умение думать. Поэтому он часто дает своей группе задания, которые не так просто выполнить.
Вот каким было сегодняшнее задание. Изначально n андроидов стояли в одну шеренгу. Преподаватель выдал им различные номера, записанные десятичными цифрами. Все номера лежали в пределах от 1 до n и соответствовали порядку, в котором стояли андроиды, слева направо. По команде преподавателя ученики должны были перестроиться в шеренгу в другом порядке так, чтобы для любых двух рядом стоящих андроидов выполнялось одно из двух условий:
  • сумма цифр в номере левого андроида меньше суммы цифр в номере правого;
  • суммы цифр их номеров равны, и номер левого андроида меньше номера правого.
Группа долго выполняла это задание, а Васе оно показалось очень скучным. Ведь ему даже не пришлось сдвинуться с места — он стоял первым в шеренге.
Пока все остальные перестраивались, Вася задался вопросом, сколько еще андроидов остались на своих местах. Помогите Васе посчитать это.

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

В единственной строке записано целое число n — количество андроидов в группе (2 ≤ n ≤ 109).

Результат

Выведите количество андроидов, оставшихся на своих местах.

Пример

исходные данныерезультат
19
3

Замечания

После перестроения андроиды заняли места в таком порядке: 1, 10, 2, 11, 3, 12, 4, 13, 5, 14, 6, 15, 7, 16, 8, 17, 9, 18, 19. Кроме Васи, на месте остались еще андроиды с номерами 18 и 19.
Автор задачи: Александр Ипатов (подготовил Булат Зайнуллин)
Источник задачи: XIX Открытый чемпионат Урала по спортивному программированию (апрель, 2015)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2052. Физкультура