import java.util.*;
import java.io.*;
public class numbers {
private static String a, b;
private static Long[][][][][] dp;
private static long palRange(int i, int lst1, int lst2, int blo, int bhi) {
if (dp[i][lst1+1][lst2+1][blo][bhi] != null) return dp[i][lst1+1][lst2+1][blo][bhi];
if (i == a.length()) return dp[i][lst1+1][lst2+1][blo][bhi] = 1L;
long ret = 0;
for (int k = -1; k <= 9; k++) {
if (k == -1 && lst1 == -1 && a.charAt(i) == '#') ret += palRange(i+1, k, lst1, 1, 0);
else if (k == -1) continue;
if (k == 0 && a.charAt(i) == '#' || k == lst1 || k == lst2) continue;
if (blo == 1 && k < (a.charAt(i) - '0') || bhi == 1 && k > (b.charAt(i) - '0')) continue;
ret += palRange(i+1, k, lst1, blo == 1 && k == (a.charAt(i) - '0') ? 1 : 0,
bhi == 1 && k == (b.charAt(i) - '0') ? 1 : 0);
}
return dp[i][lst1+1][lst2+1][blo][bhi] = ret;
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
StringTokenizer ST = new StringTokenizer(in.readLine());
a = ST.nextToken();
b = ST.nextToken();
while (a.length() < b.length()) a = "#" + a;
dp = new Long[a.length()+1][11][11][2][2];
long ans = palRange(0, -1, -1, 1, 1);
System.out.println(ans);
in.close();
out.close();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
10352 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
10372 KB |
Output isn't correct |
| 3 |
Correct |
82 ms |
10616 KB |
Output is correct |
| 4 |
Incorrect |
82 ms |
10572 KB |
Output isn't correct |
| 5 |
Correct |
85 ms |
10488 KB |
Output is correct |
| 6 |
Correct |
81 ms |
10596 KB |
Output is correct |
| 7 |
Correct |
76 ms |
10224 KB |
Output is correct |
| 8 |
Incorrect |
78 ms |
10232 KB |
Output isn't correct |
| 9 |
Correct |
76 ms |
10416 KB |
Output is correct |
| 10 |
Correct |
77 ms |
10620 KB |
Output is correct |
| 11 |
Correct |
78 ms |
10252 KB |
Output is correct |
| 12 |
Correct |
76 ms |
10492 KB |
Output is correct |
| 13 |
Correct |
81 ms |
10436 KB |
Output is correct |
| 14 |
Incorrect |
79 ms |
10856 KB |
Output isn't correct |
| 15 |
Incorrect |
83 ms |
10776 KB |
Output isn't correct |
| 16 |
Correct |
82 ms |
10484 KB |
Output is correct |
| 17 |
Correct |
80 ms |
11000 KB |
Output is correct |
| 18 |
Correct |
79 ms |
10360 KB |
Output is correct |
| 19 |
Correct |
85 ms |
10868 KB |
Output is correct |
| 20 |
Incorrect |
89 ms |
10716 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
10896 KB |
Output is correct |
| 2 |
Correct |
82 ms |
11004 KB |
Output is correct |
| 3 |
Correct |
89 ms |
11000 KB |
Output is correct |
| 4 |
Correct |
94 ms |
10848 KB |
Output is correct |
| 5 |
Incorrect |
81 ms |
10992 KB |
Output isn't correct |
| 6 |
Correct |
83 ms |
10876 KB |
Output is correct |
| 7 |
Incorrect |
80 ms |
11056 KB |
Output isn't correct |
| 8 |
Incorrect |
81 ms |
10588 KB |
Output isn't correct |
| 9 |
Incorrect |
86 ms |
10976 KB |
Output isn't correct |
| 10 |
Incorrect |
85 ms |
11100 KB |
Output isn't correct |
| 11 |
Correct |
84 ms |
10868 KB |
Output is correct |
| 12 |
Incorrect |
85 ms |
10792 KB |
Output isn't correct |
| 13 |
Incorrect |
84 ms |
10740 KB |
Output isn't correct |
| 14 |
Incorrect |
79 ms |
10740 KB |
Output isn't correct |
| 15 |
Incorrect |
82 ms |
10928 KB |
Output isn't correct |
| 16 |
Correct |
86 ms |
10900 KB |
Output is correct |
| 17 |
Correct |
77 ms |
10616 KB |
Output is correct |
| 18 |
Correct |
83 ms |
10648 KB |
Output is correct |
| 19 |
Correct |
78 ms |
10732 KB |
Output is correct |
| 20 |
Correct |
86 ms |
10512 KB |
Output is correct |
| 21 |
Correct |
91 ms |
11000 KB |
Output is correct |
| 22 |
Correct |
80 ms |
10616 KB |
Output is correct |
| 23 |
Correct |
90 ms |
11032 KB |
Output is correct |
| 24 |
Correct |
78 ms |
10744 KB |
Output is correct |
| 25 |
Correct |
88 ms |
10872 KB |
Output is correct |
| 26 |
Correct |
91 ms |
11016 KB |
Output is correct |
| 27 |
Correct |
85 ms |
11020 KB |
Output is correct |
| 28 |
Correct |
95 ms |
10888 KB |
Output is correct |
| 29 |
Correct |
82 ms |
10616 KB |
Output is correct |
| 30 |
Correct |
76 ms |
10480 KB |
Output is correct |
| 31 |
Correct |
89 ms |
11460 KB |
Output is correct |
| 32 |
Correct |
78 ms |
10616 KB |
Output is correct |
| 33 |
Correct |
88 ms |
11600 KB |
Output is correct |
| 34 |
Correct |
77 ms |
10488 KB |
Output is correct |
| 35 |
Correct |
82 ms |
10872 KB |
Output is correct |
| 36 |
Correct |
85 ms |
10996 KB |
Output is correct |
| 37 |
Correct |
85 ms |
10800 KB |
Output is correct |
| 38 |
Correct |
88 ms |
10900 KB |
Output is correct |
| 39 |
Correct |
88 ms |
11788 KB |
Output is correct |
| 40 |
Correct |
80 ms |
10492 KB |
Output is correct |
| 41 |
Correct |
86 ms |
10868 KB |
Output is correct |
| 42 |
Correct |
79 ms |
10572 KB |
Output is correct |
| 43 |
Correct |
85 ms |
10996 KB |
Output is correct |
| 44 |
Correct |
84 ms |
10872 KB |
Output is correct |
| 45 |
Correct |
85 ms |
11128 KB |
Output is correct |
