Yet another SOD problem solution codechef

• For Solution

  Click Here!

Ujan is a software developer. He is developing a software that takes two integers LL and RR and outputs the count of integers in the sequence L,L+1,…,R−1,RL,L+1,…,R−1,R whose sum of digits (SOD) is divisible by 33.

He has developed the user interface (UI) quite easily. He is having a hard time finding the logic to solve the problem. As you are not only a good friend of Ujan but also a good problem solver, he asks you to help him out.

Can you solve the problem for your friend, Ujan?

Yet another SOD problem solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The only line of each test case contains two integer L,RL,R.

Output Format

For each test case, print a single line containing one integer equal to the count of of integers in the sequence, whose sum of digits is divisible by 33 .

Yet another SOD problem solution codechef

• 1≤T≤1041≤T≤104
• 1≤L≤R≤10181≤L≤R≤1018

Subtasks

• Subtask 11 (100100 points): Original constraints

Yet another SOD problem solution codechef

 

5
139 141
100 1235
1000 2537
998244353 1000000007
27182818284 31415926535897

Sample Output 1 

1
378
512
585218
10462914572538

Explanation

Test case 1: The numbers are 139139, 140140 and 141141. Their sum of digits is 1313, 55 and 66 respectively. So, only 141141 is the number that has its sum of digits divisible by 33.

• For Solution

  Click Here!