Submission #96950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96950	2019-02-12T20:36:47 Z	dalgerok	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	7 ms	1152 KB

numbers

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


long long ans;
string s;
long long dp[20][10][10][20][2];

long long rec(int pos, int d1, int d2, int curpos, bool pref){
    ///cout << (int)s.size() << " " << pos << " " << d1 << " " << d2 << " " << curpos << " " << pref << " " << dp[pos][d1][d2][curpos][pref] << "\n";
    if(pos >= (int)s.size()){
        return 1;
    }
    if(dp[pos][d1][d2][curpos][pref] != -1){
        return dp[pos][d1][d2][curpos][pref];
    }
    long long &cur = dp[pos][d1][d2][curpos][pref];
    cur = 0;
    int bound = (pref ? s[pos] - '0' : 9);
    for(int i = 0; i <= bound; i++){
        if(curpos == 0){
            if(i){
                cur += rec(pos + 1, i, 0, 1, (pref && bound == i));
            }
            else{
                cur += rec(pos + 1, 0, 0, 0, (pref && bound == i));
            }
        }
        else if(i != d1){
            if(curpos >= 2 && i != d2){
                cur += rec(pos + 1, i, d1, curpos + 1, (pref && bound == i));
            }
            else if(curpos == 1){
                cur += rec(pos + 1, i, d1, curpos + 1, (pref && bound == i));
            }
        }
    }
    return cur;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long a, b;
    cin >> a >> b;
    if(a == 0){
        ans += 1;
    }
    else{
        a -= 1;
    }
    s = to_string(b);
    memset(dp, -1, sizeof(dp));
    ans += rec(0, 0, 0, 0, true);
    s = to_string(a);
    memset(dp, -1, sizeof(dp));
    ans -= rec(0, 0, 0, 0, true);
    cout << ans;
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1152 KB	Output is correct
2	Correct	4 ms	1024 KB	Output is correct
3	Correct	4 ms	1024 KB	Output is correct
4	Correct	2 ms	1024 KB	Output is correct
5	Correct	3 ms	1024 KB	Output is correct
6	Correct	3 ms	1024 KB	Output is correct
7	Correct	3 ms	904 KB	Output is correct
8	Correct	3 ms	896 KB	Output is correct
9	Correct	3 ms	1024 KB	Output is correct
10	Correct	2 ms	896 KB	Output is correct
11	Correct	2 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	1024 KB	Output is correct
14	Correct	3 ms	896 KB	Output is correct
15	Correct	3 ms	896 KB	Output is correct
16	Correct	3 ms	1024 KB	Output is correct
17	Correct	3 ms	1024 KB	Output is correct
18	Correct	3 ms	896 KB	Output is correct
19	Correct	4 ms	896 KB	Output is correct
20	Correct	3 ms	896 KB	Output is correct

Subtask #2

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1024 KB	Output is correct
2	Correct	5 ms	896 KB	Output is correct
3	Correct	5 ms	896 KB	Output is correct
4	Correct	6 ms	896 KB	Output is correct
5	Correct	3 ms	896 KB	Output is correct
6	Correct	3 ms	896 KB	Output is correct
7	Correct	4 ms	1024 KB	Output is correct
8	Correct	3 ms	896 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	3 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	1024 KB	Output is correct
13	Correct	3 ms	1024 KB	Output is correct
14	Correct	4 ms	1024 KB	Output is correct
15	Correct	3 ms	1024 KB	Output is correct
16	Correct	6 ms	1152 KB	Output is correct
17	Correct	4 ms	896 KB	Output is correct
18	Correct	6 ms	1024 KB	Output is correct
19	Correct	5 ms	1024 KB	Output is correct
20	Correct	5 ms	1024 KB	Output is correct
21	Correct	5 ms	1024 KB	Output is correct
22	Correct	5 ms	1024 KB	Output is correct
23	Correct	6 ms	1024 KB	Output is correct
24	Correct	6 ms	896 KB	Output is correct
25	Correct	6 ms	896 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	5 ms	1024 KB	Output is correct
28	Correct	4 ms	896 KB	Output is correct
29	Correct	5 ms	896 KB	Output is correct
30	Correct	4 ms	896 KB	Output is correct
31	Correct	5 ms	1024 KB	Output is correct
32	Correct	5 ms	896 KB	Output is correct
33	Correct	7 ms	896 KB	Output is correct
34	Correct	6 ms	1024 KB	Output is correct
35	Correct	5 ms	896 KB	Output is correct
36	Correct	5 ms	896 KB	Output is correct
37	Correct	4 ms	1024 KB	Output is correct
38	Correct	4 ms	896 KB	Output is correct
39	Correct	6 ms	1024 KB	Output is correct
40	Correct	5 ms	1024 KB	Output is correct
41	Correct	5 ms	896 KB	Output is correct
42	Correct	4 ms	896 KB	Output is correct
43	Correct	5 ms	1024 KB	Output is correct
44	Correct	6 ms	896 KB	Output is correct
45	Correct	4 ms	896 KB	Output is correct