| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 392524 | 2021-04-21T09:42:27 Z | piyushsethia17 | Palindrome-Free Numbers (BOI13_numbers) | Java 11 | 0 ms | 0 KB |
import java.io.*;
import java.util.*;
public class Main {
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 Main().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());
}
}