ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 103. Динамическое программирование > задача:


Макс и K-равные числа HARD

Задачи раздела

• Демоническое программирование
• ЕГЭ — B1
• Ежевика
• Жадина
• Игра с разрезанием
• Количество путей
• Макс и K-равные числа HARD
• Макс и Дом интернета
• Макс и бельевая верёвка
• Макс и перестановка цифр
• Наибольшая возрастающая подпос...
• Наибольшая общая подпоследова...
• Непрерывный рюкзак
• Несчастливые дни
• Подотрезок с максимальной суммой

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 131072/131072/131072/131072 Кб.

Макс и K-равные числа HARD
Макс и K-равные числа HARD
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очередная задача на подсчёт «особенных» чисел? Ничего умнее не смогли придумать?
— неизвестный дисквалифицированный участник

В свободное время Макс любит изучать разные виды чисел. На этот раз ему приглянулись числа со следующими свойствами:

  • Эти числа делятся на $$$K$$$ без остатка;
  • Эти числа содержат равное количество чётных и нечётных цифр.
Такие числа Макс называет $$$K$$$-равными.

Помогите Максу подсчитать количество $$$K$$$-равных чисел в диапазоне от $$$L$$$ до $$$R$$$ включительно.

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

Ввод содержит целые числа $$$L$$$, $$$R$$$ и $$$K$$$ ($$$1 \le L \le R \le 10^{18}$$$, $$$1 \le K \le 1000$$$) — соответственно границы диапазона и число, на которое интересующие числа должны делиться.

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

Выведите одно целое число — количество $$$K$$$-равных чисел в диапазоне от $$$L$$$ до $$$R$$$.

Примеры

Входные данные
1 20 2
Выходные данные
5
Входные данные
20 100 7
Выходные данные
6

Для отправки решений необходимо выполнить вход.

www.contester.ru