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

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!