oj.uz

답안 #446147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446147 2021-07-21T06:15:56 Z guru1603 Palindrome-Free Numbers (BOI13_numbers) Java 11
0 / 100
 186 ms 12276 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;
			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
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 160 ms 12032 KB Execution failed because the return code was nonzero
2 Runtime error 158 ms 12172 KB Execution failed because the return code was nonzero
3 Runtime error 160 ms 12016 KB Execution failed because the return code was nonzero
4 Runtime error 168 ms 11924 KB Execution failed because the return code was nonzero
5 Runtime error 166 ms 12092 KB Execution failed because the return code was nonzero
6 Runtime error 169 ms 12188 KB Execution failed because the return code was nonzero
7 Runtime error 185 ms 11852 KB Execution failed because the return code was nonzero
8 Runtime error 172 ms 12068 KB Execution failed because the return code was nonzero
9 Runtime error 156 ms 12104 KB Execution failed because the return code was nonzero
10 Runtime error 174 ms 12024 KB Execution failed because the return code was nonzero
11 Runtime error 156 ms 12124 KB Execution failed because the return code was nonzero
12 Runtime error 177 ms 11808 KB Execution failed because the return code was nonzero
13 Runtime error 159 ms 12068 KB Execution failed because the return code was nonzero
14 Runtime error 162 ms 12128 KB Execution failed because the return code was nonzero
15 Runtime error 164 ms 11876 KB Execution failed because the return code was nonzero
16 Runtime error 166 ms 11972 KB Execution failed because the return code was nonzero
17 Runtime error 163 ms 11844 KB Execution failed because the return code was nonzero
18 Runtime error 167 ms 11908 KB Execution failed because the return code was nonzero
19 Runtime error 170 ms 12100 KB Execution failed because the return code was nonzero
20 Runtime error 174 ms 12020 KB Execution failed because the return code was nonzero

Subtask #2
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 171 ms 11988 KB Execution failed because the return code was nonzero
2 Runtime error 162 ms 12068 KB Execution failed because the return code was nonzero
3 Runtime error 179 ms 12024 KB Execution failed because the return code was nonzero
4 Runtime error 166 ms 11912 KB Execution failed because the return code was nonzero
5 Runtime error 160 ms 12116 KB Execution failed because the return code was nonzero
6 Runtime error 175 ms 11908 KB Execution failed because the return code was nonzero
7 Runtime error 174 ms 11964 KB Execution failed because the return code was nonzero
8 Runtime error 176 ms 11972 KB Execution failed because the return code was nonzero
9 Runtime error 158 ms 12044 KB Execution failed because the return code was nonzero
10 Runtime error 164 ms 12244 KB Execution failed because the return code was nonzero
11 Runtime error 186 ms 12000 KB Execution failed because the return code was nonzero
12 Runtime error 159 ms 12252 KB Execution failed because the return code was nonzero
13 Runtime error 159 ms 12276 KB Execution failed because the return code was nonzero
14 Runtime error 166 ms 11932 KB Execution failed because the return code was nonzero
15 Runtime error 182 ms 11984 KB Execution failed because the return code was nonzero
16 Runtime error 162 ms 12116 KB Execution failed because the return code was nonzero
17 Runtime error 160 ms 11976 KB Execution failed because the return code was nonzero
18 Runtime error 162 ms 12048 KB Execution failed because the return code was nonzero
19 Runtime error 162 ms 12024 KB Execution failed because the return code was nonzero
20 Runtime error 159 ms 12136 KB Execution failed because the return code was nonzero
21 Runtime error 161 ms 11888 KB Execution failed because the return code was nonzero
22 Runtime error 183 ms 11988 KB Execution failed because the return code was nonzero
23 Runtime error 176 ms 11912 KB Execution failed because the return code was nonzero
24 Runtime error 160 ms 11956 KB Execution failed because the return code was nonzero
25 Runtime error 172 ms 12048 KB Execution failed because the return code was nonzero
26 Runtime error 167 ms 12028 KB Execution failed because the return code was nonzero
27 Runtime error 170 ms 11904 KB Execution failed because the return code was nonzero
28 Runtime error 175 ms 11900 KB Execution failed because the return code was nonzero
29 Runtime error 160 ms 12120 KB Execution failed because the return code was nonzero
30 Runtime error 176 ms 12024 KB Execution failed because the return code was nonzero
31 Runtime error 166 ms 12112 KB Execution failed because the return code was nonzero
32 Runtime error 158 ms 12048 KB Execution failed because the return code was nonzero
33 Runtime error 168 ms 12000 KB Execution failed because the return code was nonzero
34 Runtime error 171 ms 12076 KB Execution failed because the return code was nonzero
35 Runtime error 160 ms 12164 KB Execution failed because the return code was nonzero
36 Runtime error 176 ms 11988 KB Execution failed because the return code was nonzero
37 Runtime error 183 ms 11864 KB Execution failed because the return code was nonzero
38 Runtime error 163 ms 12272 KB Execution failed because the return code was nonzero
39 Runtime error 175 ms 11952 KB Execution failed because the return code was nonzero
40 Runtime error 164 ms 11924 KB Execution failed because the return code was nonzero
41 Runtime error 166 ms 12012 KB Execution failed because the return code was nonzero
42 Runtime error 161 ms 12124 KB Execution failed because the return code was nonzero
43 Runtime error 161 ms 12136 KB Execution failed because the return code was nonzero
44 Runtime error 164 ms 12176 KB Execution failed because the return code was nonzero
45 Runtime error 161 ms 12116 KB Execution failed because the return code was nonzero