답안 #446149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446149	2021-07-21T06:18:10 Z	guru1603	Palindrome-Free Numbers (BOI13_numbers)	Java 11	100 / 100	165 ms	11896 KB

numbers

/*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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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