Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2430. Первоклассные числа
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 02/11/2018 | Муниципальный этап 10-11 классы (2) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Если взять натуральное число и найти сумму квадратов его цифр, затем сумму
квадратов цифр результата и так далее, то через несколько шагов для некоторых из чисел получится число 1.
Такие числа будем называть первоклассными. Например, первоклассным будет число 19,
так как `1^2+9^2=82`, `8^2+2^2=68`, `6^2+8^2=100`, `1^2+0^2+0^2=1`. А числа 2 или 5 первоклассными
не являются.
Напишите программу, которая находит количество первоклассных чисел среди чисел в диапазоне от `A` до `B` включительно.
Первая строка ввода содержит два целых чисел `A`, `B`.
Вывести одно целое число – количество первоклассных чисел среди чисел в диапазоне от `A` до `B`.
Пример ввода
1 20
Пример вывода
5
Описание подзадач и системы оценивания
Подзадача 1 (25 баллов)
`1\ ≤\ A\ ≤\ B\ ≤\ 10^6`, `B\ -\ A\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (25 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ A\ ≤\ B\ ≤\ 10^9`, `B-\ A\ ≤\ 10^6`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (50 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ A\ ≤\ B\ ≤\ 10^{18}`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
