oj.uz

Submission #137564

# Submission time Handle Problem Language Result Execution time Memory
137564 2019-07-28T06:33:46 Z silxikys Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int dig[20];
ll dp[20][11][11][2][2]; //place, 2, 1, under, hasStarted

ll f(int len, int d1, int d2, bool under, bool started) {
    if (len == -1) return 1;
    ll& res = dp[len][d1][d2][under][started];
    if (res >= 0) return res;
    res = 0;
    if (under) {
        if (d1 != 0 && d2 != 0) res += f(len-1,d2,started?0:10,under,started);
        for (int d = 1; d <= 9; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,under,true);
        }
    }
    else {
        if (dig[len] > 0 && d1 != 0 && d2 != 0) res += f(len-1,d2,started?0:10,true,started);
        for (int d = 1; d < dig[len]; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,true,true);
        }
        if (dig[len] != d1 && dig[len] != d2) 
            res += f(len-1,d2,dig[len],under,true);
    }
    //printf("[%d][%d][%d][%d][%d]: %lld\n",len,d1,d2,under,started,res);
    return res;
}

ll solve(ll x) {
    if (x == -1) return 0;
    memset(dp,-1,sizeof dp);
    int len = 0;
    while (x) {
        dig[len++] = x % 10;
        x /= 10;
    }
    return f(len-1,10,10,false,false);
}

bool isPalindrome(ll x) {
    vector<int> digits;
    while (x > 0) {
        digits.push_back(x % 10);
        x /= 10;
    }
    if (digits.size() <= 1) return false;
    for (int i = 0; i < digits.size()-1; i++) {
        if (digits[i] == digits[i+1]) return true;
    }
    for (int i = 0; i < digits.size()-2; i++) {
        if (digits[i] == digits[i+2]) return true;
    }
    return false;
}

ll check(ll x) {
    ll ans = 0;
    for (ll i = 0; i <= x; i++) {
        if (!isPalindrome(i)) {
            ans++;
            //cout << i << '\n';
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll a, b; cin >> a >> b;
    ll ans = solve(b) - solve(a-1);
    cout << ans << '\n';
    /*
    ll a; cin >> a;
    cout << solve(a) << ' ' << check(a) << '\n';
    */
}

Compilation message

numbers.cpp: In function 'bool isPalindrome(ll)':
numbers.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < digits.size()-1; i++) {
                     ~~^~~~~~~~~~~~~~~~~
numbers.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < digits.size()-2; i++) {
                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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