oj.uz

Submission #283065

# Submission time Handle Problem Language Result Execution time Memory
283065 2020-08-25T09:27:02 Z Atill83 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 11 ms 512 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll d[2][13][12][11];
int bas[21];
ll kc[20];

bool pal(ll a){
    ll last1 = -2, last2 = -1;

    while(a){
        ll cur = a % 10;
        if(cur == last1 || cur == last2){
            return 0;
        }
        last1 = last2;
        last2 = cur;
        a /= 10;
    }
    return 1;
}

ll ite(int say){
    ll ans = 0;
    if(say == 0){
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(k == 10 && l == 0) continue;
                    ans += d[0][j][k][l];
                }
            }
        }
    }
    for(int i = 1; i <= say; i++){
        ans = 0;
        memset(d[i&1], 0, sizeof(d[i&1]));
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(l == 0 && k == 10) continue;
                    if(j == k || k == l || j == l) continue;
                    for(int z = 0; z <= 12; z++){
                        if(z == j || z == k || j == k) continue;
                        d[i&1][j][k][l] += d[i&1^1][z][j][k];
                    }
                    ans += d[i&1][j][k][l];
                }
            }
        }
    }
    return ans;
}



ll cn(ll x){
    if(x < 0) return 0;
    if(x <= 9) return x + 1;
    ll y = x;
    int idx = 0;
    while(y){
        bas[idx++] = y % 10;
        y /= 10;
    }
    reverse(bas, bas + idx);
    ll ans = 0;
    for(int i = 1; i < idx; i++){
        ans += kc[i];
    }
    ll cur = 0;
    //cerr<<x<<" "<<idx<<endl;
    for(int i = 0; i < idx; i++){
        if(pal(cur)){
            memset(d[0], 0, sizeof(d[0]));
            if(i == 0){
                for(int j = 1; j < bas[i]; j++){
                    d[0][11][10][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }else if(i == 1){
                for(int j = 0; j < bas[i]; j++){
                    if(j == bas[i - 1]) continue;
                    d[0][10][bas[i - 1]][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }else{
                
                for(int j = 0; j < bas[i]; j++){
                    if(j == bas[i - 1] || j == bas[i - 2]) continue;
                    d[0][bas[i - 2]][bas[i - 1]][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }
        }else{
            break;
        }
        cur *= 10;
        cur += bas[i];
    }
    //cerr<<x<<" "<<ans<<endl;
    ans += pal(x);
    return ans;
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif
    ll a, b;
    cin>>a>>b;


    d[0][12][11][10] = 1;


    for(int i = 1; i <= 19; i++){
        memset(d[i&1], 0, sizeof(d[i&1]));
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(l == 0 && k == 10) continue;
                    if(j == k || k == l || j == l) continue;
                    for(int z = 0; z <= 12; z++){
                        if(z == j || z == k || j == k) continue;
                        d[i&1][j][k][l] += d[i&1^1][z][j][k];
                    }
                    kc[i] += d[i&1][j][k][l];
                }
            }
        }
    }
    kc[1]++;
    cout<<cn(b) - cn(a - 1)<<endl;  




    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

numbers.cpp: In function 'll ite(int)':
numbers.cpp:55:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   55 |                         d[i&1][j][k][l] += d[i&1^1][z][j][k];
      |                                              ~^~
numbers.cpp: In function 'int main()':
numbers.cpp:143:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  143 |                         d[i&1][j][k][l] += d[i&1^1][z][j][k];
      |                                              ~^~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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