oj.uz

Submission #446149

# Submission time Handle Problem Language Result Execution time Memory
446149 2021-07-21T06:18:10 Z guru1603 Palindrome-Free Numbers (BOI13_numbers) Java 11
100 / 100
 165 ms 11896 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;
			out.write(right+"\n");
		}
		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 116 ms 9656 KB Output is correct
2 Correct 117 ms 9656 KB Output is correct
3 Correct 149 ms 11632 KB Output is correct
4 Correct 120 ms 9532 KB Output is correct
5 Correct 119 ms 9704 KB Output is correct
6 Correct 116 ms 9756 KB Output is correct
7 Correct 117 ms 9660 KB Output is correct
8 Correct 115 ms 9672 KB Output is correct
9 Correct 118 ms 9580 KB Output is correct
10 Correct 115 ms 9560 KB Output is correct
11 Correct 115 ms 9664 KB Output is correct
12 Correct 118 ms 9720 KB Output is correct
13 Correct 113 ms 9720 KB Output is correct
14 Correct 115 ms 9760 KB Output is correct
15 Correct 117 ms 9700 KB Output is correct
16 Correct 133 ms 11512 KB Output is correct
17 Correct 141 ms 11676 KB Output is correct
18 Correct 118 ms 9564 KB Output is correct
19 Correct 165 ms 11704 KB Output is correct
20 Correct 118 ms 9452 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11400 KB Output is correct
2 Correct 147 ms 11648 KB Output is correct
3 Correct 144 ms 11520 KB Output is correct
4 Correct 145 ms 11432 KB Output is correct
5 Correct 138 ms 11564 KB Output is correct
6 Correct 154 ms 11324 KB Output is correct
7 Correct 131 ms 11552 KB Output is correct
8 Correct 133 ms 11536 KB Output is correct
9 Correct 115 ms 9960 KB Output is correct
10 Correct 130 ms 11644 KB Output is correct
11 Correct 144 ms 11504 KB Output is correct
12 Correct 134 ms 11448 KB Output is correct
13 Correct 135 ms 11388 KB Output is correct
14 Correct 137 ms 11472 KB Output is correct
15 Correct 127 ms 10796 KB Output is correct
16 Correct 143 ms 11704 KB Output is correct
17 Correct 140 ms 11680 KB Output is correct
18 Correct 148 ms 11556 KB Output is correct
19 Correct 144 ms 11684 KB Output is correct
20 Correct 143 ms 11400 KB Output is correct
21 Correct 142 ms 11496 KB Output is correct
22 Correct 142 ms 11652 KB Output is correct
23 Correct 145 ms 11432 KB Output is correct
24 Correct 145 ms 11388 KB Output is correct
25 Correct 146 ms 11692 KB Output is correct
26 Correct 144 ms 11676 KB Output is correct
27 Correct 143 ms 11528 KB Output is correct
28 Correct 148 ms 11456 KB Output is correct
29 Correct 147 ms 11628 KB Output is correct
30 Correct 147 ms 11768 KB Output is correct
31 Correct 147 ms 11460 KB Output is correct
32 Correct 142 ms 11672 KB Output is correct
33 Correct 145 ms 11444 KB Output is correct
34 Correct 147 ms 11552 KB Output is correct
35 Correct 145 ms 11404 KB Output is correct
36 Correct 147 ms 11740 KB Output is correct
37 Correct 144 ms 11472 KB Output is correct
38 Correct 142 ms 11600 KB Output is correct
39 Correct 148 ms 11896 KB Output is correct
40 Correct 147 ms 11544 KB Output is correct
41 Correct 148 ms 11424 KB Output is correct
42 Correct 140 ms 11724 KB Output is correct
43 Correct 144 ms 11552 KB Output is correct
44 Correct 144 ms 11752 KB Output is correct
45 Correct 143 ms 11580 KB Output is correct