oj.uz

Submission #309390

# Submission time Handle Problem Language Result Execution time Memory
309390 2020-10-03T12:43:21 Z nicolaalexandra Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

long long dp[20][10][10];
int v[20];
long long a,b;
int i,j,k,t;

long long solve (long long n){
    if (n < 0)
        return 0;
    if (!n)
        return 1;

    long long nr = n, sol = 1;
    int i,j,k,poz,el = 0;
    memset (v,0,sizeof v);

    while (nr){
        v[++el] = nr%10;
        nr /= 10;
    }

    reverse (v+1,v+el+1);

    for (i=1;i<el;i++){
        for (j=0;j<=9;j++)
            for (k=1;k<=9;k++)
                sol += dp[i][j][k];
    }


    for (poz=1,i=el;poz<=el;poz++,i--){
        int start = (poz == 1) ? (1) : (0);

        if (poz == el)
            v[poz]++;

        for (k=start;k<v[poz];k++){
            if ( (poz > 1 && k == v[poz-1]) || (poz > 2 && k == v[poz-2]))
                continue;
            for (j=0;j<=9;j++)
                if ((i == 1) || (j != v[poz-1] || poz == 1) )
                    sol += dp[i][j][k];
        }

        if ((poz > 1 && v[poz] == v[poz-1]) || (poz > 2 && v[poz] == v[poz-2]))
            break;

    }

    return sol;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    /// dp[i][j][k] - in cate moduri pot sa construiesc un nr din i cifre cu ultimele doua j,k
    for (i=0;i<=9;i++)
        dp[1][0][i] = 1;
    for (i=0;i<=9;i++)
        for (j=0;j<=9;j++)
            if (i != j)
                dp[2][i][j] = 1;

    for (i=3;i<=18;i++){
        for (j=0;j<=9;j++){
            for (k=0;k<=9;k++){
                if (j == k)
                    continue;
                for (t=0;t<=9;t++)
                    if (t != k && t != j)
                        dp[i][j][k] += dp[i-1][t][j];
            }}}

    cin>>a>>b;
    cout<<solve (b) - solve (a-1);

    return 0;
}

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 0 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 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 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct

Subtask #2
75.0 / 75.0

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