VK Cup 2018 - Раунд 2 |
---|
Закончено |
Будем называть положительное целое число 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).
Для каждого запроса выведите одно целое число — ответ на этот запрос.
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
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
Если 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.
Название |
---|