oj.uz

Submission #40809

# Submission time Handle Problem Language Result Execution time Memory
40809 2018-02-08T07:57:56 Z someone_aa Palindrome-Free Numbers (BOI13_numbers) C++14
96.25 / 100
 2 ms 1008 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string x;
ll dp[10][10][20][2];
ll a, b;

ll recursion(int first, int second, int position, bool f) {
    if(position >= x.length()) {
        return 1;
    }
    else {
        if(dp[first][second][position][f] == -1) {
            ll sum = 0;
            if(f) {
                for(int i=0;i<=9;i++) {
                    if(i!=first && i!=second)
                        sum += recursion(second, i, position+1, f);
                }
            }
            else {
                int temp = x[position] - '0';
                for(int i=0;i<temp;i++) {
                    if(i!=first && i!=second) {
                        sum += recursion(second,i,position+1, true);
                    }
                }

                if(temp!=first && temp!=second) {
                    sum += recursion(second,temp,position+1,false);
                }
            }
            dp[first][second][position][f] = sum;
        }
        return dp[first][second][position][f];
    }
}

ll solve(ll y) {
    stringstream ss; ss << y; x = ss.str();

    memset(dp,-1,sizeof(dp));
    ll result = 1;
    int temp = x[0]-'0';

    for(int i=1;i<=temp;i++) {
        result += recursion(i,i,1,i!=temp);
    }

    for(int i=2;i<=x.length();i++) {
        for(int j=1;j<10;j++) {
            result += recursion(j,j, i, true);
        }
    }
    return result;
}

int main() {
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<"\n";
    return 0;
}

Compilation message

numbers.cpp: In function 'long long int recursion(int, int, int, bool)':
numbers.cpp:9:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(position >= x.length()) {
                 ^
numbers.cpp: In function 'long long int solve(long long int)':
numbers.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<=x.length();i++) {
                  ^

Subtask #1
21.25 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Incorrect 1 ms 612 KB Output isn't correct
5 Correct 1 ms 612 KB Output is correct
6 Correct 1 ms 612 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 1 ms 612 KB Output is correct
9 Correct 1 ms 696 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Incorrect 1 ms 760 KB Output isn't correct
15 Correct 1 ms 776 KB Output is correct
16 Correct 1 ms 780 KB Output is correct
17 Correct 1 ms 784 KB Output is correct
18 Incorrect 1 ms 792 KB Output isn't correct
19 Correct 2 ms 792 KB Output is correct
20 Correct 1 ms 796 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 800 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 2 ms 916 KB Output is correct
4 Correct 2 ms 916 KB Output is correct
5 Correct 1 ms 916 KB Output is correct
6 Correct 1 ms 916 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 1 ms 916 KB Output is correct
9 Correct 1 ms 916 KB Output is correct
10 Correct 1 ms 916 KB Output is correct
11 Correct 2 ms 916 KB Output is correct
12 Correct 1 ms 916 KB Output is correct
13 Correct 1 ms 916 KB Output is correct
14 Correct 2 ms 916 KB Output is correct
15 Correct 1 ms 916 KB Output is correct
16 Correct 2 ms 916 KB Output is correct
17 Correct 2 ms 916 KB Output is correct
18 Correct 2 ms 916 KB Output is correct
19 Correct 2 ms 916 KB Output is correct
20 Correct 2 ms 916 KB Output is correct
21 Correct 2 ms 916 KB Output is correct
22 Correct 2 ms 916 KB Output is correct
23 Correct 2 ms 916 KB Output is correct
24 Correct 2 ms 916 KB Output is correct
25 Correct 2 ms 916 KB Output is correct
26 Correct 2 ms 916 KB Output is correct
27 Correct 2 ms 916 KB Output is correct
28 Correct 2 ms 916 KB Output is correct
29 Correct 2 ms 916 KB Output is correct
30 Correct 2 ms 924 KB Output is correct
31 Correct 2 ms 928 KB Output is correct
32 Correct 2 ms 928 KB Output is correct
33 Correct 2 ms 932 KB Output is correct
34 Correct 2 ms 936 KB Output is correct
35 Correct 2 ms 940 KB Output is correct
36 Correct 2 ms 944 KB Output is correct
37 Correct 2 ms 944 KB Output is correct
38 Correct 2 ms 952 KB Output is correct
39 Correct 2 ms 956 KB Output is correct
40 Correct 2 ms 992 KB Output is correct
41 Correct 2 ms 996 KB Output is correct
42 Correct 2 ms 1000 KB Output is correct
43 Correct 2 ms 1004 KB Output is correct
44 Correct 2 ms 1008 KB Output is correct
45 Correct 2 ms 1008 KB Output is correct