Олимпиадный тренинг

Задача . F. Минимальная разница подмножеств


Задача

Темы: дп *3200

Будем называть положительное целое число x k-красивым целым числом, если и только если возможно разбить мультимножество его цифр в десятичном представлении на два подмножества так, чтобы разница между суммой цифр в этих множествах была меньше либо равна k. Каждая цифра должна принадлежать ровно одному подмножеству послу разбиения.

Мы подготовили для вас n запросов. Каждый запрос описывается тремя целыми числами l, r и k, которые означают, что вы должны вычислить количество k-красивых целых чисел x в пределах от l до r (включительно).

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

Первая строка содержит одно целое число n (1 ≤ n ≤ 5·104) — количество запросов.

Каждая из следующих n строк описывает один запрос и содержит три целых числа l, r и k (1 ≤ l ≤ r ≤ 1018, 0 ≤ k ≤ 9).

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

Для каждого запроса выведите одно целое число — ответ на этот запрос.

Примечание

Если 1 ≤ x ≤ 9, то число x является k-красивым если и только если x ≤ k.

Если 10 ≤ x ≤ 99, то число x = 10a + b является k-красивым если и только если |a - b| ≤ k, где a и b — целые числа от 0 до 9 включительно.

100 является k-красивым только и только если k ≥ 1.


Примеры
№Входные данныеВыходные данные
1 
10
1 100 0
1 100 1
1 100 2
1 100 3
1 100 4
1 100 5
1 100 6
1 100 7
1 100 8
1 100 9
 
9
28
44
58
70
80
88
94
98
100
2 
10
1 1000 0
1 1000 1
1 1000 2
1 1000 3
1 1000 4
1 1000 5
1 1000 6
1 1000 7
1 1000 8
1 1000 9
 
135
380
573
721
830
906
955
983
996
1000

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет