Submission #166583

#	Time	Username	Problem	Language	Result	Execution time	Memory
166583		GioChkhaidze	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	12 ms	504 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int cnt,a[22];
ll dp[22][11][11][2],P[22];

void Clear() {
	cnt=0;
	for (int i=0; i<=20; i++) a[i]=0;
	for (int i=0; i<=20; i++)
		for (int j1=0; j1<=9; j1++)
			for (int j2=0; j2<=9; j2++)
				for (int k=0; k<=1; k++)
					dp[i][j1][j2][k]=0;
}

void N(ll x) {
	while (x>0) { a[++cnt]=x%10; x/=10; }
	for (int i=1; i<=cnt/2; i++)
		swap(a[i],a[cnt-i+1]);
}

ll Get(ll x,int type) {
	if (x==-1) return 0;
	if (x<=9) return x+1;
	Clear();
	N(x);
	
	for (int j1=1; j1<=a[1]; j1++) 
		for (int j2=0; j2<=9; j2++) {
			if (j1==j2) continue;
			if (j1==a[1] && j2>a[2]) break;
			if (j1==a[1] && j2==a[2]) dp[2][j1][j2][1]=1;
						         else dp[2][j1][j2][0]=1;
		}
		
	for (int i=2; i<cnt; i++) 
		for (int j1=0; j1<=9; j1++) {
			for (int j2=0; j2<=9; j2++) {
				if (j1==j2) continue;
				for (int j3=0; j3<=9; j3++) {
					if (j3==j2 || j3==j1) continue;
					dp[i+1][j2][j3][0]+=dp[i][j1][j2][0];
					if (j2==a[i] && j3<a[i+1]) dp[i+1][j2][j3][0]+=dp[i][j1][j2][1];
					if (j2==a[i] && j3==a[i+1]) dp[i+1][j2][j3][1]+=dp[i][j1][j2][1];
				}
			}
		}
	
	ll res=0;
	for (int j1=0; j1<=9; j1++)
		for (int j2=0; j2<=9; j2++)
			for (int k=0; k<=1; k++)
				res+=dp[cnt][j1][j2][k];			
	
	if (!type) return res;
	return res+P[cnt-1];
}
	
main () {
	ll x=0,a,b;
	for (int i=1; i<=19; i++) {
		x=(1ll*x*10)+9;
		P[i]=P[i-1]+Get(x,0);
	}
	
	cin>>a>>b;
	cout<<Get(b,1)-Get(a-1,1)<<"\n";
}

Compilation message (stderr)

numbers.cpp:61:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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