oj.uz

Submission #446148

# Submission time Handle Problem Language Result Execution time Memory
446148 2021-07-21T06:17:08 Z guru1603 Palindrome-Free Numbers (BOI13_numbers) Java 11
100 / 100
 119 ms 10704 KB 
/*Everything is Hard 
 * Before Easy 
 * Jai Mata Dii 
 */ 
 
import java.util.*;
import java.io.*; 
  
public class numbers { 
	static class FastReader{ BufferedReader br;StringTokenizer st;public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}String next(){while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());}catch (IOException  e){e.printStackTrace();}}return st.nextToken();}int nextInt(){ return Integer.parseInt(next());}long nextLong(){return Long.parseLong(next());}double nextDouble(){return Double.parseDouble(next());}String nextLine(){String str = ""; try{str = br.readLine(); } catch (IOException e) {e.printStackTrace();} return str; }} 
	static long mod = (long)(1e9+7); 
	// static long mod = 998244353; 
//	 static Scanner sc = new Scanner(System.in); 
	static FastReader sc = new FastReader(); 
	static PrintWriter out = new PrintWriter(System.out);
	static long dp[][][][][];
	public static void main (String[] args) { 
		int ttt = 1;
//		ttt = sc.nextInt();
		z :for(int tc=1;tc<=ttt;tc++){
			long a = sc.nextLong();
			long b = sc.nextLong();
			long left = 0, right = 0;
			
			dp = new long[2][3][10][10][20];
			if(a>0) {
				for(int i=0;i<2;i++) {
					for(int j=0;j<3;j++) {
						for(int k=0;k<10;k++) {
							for(int l=0;l<10;l++) {
								Arrays.fill(dp[i][j][k][l], -1);
							}
						}
					}
				}
				List<Integer> l = cnvrt(a-1);
				left = find_ans(l, l.size()-1, 0, 0, 0, 0);
			}
			if(b>=0) {
				for(int i=0;i<2;i++) {
					for(int j=0;j<3;j++) {
						for(int k=0;k<10;k++) {
							for(int l=0;l<10;l++) {
								Arrays.fill(dp[i][j][k][l], -1);
							}
						}
					}
				}
				List<Integer> l = cnvrt(b);
				right = find_ans(l, l.size()-1, 0, 0, 0, 0);
			}
			right -= left;
			System.out.println(right);
		}
		out.close();
	}
	private static long find_ans(List<Integer> l, int i, int is, int already_smaller, int prev, int pprev) {
		if(i<0) {
			return 1;
		}
		
		if(dp[already_smaller][is][prev][pprev][i]!=-1) return dp[already_smaller][is][prev][pprev][i];
		
		int bound = 9;
		if(already_smaller == 0) {
			bound = l.get(i);
		}
		
		long ans = 0;
		for(int j=0;j<=bound;j++) {
			if(already_smaller == 1) {
				if(is == 0) {
					if(j == 0) {
						ans += find_ans(l, i-1, 0, already_smaller, prev, pprev);
					}
					else {
						ans += find_ans(l, i-1, 1, already_smaller, j, pprev);
					}
				}
				else {
					if(is == 1) {
						if(j!=prev) {
							ans += find_ans(l, i-1, 2, already_smaller, j, prev);
						}
					}
					else {
						if(j!=prev && j!= pprev) {
							ans += find_ans(l, i-1, 2, already_smaller, j, prev);
						}
					}
				}
			}
			else {
				if(is == 0) {
					if(j == 0) {
						ans += find_ans(l, i-1, 0, j<bound?1:0, prev, pprev);
					}
					else {
						ans += find_ans(l ,i-1, 1, j<bound?1:0, j, pprev);
					}
				}
				else {
					if(is == 1) {
						if(j!=prev) ans += find_ans(l, i-1, 2, j<bound?1:0, j, prev);
					}
					else {
						if(j!=prev && j!= pprev) {
							ans += find_ans(l, i-1, 2, j<bound?1:0, j, prev);
						}
					}
				}
			}
		}
		return dp[already_smaller][is][prev][pprev][i] = ans;
	}
	private static List<Integer> cnvrt(long a) {
		ArrayList<Integer> ret = new ArrayList<>();
		while(a>0) {
			ret.add((int) (a%10));
			a /= 10;
		}
		return ret;
	}
	static long pow(long a, long b){long ret = 1;while(b>0){if(b%2 == 0){a = a*a;b /= 2;}else{ret *= a;b--;}}return ret;}
	static int gcd(long a,long b){if(b==0) return  (int)a; return gcd(b,a%b); } 
	private static void sort(int[] a) {List<Integer> k = new ArrayList<>();for(int val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);} 
	private static void ini(List<Integer>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}} 
	private static void init(List<int[]>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}} 
	private static void sort(long[] a) {List<Long> k = new ArrayList<>();for(long val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);} 
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8620 KB Output is correct
2 Correct 77 ms 8532 KB Output is correct
3 Correct 110 ms 10344 KB Output is correct
4 Correct 80 ms 8572 KB Output is correct
5 Correct 77 ms 8536 KB Output is correct
6 Correct 74 ms 8588 KB Output is correct
7 Correct 78 ms 8700 KB Output is correct
8 Correct 77 ms 8412 KB Output is correct
9 Correct 77 ms 8724 KB Output is correct
10 Correct 76 ms 8668 KB Output is correct
11 Correct 76 ms 8628 KB Output is correct
12 Correct 77 ms 8508 KB Output is correct
13 Correct 79 ms 8632 KB Output is correct
14 Correct 79 ms 8512 KB Output is correct
15 Correct 95 ms 8620 KB Output is correct
16 Correct 103 ms 10264 KB Output is correct
17 Correct 93 ms 10364 KB Output is correct
18 Correct 79 ms 8632 KB Output is correct
19 Correct 104 ms 10472 KB Output is correct
20 Correct 79 ms 8608 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10608 KB Output is correct
2 Correct 106 ms 10400 KB Output is correct
3 Correct 107 ms 10276 KB Output is correct
4 Correct 111 ms 10332 KB Output is correct
5 Correct 95 ms 10340 KB Output is correct
6 Correct 105 ms 10280 KB Output is correct
7 Correct 92 ms 10400 KB Output is correct
8 Correct 97 ms 10424 KB Output is correct
9 Correct 79 ms 8644 KB Output is correct
10 Correct 96 ms 10500 KB Output is correct
11 Correct 102 ms 10496 KB Output is correct
12 Correct 98 ms 10308 KB Output is correct
13 Correct 95 ms 10404 KB Output is correct
14 Correct 96 ms 10324 KB Output is correct
15 Correct 88 ms 9768 KB Output is correct
16 Correct 108 ms 10460 KB Output is correct
17 Correct 119 ms 10420 KB Output is correct
18 Correct 109 ms 10584 KB Output is correct
19 Correct 105 ms 10572 KB Output is correct
20 Correct 109 ms 10352 KB Output is correct
21 Correct 104 ms 10704 KB Output is correct
22 Correct 103 ms 10460 KB Output is correct
23 Correct 110 ms 10440 KB Output is correct
24 Correct 104 ms 10248 KB Output is correct
25 Correct 110 ms 10408 KB Output is correct
26 Correct 102 ms 10492 KB Output is correct
27 Correct 103 ms 10340 KB Output is correct
28 Correct 114 ms 10568 KB Output is correct
29 Correct 109 ms 10448 KB Output is correct
30 Correct 104 ms 10460 KB Output is correct
31 Correct 105 ms 10460 KB Output is correct
32 Correct 105 ms 10472 KB Output is correct
33 Correct 111 ms 10340 KB Output is correct
34 Correct 118 ms 10264 KB Output is correct
35 Correct 107 ms 10452 KB Output is correct
36 Correct 104 ms 10556 KB Output is correct
37 Correct 103 ms 10440 KB Output is correct
38 Correct 111 ms 10324 KB Output is correct
39 Correct 103 ms 10416 KB Output is correct
40 Correct 104 ms 10360 KB Output is correct
41 Correct 106 ms 10220 KB Output is correct
42 Correct 116 ms 10420 KB Output is correct
43 Correct 104 ms 10476 KB Output is correct
44 Correct 104 ms 10592 KB Output is correct
45 Correct 108 ms 10496 KB Output is correct