Submission #392526

#	Time	Username	Problem	Language	Result	Execution time	Memory
392526		piyushsethia17	Palindrome-Free Numbers (BOI13_numbers)	Java	100 / 100	155 ms	12144 KiB

numbers

import java.io.*;
import java.util.*;
public class numbers {

	private void solve()throws Exception {
		long a = nextLong();
		long b = nextLong();
		out.println(solve(b)-(a==0?0:solve(a-1)));
	}

	long solve(long a) {
		
		String s = Long.toString(a);
		int len = s.length();
		int dig[] = new int[len+1];
		for(int i=1;i<=len;i++)
			dig[i] = s.charAt(i-1)-'0';

		// dp[i][l][ll][cmp] is the number of palindrome free integers of length i
		// such that the last dig is l and second last is ll
		// and cmp is 0 if integer < a, 1 if integer == a, 2 if integer > a
		long dp[][][][] = new long[len+1][10][10][3];
		long ret = 0;

		// for length 1 and 2
		for(int i=0;i<=99 && i<=a;i++)
			if(i==0 || i%10 != i/10)
				ret++;

		for(int i=3;i<=len;i++) {
			for(int l=0;l<=9;l++) {
				for(int ll=0;ll<=9;ll++) {
					for(int lll=0;lll<=9;lll++) {
						if(l!=lll && l!=ll && ll!=lll) {
							if(i==3) {
								if(lll==0)
									continue;
								int diff = 100*(lll-dig[1]) + 10*(ll-dig[2]) + (l-dig[3]);
								dp[i][l][ll][0] += diff<0?1:0;
								dp[i][l][ll][1] += diff==0?1:0;
								dp[i][l][ll][2] += diff>0?1:0;
							} else {
								dp[i][l][ll][0] += dp[i - 1][ll][lll][0] + (l < dig[i] ? dp[i - 1][ll][lll][1] : 0);
								dp[i][l][ll][1] += l == dig[i] ? dp[i - 1][ll][lll][1] : 0;
								dp[i][l][ll][2] += dp[i - 1][ll][lll][2] + (l > dig[i] ? dp[i - 1][ll][lll][1] : 0);
							}
						}
					}
					if(i<len)
						ret += dp[i][l][ll][0] + dp[i][l][ll][1] + dp[i][l][ll][2];
					else
						ret += dp[i][l][ll][0] + dp[i][l][ll][1];
				}
			}
		}
		return ret;
	}


	///////////////////////////////////////////////////////////

	public void run()throws Exception {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		try{
			solve();

		} catch(Exception e){e.printStackTrace();}
		finally{
			br.close();
			out.close();
		}

	}
	public static void main(String args[])throws Exception{
		new numbers().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws Exception{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws Exception{
		return br.readLine();
	}
	int nextInt()throws Exception{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws Exception{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws Exception{
		return Double.parseDouble(nextToken());
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75