| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 392525 | 2021-04-21T09:42:56 Z | piyushsethia17 | Palindrome-Free Numbers (BOI13_numbers) | Java 11 | 186 ms | 12492 KB |
import java.io.*;
import java.util.*;
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());
}
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 162 ms | 12492 KB | Execution failed because the return code was nonzero |
| 2 | Runtime error | 172 ms | 12108 KB | Execution failed because the return code was nonzero |
| 3 | Runtime error | 171 ms | 11880 KB | Execution failed because the return code was nonzero |
| 4 | Runtime error | 167 ms | 12340 KB | Execution failed because the return code was nonzero |
| 5 | Runtime error | 161 ms | 12088 KB | Execution failed because the return code was nonzero |
| 6 | Runtime error | 163 ms | 12164 KB | Execution failed because the return code was nonzero |
| 7 | Runtime error | 160 ms | 12180 KB | Execution failed because the return code was nonzero |
| 8 | Runtime error | 163 ms | 12472 KB | Execution failed because the return code was nonzero |
| 9 | Runtime error | 166 ms | 12308 KB | Execution failed because the return code was nonzero |
| 10 | Runtime error | 165 ms | 12108 KB | Execution failed because the return code was nonzero |
| 11 | Runtime error | 168 ms | 12244 KB | Execution failed because the return code was nonzero |
| 12 | Runtime error | 182 ms | 12244 KB | Execution failed because the return code was nonzero |
| 13 | Runtime error | 161 ms | 12304 KB | Execution failed because the return code was nonzero |
| 14 | Runtime error | 162 ms | 12348 KB | Execution failed because the return code was nonzero |
| 15 | Runtime error | 164 ms | 12228 KB | Execution failed because the return code was nonzero |
| 16 | Runtime error | 167 ms | 12200 KB | Execution failed because the return code was nonzero |
| 17 | Runtime error | 160 ms | 12252 KB | Execution failed because the return code was nonzero |
| 18 | Runtime error | 161 ms | 12340 KB | Execution failed because the return code was nonzero |
| 19 | Runtime error | 166 ms | 12360 KB | Execution failed because the return code was nonzero |
| 20 | Runtime error | 159 ms | 12308 KB | Execution failed because the return code was nonzero |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 167 ms | 12100 KB | Execution failed because the return code was nonzero |
| 2 | Runtime error | 181 ms | 12180 KB | Execution failed because the return code was nonzero |
| 3 | Runtime error | 167 ms | 12268 KB | Execution failed because the return code was nonzero |
| 4 | Runtime error | 160 ms | 12268 KB | Execution failed because the return code was nonzero |
| 5 | Runtime error | 162 ms | 12284 KB | Execution failed because the return code was nonzero |
| 6 | Runtime error | 159 ms | 12316 KB | Execution failed because the return code was nonzero |
| 7 | Runtime error | 163 ms | 12440 KB | Execution failed because the return code was nonzero |
| 8 | Runtime error | 160 ms | 12324 KB | Execution failed because the return code was nonzero |
| 9 | Runtime error | 161 ms | 12264 KB | Execution failed because the return code was nonzero |
| 10 | Runtime error | 175 ms | 12372 KB | Execution failed because the return code was nonzero |
| 11 | Runtime error | 159 ms | 12376 KB | Execution failed because the return code was nonzero |
| 12 | Runtime error | 160 ms | 12168 KB | Execution failed because the return code was nonzero |
| 13 | Runtime error | 178 ms | 12424 KB | Execution failed because the return code was nonzero |
| 14 | Runtime error | 186 ms | 12032 KB | Execution failed because the return code was nonzero |
| 15 | Runtime error | 163 ms | 12328 KB | Execution failed because the return code was nonzero |
| 16 | Runtime error | 159 ms | 12068 KB | Execution failed because the return code was nonzero |
| 17 | Runtime error | 161 ms | 12404 KB | Execution failed because the return code was nonzero |
| 18 | Runtime error | 165 ms | 12364 KB | Execution failed because the return code was nonzero |
| 19 | Runtime error | 159 ms | 12280 KB | Execution failed because the return code was nonzero |
| 20 | Runtime error | 163 ms | 12156 KB | Execution failed because the return code was nonzero |
| 21 | Runtime error | 159 ms | 12216 KB | Execution failed because the return code was nonzero |
| 22 | Runtime error | 162 ms | 12224 KB | Execution failed because the return code was nonzero |
| 23 | Runtime error | 163 ms | 12408 KB | Execution failed because the return code was nonzero |
| 24 | Runtime error | 169 ms | 12180 KB | Execution failed because the return code was nonzero |
| 25 | Runtime error | 174 ms | 11988 KB | Execution failed because the return code was nonzero |
| 26 | Runtime error | 164 ms | 12428 KB | Execution failed because the return code was nonzero |
| 27 | Runtime error | 163 ms | 12416 KB | Execution failed because the return code was nonzero |
| 28 | Runtime error | 160 ms | 12272 KB | Execution failed because the return code was nonzero |
| 29 | Runtime error | 161 ms | 12100 KB | Execution failed because the return code was nonzero |
| 30 | Runtime error | 160 ms | 12072 KB | Execution failed because the return code was nonzero |
| 31 | Runtime error | 162 ms | 12212 KB | Execution failed because the return code was nonzero |
| 32 | Runtime error | 162 ms | 12456 KB | Execution failed because the return code was nonzero |
| 33 | Runtime error | 163 ms | 12416 KB | Execution failed because the return code was nonzero |
| 34 | Runtime error | 162 ms | 12068 KB | Execution failed because the return code was nonzero |
| 35 | Runtime error | 173 ms | 12244 KB | Execution failed because the return code was nonzero |
| 36 | Runtime error | 182 ms | 12248 KB | Execution failed because the return code was nonzero |
| 37 | Runtime error | 180 ms | 12384 KB | Execution failed because the return code was nonzero |
| 38 | Runtime error | 160 ms | 12284 KB | Execution failed because the return code was nonzero |
| 39 | Runtime error | 160 ms | 12256 KB | Execution failed because the return code was nonzero |
| 40 | Runtime error | 166 ms | 12140 KB | Execution failed because the return code was nonzero |
| 41 | Runtime error | 164 ms | 12492 KB | Execution failed because the return code was nonzero |
| 42 | Runtime error | 164 ms | 12124 KB | Execution failed because the return code was nonzero |
| 43 | Runtime error | 169 ms | 12480 KB | Execution failed because the return code was nonzero |
| 44 | Runtime error | 167 ms | 12104 KB | Execution failed because the return code was nonzero |
| 45 | Runtime error | 166 ms | 12140 KB | Execution failed because the return code was nonzero |