CPCRC1C - Sum of Digits


Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.

Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.

Majid did finally find the solution. Now it is your turn, can you find a solution?

Input

Two space-separated integers 0 <= a <= b <= 109.

Program terminates if a and b are -1.

Output

The sum of the digits of numbers a through b.

Example

Input:
1 10
100 777
-1 -1

Output:
46
8655

hide comments
cicipi: 2018-06-19 15:27:14

just same as this one .....here b<=1e15
http://www.spoj.com/problems/PR003004/

codefield: 2018-05-18 11:38:45

can be solved without digit dp

Last edit: 2018-05-18 11:48:58
r19: 2018-02-26 20:59:51

A comment was left

Akshay Aradhya: 2018-02-04 12:56:06

Digit DP :)

herkeyrefugee: 2017-11-22 07:51:05

Good one pure math!!Finally AC

gourav_123: 2017-09-27 11:06:21

wooooo !!!!! learned a new thing "DIGIT DP" :-)

kshubham02: 2017-08-25 08:59:32

Do with digit DP

anubhav1772: 2017-07-13 14:54:45

I don't know why I'm getting WA though my code passes every test case....those present on spojtoolkit as well...
Edit : Finally got AC on 4th attempt...a silly mistake cost me 3 WA

Last edit: 2017-07-13 15:31:23
rohit659: 2017-06-28 21:11:12

Very Nice Problem!!
learned new thing :-)

mddaud001: 2017-06-24 00:32:54

Digit Dp :)


Added by:Tii
Date:2010-10-25
Time limit:0.219s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://cs.ikiu.ac.ir/cms/icpc/training/7-contest/86-contest1