Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2138. Sum of distances
Динамическое программирование и запоминающие функцииОлимпиадные задачи на английском языке
| 21/07/2014 | Лето 2014 - 15 (E) |
Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
The distance between two integers is defined as the sum of the absolute result of subtracting their
digits. For example, the distance between the numbers 4561 and 3278 is `|4\ –\ 3|\ +\ |5\ -\ 2|\ +\ |6\ -\ 7|\ +\ |1\ -\ 8|\ =\ 12`.
If one of the numbers consists of fewer digits than the other, we fill it with leading
zeroes. Therefore, the distance between the numbers 32 and 5678 is `|0\ -\ 5|\ +\ |0\ -\ 6|\ +\ |3\ -\ 7|\ +\ |2\ -\ 8|\ =\ 21`.
You are given two integers `A` and `B`. Calculate the sum of distances between each pair of numbers
belonging in the interval `[A,\ B]`!
The first and only line of input contains integers `A`, `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^50000`).
The first and only line of output must contain the required number from the text. Given that the
number could be extremely large, output answer modulo `1\ 000\ 000\ 007`.
Sample Input #1
1 5
Sample Output #1
40
Sample Input #2
288 291
Sample Output #2
76
Sample Input #3
1000000 10000000
Sample Output #3
581093400
Clarification of the second example: The distances are, respectively, (288, 289) = 1, (288, 290) = 9,
(288, 291) = 8, (289, 290) = 10, (289, 291) = 9, (290, 291) = 1. Each of them counts twice, which is in
total `2\ *\ (1\ +\ 9\ +\ 8\ +\ 10\ +\ 9\ +1)\ =\ 76`.
Source: COCI 2013/2014, contest #3