제출 #446149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446149		guru1603	Palindrome-Free Numbers (BOI13_numbers)	Java	100 / 100	165 ms	11896 KiB

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 / 25
• Subtask 2: 75 / 75