Красивые числа


Источник: Problem B. Tidy Numbers

Задача

Татьяна любит порядок во всём. Её игрушки упорядочены от самой маленькой до самой большой, её карандаши расположены от самого короткого до самого длинного, а её компьютеры расставлены от самого старого до самого нового. Однажды во время тренировки навыков счёта она заметила, что у некоторых целых чисел, записанных в десятичной системе счисления, цифры расположены в неубывающем порядке. Примеры таких чисел: 8, 123, 555 и 224488. Она решила называть такие числа красивыми. Числа, не обладающие таким свойством (20, 321, 495 и 999990), – некрасивые.

Она только что закончила перечислять все положительные числа по возрастанию от 1 до N. Каким было последнее красивое число?

Входные данные

Первая строка входных данных содержит количество тестов, T. Далее следуют T строк. В каждой строке находится целое число N, последнее число, перечисленное Татьяной.

Выходные данные

Для каждого теста выведите одну строку вида Case #x: y, где x – номер теста (начиная с 1), а y – последнее красивое число, перечисленное Татьяной.

Пределы

1 ≤ T ≤ 100.

Малый набор данных

1 ≤ N ≤ 1000.

Большой набор данных

1 ≤ N ≤ 1018.

Пример

Входные данные Выходные данные
4
132
1000
7
111111111111111110
Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Обратите внимание на то, что последний тест отсутствует в малом наборе данных.

Решение на C++

Реклама
Запись опубликована в рубрике перевод, программирование с метками . Добавьте в закладки постоянную ссылку.

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

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s