답안 #99743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99743 2019-03-06T15:06:11 Z nandonathaniel Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
4 ms 568 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL memo[20][11][11][2][2][2];

string s[2];

LL DP(LL digit_ke,LL last1,LL last2,LL flag,LL kata,LL tzero){    
    if(digit_ke>=s[kata].length())return 1;
    if(memo[digit_ke][last1][last2][flag][kata][tzero]!=-1)return memo[digit_ke][last1][last2][flag][kata][tzero];
    LL ans=0;
    if(flag==1){
		if(tzero==1){
			if(s[kata][digit_ke]=='0')ans+=DP(digit_ke+1,10,last1,1,kata,1);
			else ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
		else{
			if((LL)(s[kata][digit_ke]-'0')!=last1 && (LL)(s[kata][digit_ke]-'0')!=last2)ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
        for(LL dig=0;dig<(LL)(s[kata][digit_ke]-'0');dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }
    else{
        for(LL dig=0;dig<=9;dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }

    return memo[digit_ke][last1][last2][flag][kata][tzero]=ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	memset(memo,-1,sizeof(memo));
	LL L,res2;
	cin >> L >> s[1];
	LL res1=DP(0,10,10,1,1,1);
	if(L==0)res2=0;
	else{
		L--;
		s[0]=to_string(L);
		res2=DP(0,10,10,1,0,1);
	}
	//cout << res1 << " " << res2  << endl;
	cout << res1-res2 << endl;
	return 0;
}

Compilation message

numbers.cpp: In function 'LL DP(LL, LL, LL, LL, LL, LL)':
numbers.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(digit_ke>=s[kata].length())return 1;
        ~~~~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 484 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 432 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 3 ms 512 KB Output is correct
29 Correct 3 ms 512 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 3 ms 512 KB Output is correct
34 Correct 3 ms 512 KB Output is correct
35 Correct 3 ms 512 KB Output is correct
36 Correct 3 ms 512 KB Output is correct
37 Correct 3 ms 512 KB Output is correct
38 Correct 2 ms 512 KB Output is correct
39 Correct 2 ms 512 KB Output is correct
40 Correct 3 ms 512 KB Output is correct
41 Correct 2 ms 508 KB Output is correct
42 Correct 3 ms 512 KB Output is correct
43 Correct 3 ms 568 KB Output is correct
44 Correct 3 ms 512 KB Output is correct
45 Correct 2 ms 512 KB Output is correct