import java.io.*;
import java.util.*;
public class numbers {
private void solve()throws Exception {
long a = nextLong();
long b = nextLong();
out.println(solve(b)-(a==0?0:solve(a-1)));
}
long solve(long a) {
String s = Long.toString(a);
int len = s.length();
int dig[] = new int[len+1];
for(int i=1;i<=len;i++)
dig[i] = s.charAt(i-1)-'0';
// dp[i][l][ll][cmp] is the number of palindrome free integers of length i
// such that the last dig is l and second last is ll
// and cmp is 0 if integer < a, 1 if integer == a, 2 if integer > a
long dp[][][][] = new long[len+1][10][10][3];
long ret = 0;
// for length 1 and 2
for(int i=0;i<=99 && i<=a;i++)
if(i==0 || i%10 != i/10)
ret++;
for(int i=3;i<=len;i++) {
for(int l=0;l<=9;l++) {
for(int ll=0;ll<=9;ll++) {
for(int lll=0;lll<=9;lll++) {
if(l!=lll && l!=ll && ll!=lll) {
if(i==3) {
if(lll==0)
continue;
int diff = 100*(lll-dig[1]) + 10*(ll-dig[2]) + (l-dig[3]);
dp[i][l][ll][0] += diff<0?1:0;
dp[i][l][ll][1] += diff==0?1:0;
dp[i][l][ll][2] += diff>0?1:0;
} else {
dp[i][l][ll][0] += dp[i - 1][ll][lll][0] + (l < dig[i] ? dp[i - 1][ll][lll][1] : 0);
dp[i][l][ll][1] += l == dig[i] ? dp[i - 1][ll][lll][1] : 0;
dp[i][l][ll][2] += dp[i - 1][ll][lll][2] + (l > dig[i] ? dp[i - 1][ll][lll][1] : 0);
}
}
}
if(i<len)
ret += dp[i][l][ll][0] + dp[i][l][ll][1] + dp[i][l][ll][2];
else
ret += dp[i][l][ll][0] + dp[i][l][ll][1];
}
}
}
return ret;
}
///////////////////////////////////////////////////////////
public void run()throws Exception {
br=new BufferedReader(new InputStreamReader(System.in));
st=null;
out=new PrintWriter(System.out);
try{
solve();
} catch(Exception e){e.printStackTrace();}
finally{
br.close();
out.close();
}
}
public static void main(String args[])throws Exception{
new numbers().run();
}
BufferedReader br;
StringTokenizer st;
PrintWriter out;
String nextToken()throws Exception{
while(st==null || !st.hasMoreTokens())
st=new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine()throws Exception{
return br.readLine();
}
int nextInt()throws Exception{
return Integer.parseInt(nextToken());
}
long nextLong()throws Exception{
return Long.parseLong(nextToken());
}
double nextDouble()throws Exception{
return Double.parseDouble(nextToken());
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
75 ms |
8460 KB |
Output is correct |
| 3 |
Correct |
140 ms |
12144 KB |
Output is correct |
| 4 |
Correct |
73 ms |
8636 KB |
Output is correct |
| 5 |
Correct |
75 ms |
8372 KB |
Output is correct |
| 6 |
Correct |
71 ms |
8452 KB |
Output is correct |
| 7 |
Correct |
72 ms |
8560 KB |
Output is correct |
| 8 |
Correct |
71 ms |
8468 KB |
Output is correct |
| 9 |
Correct |
70 ms |
8304 KB |
Output is correct |
| 10 |
Correct |
71 ms |
8336 KB |
Output is correct |
| 11 |
Correct |
72 ms |
8720 KB |
Output is correct |
| 12 |
Correct |
75 ms |
8600 KB |
Output is correct |
| 13 |
Correct |
74 ms |
8376 KB |
Output is correct |
| 14 |
Correct |
71 ms |
8696 KB |
Output is correct |
| 15 |
Correct |
73 ms |
8348 KB |
Output is correct |
| 16 |
Correct |
75 ms |
8640 KB |
Output is correct |
| 17 |
Correct |
72 ms |
8564 KB |
Output is correct |
| 18 |
Correct |
82 ms |
8140 KB |
Output is correct |
| 19 |
Correct |
155 ms |
11920 KB |
Output is correct |
| 20 |
Correct |
71 ms |
8472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
8580 KB |
Output is correct |
| 2 |
Correct |
107 ms |
11316 KB |
Output is correct |
| 3 |
Correct |
113 ms |
11144 KB |
Output is correct |
| 4 |
Correct |
109 ms |
11428 KB |
Output is correct |
| 5 |
Correct |
73 ms |
8544 KB |
Output is correct |
| 6 |
Correct |
75 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
72 ms |
8480 KB |
Output is correct |
| 8 |
Correct |
71 ms |
8392 KB |
Output is correct |
| 9 |
Correct |
74 ms |
8404 KB |
Output is correct |
| 10 |
Correct |
79 ms |
8416 KB |
Output is correct |
| 11 |
Correct |
79 ms |
8472 KB |
Output is correct |
| 12 |
Correct |
76 ms |
8328 KB |
Output is correct |
| 13 |
Correct |
75 ms |
8512 KB |
Output is correct |
| 14 |
Correct |
74 ms |
8636 KB |
Output is correct |
| 15 |
Correct |
74 ms |
8344 KB |
Output is correct |
| 16 |
Correct |
110 ms |
11492 KB |
Output is correct |
| 17 |
Correct |
109 ms |
11396 KB |
Output is correct |
| 18 |
Correct |
124 ms |
11360 KB |
Output is correct |
| 19 |
Correct |
110 ms |
11472 KB |
Output is correct |
| 20 |
Correct |
114 ms |
11256 KB |
Output is correct |
| 21 |
Correct |
127 ms |
11208 KB |
Output is correct |
| 22 |
Correct |
113 ms |
11672 KB |
Output is correct |
| 23 |
Correct |
112 ms |
11356 KB |
Output is correct |
| 24 |
Correct |
109 ms |
11460 KB |
Output is correct |
| 25 |
Correct |
111 ms |
11508 KB |
Output is correct |
| 26 |
Correct |
108 ms |
11360 KB |
Output is correct |
| 27 |
Correct |
107 ms |
11400 KB |
Output is correct |
| 28 |
Correct |
126 ms |
11392 KB |
Output is correct |
| 29 |
Correct |
116 ms |
11400 KB |
Output is correct |
| 30 |
Correct |
108 ms |
11276 KB |
Output is correct |
| 31 |
Correct |
109 ms |
11268 KB |
Output is correct |
| 32 |
Correct |
108 ms |
11284 KB |
Output is correct |
| 33 |
Correct |
140 ms |
12024 KB |
Output is correct |
| 34 |
Correct |
112 ms |
11260 KB |
Output is correct |
| 35 |
Correct |
109 ms |
11332 KB |
Output is correct |
| 36 |
Correct |
109 ms |
11276 KB |
Output is correct |
| 37 |
Correct |
118 ms |
11592 KB |
Output is correct |
| 38 |
Correct |
115 ms |
11204 KB |
Output is correct |
| 39 |
Correct |
111 ms |
11256 KB |
Output is correct |
| 40 |
Correct |
116 ms |
11384 KB |
Output is correct |
| 41 |
Correct |
112 ms |
11392 KB |
Output is correct |
| 42 |
Correct |
114 ms |
11200 KB |
Output is correct |
| 43 |
Correct |
111 ms |
11228 KB |
Output is correct |
| 44 |
Correct |
111 ms |
11072 KB |
Output is correct |
| 45 |
Correct |
112 ms |
11408 KB |
Output is correct |
