fork download
copy 
  1. /*
  2.     created by: nitin23329
  3.     on Date: 09/06/21
  4. */
  5. import java.io.*;
  6. import java.util.*;
  7. /*****************************************WRITING CODE STARTS HERE******************************************/
  8.  class CodeForces {
  9.  
  10.     static long [][][] dp = new long[18][140][2];
  11.     private static void solve() {
  12.        long l = sc.nextLong();
  13.        long r = sc.nextLong();
  14.        long ans = 0;
  15.        if(r>0)ans += helper(r);
  16.        if(l-1>0) ans -= helper(l-1);
  17.        out.println(ans);
  18.     }
  19.     private static long helper(long n){
  20.         int digitLength = countDigitBase10(n);
  21.         int[] digitArray = new int[digitLength];
  22.         for(int i = digitLength-1;i>=0;i--){
  23.             digitArray[i] = (int)(n % 10);
  24.             n/=10;
  25.         }
  26.         for(int i=0;i<dp.length;i++)
  27.             for(int j=0;j<dp[0].length;j++)
  28.                 dp[i][j] = new long[]{-1,-1};
  29.  
  30.         return memo(0,0,1,digitArray);
  31.  
  32.     }
  33.     private static long memo(int i,int currDigitSum,int isBounded,int[] digitArray){
  34.         if(i==digitArray.length)return currDigitSum;
  35.         if(dp[i][currDigitSum][isBounded]!=-1)return dp[i][currDigitSum][isBounded];
  36.         long ans = 0;
  37.         if(isBounded==1){
  38.             for(int digit = 0;digit <= digitArray[i];digit++){
  39.                 ans += memo(i+1,currDigitSum + digit,digit == digitArray[i]?1:0,digitArray);
  40.             }
  41.         }else {
  42.             for(int digit = 0;digit <= 9;digit++){
  43.                 ans += memo(i+1,currDigitSum + digit,0,digitArray);
  44.             }
  45.         }
  46.         return dp[i][currDigitSum][isBounded] = ans;
  47.     }
  48.  
  49.     /*****************************************WRITING CODE ENDS HERE******************************************/
  50.  
  51.     public static void main(String[] args){
  52.         FIO(false);
  53.         int testCase = 1;
  54.         testCase = sc.nextInt();
  55.         while (testCase-- > 0) solve();
  56.         closeIO();
  57.     }
  58.  
  59.     static Scanner sc ;                     // FAST INPUT
  60.     static PrintWriter out;                // FAST OUTPUT
  61.     static PrintWriter debug ;             // DEBUG IN FILE : debug.txt
  62.  
  63.  
  64.     /**************************************HELPER FUNCTION STARTS HERE ************************************/
  65.  
  66.     public static int mod = (int) 1e9 + 7;
  67.     public static final int INT_MAX = Integer.MAX_VALUE;
  68.     public static final int INT_MIN = Integer.MIN_VALUE;
  69.     public static final long LONG_MAX = Long.MAX_VALUE;
  70.     public static final long LONG_MIN = Long.MIN_VALUE;
  71.     public static final double DOUBLE_MAX = Double.MAX_VALUE;
  72.     public static final double DOUBLE_MIN = Double.MIN_VALUE;
  73.     public static final String YES = "YES";
  74.     public static final String NO = "NO";
  75.  
  76.     public static void sort(int[] a, boolean isAscending) {
  77.         ArrayList<Integer> temp = new ArrayList<>();
  78.         for (int j : a) temp.add(j);
  79.         sort(temp, isAscending);
  80.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  81.     }
  82.  
  83.     public static void sort(long[] a, boolean isAscending) {
  84.         ArrayList<Long> temp = new ArrayList<>();
  85.         for (long ele : a) temp.add(ele);
  86.         sort(temp, isAscending);
  87.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  88.     }
  89.  
  90.     public static void sort(List list, boolean isAscending) {
  91.         if (isAscending)
  92.             Collections.sort(list);
  93.         else Collections.sort(list, Collections.reverseOrder());
  94.     }
  95.     // count the length of a number, time O(1)
  96.     public static int countDigitBase10(long n){
  97.         if(n == 0) return 0;
  98.         return (int)(1 + Math.log10(n));
  99.     }
  100.  
  101.     // euclidean algorithm
  102.     public static long gcd(long a, long b) {
  103.         // time O(max (loga ,logb))
  104.         long x = Math.min(a, b);
  105.         long y = Math.max(a, b);
  106.         if (y % x == 0) return x;
  107.         return gcd(y % x, x);
  108.     }
  109.  
  110.     public static long lcm(long a, long b) {
  111.         // lcm(a,b) * gcd(a,b) = a * b
  112.         return (a / gcd(a, b)) * b;
  113.     }
  114.  
  115.     public static long power(long x, long n) {
  116.         // time O(logn)
  117.         long ans = 1;
  118.         while (n > 0) {
  119.             if ((n & 1) == 1) {
  120.                 ans *= x;
  121.                 ans %= mod;
  122.                 n--;
  123.             } else {
  124.                 x *= x;
  125.                 x %= mod;
  126.                 n >>= 1;
  127.             }
  128.         }
  129.         return ans;
  130.     }
  131.  
  132.     public static long factorial(long n) {
  133.         long fact = 1L;
  134.         for (int i = 2; i <= n; i++) fact = (fact * i) % mod;
  135.         return fact;
  136.     }
  137.  
  138.     public static long firstDivisor(long n) {
  139.         if (n == 1 || n == 0) return n;
  140.         for (long i = 2; i * i <= n; i++)
  141.             if (n % i == 0) return i;
  142.         return -1;
  143.     }
  144.  
  145.     public static int ncr(int n, int r) {
  146.         // time O(n+r)
  147.         if (r > n)
  148.             return 0;
  149.         long[] inv = new long[r + 1];
  150.         inv[1] = 1;
  151.         // Getting the modular inversion
  152.         // for all the numbers
  153.         // from 2 to r with respect to m
  154.         for (int i = 2; i <= r; i++) {
  155.             inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  156.         }
  157.         int ans = 1;
  158.         // for 1/(r!) part
  159.         for (int i = 2; i <= r; i++) {
  160.             ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);
  161.         }
  162.         // for (n)*(n-1)*(n-2)*...*(n-r+1) part
  163.         for (int i = n; i >= (n - r + 1); i--) {
  164.             ans = (int) (((ans % mod) * (i % mod)) % mod);
  165.         }
  166.         return ans;
  167.     }
  168.  
  169.     public static long max3(long a, long b, long c) { return max2(max2(a, b), c);}
  170.  
  171.     public static long max2(long a, long b) {return Math.max(a, b);}
  172.  
  173.     public static long min3(long a, long b, long c) {return min2(min2(a, b), c);}
  174.  
  175.     public static long min2(long a, long b) { return Math.min(a, b); }
  176.  
  177.     public static int max3(int a, int b, int c) { return max2(max2(a, b), c); }
  178.  
  179.     public static int max2(int a, int b) { return Math.max(a, b); }
  180.  
  181.     public static int min3(int a, int b, int c) { return min2(min2(a, b), c); }
  182.  
  183.     public static int min2(int a, int b) {
  184.         return Math.min(a, b);
  185.     }
  186.  
  187.     /**************************************HELPER FUNCTION ENDS HERE ************************************/
  188.  
  189.     /*****************************************FAST INPUT STARTS HERE *************************************/
  190.  
  191.     public static void FIO(boolean isDebug){
  192.         sc = new Scanner();
  193.         out = new PrintWriter(new BufferedOutputStream(System.out));
  194.         if(isDebug){
  195.             try {
  196.                 debug = new PrintWriter(new FileOutputStream("debug.txt"));
  197.             }catch (IOException e){
  198.                 e.printStackTrace();
  199.             }
  200.         }
  201.  
  202.     }
  203.     public static void closeIO(){
  204.         sc.close();
  205.         out.flush();
  206.         out.close();
  207.         if(debug!=null){
  208.             debug.flush();
  209.             debug.close();
  210.         }
  211.     }
  212.  
  213.     private static class Scanner {
  214.         private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  215.         private StringTokenizer st = new StringTokenizer("");
  216.  
  217.         public String next() {
  218.             while (!st.hasMoreTokens())
  219.                 try {
  220.                     st = new StringTokenizer(br.readLine());
  221.                 } catch (IOException e) {
  222.                     e.printStackTrace();
  223.                 }
  224.             return st.nextToken();
  225.  
  226.         }
  227.  
  228.         public int nextInt() {
  229.             return Integer.parseInt(next());
  230.         }
  231.  
  232.         public long nextLong() {
  233.             return Long.parseLong(next());
  234.         }
  235.  
  236.         public double nextDouble() {
  237.             return Double.parseDouble(next());
  238.         }
  239.  
  240.         public int[] set_int_array(int n) {
  241.             int[] arr = new int[n];
  242.             for (int i = 0; i < n; i++) arr[i] = nextInt();
  243.             return arr;
  244.         }
  245.  
  246.         public long[] set_long_array(int n) {
  247.             long[] arr = new long[n];
  248.             for (int i = 0; i < n; i++) arr[i] = nextLong();
  249.             return arr;
  250.         }
  251.         public double[] set_double_array(int n){
  252.             double[] arr = new double[n];
  253.             for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
  254.             return arr;
  255.         }
  256.  
  257.         public int[][] set_2D_int_array(int n) {
  258.             return set2DIntArray(n, n);
  259.         }
  260.  
  261.         public int[][] set2DIntArray(int row, int col) {
  262.             int[][] arr = new int[row][col];
  263.             for (int i = 0; i < row; i++)
  264.                 for (int j = 0; j < col; j++)
  265.                     arr[i][j] = nextInt();
  266.             return arr;
  267.         }
  268.  
  269.         public long[][] set_2D_long_array(int n) {
  270.             return set2DlongArray(n, n);
  271.         }
  272.  
  273.         public long[][] set2DlongArray(int row, int col) {
  274.             long[][] arr = new long[row][col];
  275.             for (int i = 0; i < row; i++)
  276.                 for (int j = 0; j < col; j++)
  277.                     arr[i][j] = nextLong();
  278.             return arr;
  279.         }
  280.  
  281.         public char[][] set_2D_char_array(int n) {
  282.             return set2DCharArray(n, n);
  283.         }
  284.  
  285.         public char[][] set2DCharArray(int row, int col) {
  286.             char[][] ch = new char[row][col];
  287.             for (int i = 0; i < row; i++)
  288.                 ch[i] = sc.next().toCharArray();
  289.             return ch;
  290.         }
  291.  
  292.         public void close() {
  293.             try {
  294.                 br.close();
  295.             } catch (IOException e) {
  296.                 e.printStackTrace();
  297.             }
  298.         }
  299.     }
  300.     /*****************************************FAST INPUT ENDS HERE *************************************/
  301. }
Success #stdin #stdout 0.07s 51608KB
comments (?)
stdin
copy 
3
0 10
28 31
1234 56789
stdout
copy 
46
28
1128600
https://ideone.com/wmt2Ly
problem PR003004, based on SPOJ submission 28045877 (JAVA), 2021-06-12 11:52:04
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!