제출 #979263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979263		batsukh2006	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KiB

numbers

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
int solve(int n){
	if(n<=0) return n;
	string s=to_string(n);
	int N=s.size();
	int dp[N][11][11][2]={0};
	for(int i=0; i<N; i++){
		for(int j=1; j<10; j++){
			if(i==0&&j==s[i]-'0'){
				dp[i][10][j][1]=1;
				break;
			}
			dp[i][10][j][0]=1;
		}
		if(i==0) continue;
		for(int j=0; j<10; j++){
			for(int k=0; k<10; k++){
				for(int l=0; l<=10; l++){
					for(int z=0; z<2; z++){
						if(z>0&&j>s[i]-'0') continue;
						if(j!=k&&j!=l) dp[i][k][j][z&&(j==s[i]-'0')]+=dp[i-1][l][k][z];
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0; i<=10; i++){
		for(int j=0; j<=10; j++){
			for(int z=0; z<2; z++){
				ans+=dp[N-1][i][j][z];
			}
		}
	}
	return ans;
}
void solve(){
    int a,b; cin>>a>>b;
    cout<<solve(b)-solve(a-1);
}
signed main(){
    // freopen("248.in", "r", stdin);
    // freopen("248.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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