oj.uz

Submission #446146

# Submission time Handle Problem Language Result Execution time Memory
446146 2021-07-21T06:05:05 Z guru1603 Palindrome-Free Numbers (BOI13_numbers) Java 11
0 / 100
 224 ms 12348 KB 
/*Everything is Hard 
 * Before Easy 
 * Jai Mata Dii 
 */ 
 
import java.util.*;
import java.io.*; 
  
class Main { 
	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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 12316 KB Execution failed because the return code was nonzero
2 Runtime error 173 ms 11844 KB Execution failed because the return code was nonzero
3 Runtime error 187 ms 11768 KB Execution failed because the return code was nonzero
4 Runtime error 170 ms 11944 KB Execution failed because the return code was nonzero
5 Runtime error 224 ms 11892 KB Execution failed because the return code was nonzero
6 Runtime error 166 ms 11872 KB Execution failed because the return code was nonzero
7 Runtime error 173 ms 11992 KB Execution failed because the return code was nonzero
8 Runtime error 181 ms 11996 KB Execution failed because the return code was nonzero
9 Runtime error 177 ms 12016 KB Execution failed because the return code was nonzero
10 Runtime error 184 ms 11884 KB Execution failed because the return code was nonzero
11 Runtime error 191 ms 12036 KB Execution failed because the return code was nonzero
12 Runtime error 175 ms 11932 KB Execution failed because the return code was nonzero
13 Runtime error 160 ms 12016 KB Execution failed because the return code was nonzero
14 Runtime error 165 ms 12072 KB Execution failed because the return code was nonzero
15 Runtime error 163 ms 12036 KB Execution failed because the return code was nonzero
16 Runtime error 163 ms 11892 KB Execution failed because the return code was nonzero
17 Runtime error 164 ms 12160 KB Execution failed because the return code was nonzero
18 Runtime error 164 ms 12144 KB Execution failed because the return code was nonzero
19 Runtime error 160 ms 12232 KB Execution failed because the return code was nonzero
20 Runtime error 168 ms 11832 KB Execution failed because the return code was nonzero

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 12236 KB Execution failed because the return code was nonzero
2 Runtime error 167 ms 11872 KB Execution failed because the return code was nonzero
3 Runtime error 180 ms 12180 KB Execution failed because the return code was nonzero
4 Runtime error 178 ms 12224 KB Execution failed because the return code was nonzero
5 Runtime error 164 ms 12120 KB Execution failed because the return code was nonzero
6 Runtime error 184 ms 11924 KB Execution failed because the return code was nonzero
7 Runtime error 187 ms 11940 KB Execution failed because the return code was nonzero
8 Runtime error 180 ms 12048 KB Execution failed because the return code was nonzero
9 Runtime error 178 ms 11976 KB Execution failed because the return code was nonzero
10 Runtime error 176 ms 12080 KB Execution failed because the return code was nonzero
11 Runtime error 169 ms 12012 KB Execution failed because the return code was nonzero
12 Runtime error 172 ms 12152 KB Execution failed because the return code was nonzero
13 Runtime error 161 ms 12300 KB Execution failed because the return code was nonzero
14 Runtime error 160 ms 12120 KB Execution failed because the return code was nonzero
15 Runtime error 163 ms 12084 KB Execution failed because the return code was nonzero
16 Runtime error 162 ms 11972 KB Execution failed because the return code was nonzero
17 Runtime error 168 ms 11992 KB Execution failed because the return code was nonzero
18 Runtime error 162 ms 11792 KB Execution failed because the return code was nonzero
19 Runtime error 161 ms 12208 KB Execution failed because the return code was nonzero
20 Runtime error 161 ms 12080 KB Execution failed because the return code was nonzero
21 Runtime error 166 ms 11908 KB Execution failed because the return code was nonzero
22 Runtime error 157 ms 12016 KB Execution failed because the return code was nonzero
23 Runtime error 162 ms 12024 KB Execution failed because the return code was nonzero
24 Runtime error 158 ms 12144 KB Execution failed because the return code was nonzero
25 Runtime error 175 ms 11948 KB Execution failed because the return code was nonzero
26 Runtime error 159 ms 12136 KB Execution failed because the return code was nonzero
27 Runtime error 163 ms 12104 KB Execution failed because the return code was nonzero
28 Runtime error 179 ms 11900 KB Execution failed because the return code was nonzero
29 Runtime error 165 ms 11760 KB Execution failed because the return code was nonzero
30 Runtime error 162 ms 12196 KB Execution failed because the return code was nonzero
31 Runtime error 192 ms 11952 KB Execution failed because the return code was nonzero
32 Runtime error 164 ms 11968 KB Execution failed because the return code was nonzero
33 Runtime error 175 ms 11932 KB Execution failed because the return code was nonzero
34 Runtime error 162 ms 11880 KB Execution failed because the return code was nonzero
35 Runtime error 175 ms 12092 KB Execution failed because the return code was nonzero
36 Runtime error 157 ms 12348 KB Execution failed because the return code was nonzero
37 Runtime error 161 ms 12032 KB Execution failed because the return code was nonzero
38 Runtime error 176 ms 11892 KB Execution failed because the return code was nonzero
39 Runtime error 172 ms 11992 KB Execution failed because the return code was nonzero
40 Runtime error 162 ms 12000 KB Execution failed because the return code was nonzero
41 Runtime error 195 ms 11876 KB Execution failed because the return code was nonzero
42 Runtime error 166 ms 12012 KB Execution failed because the return code was nonzero
43 Runtime error 165 ms 12180 KB Execution failed because the return code was nonzero
44 Runtime error 163 ms 12124 KB Execution failed because the return code was nonzero
45 Runtime error 169 ms 12100 KB Execution failed because the return code was nonzero