oj.uz

Submission #237959

# Submission time Handle Problem Language Result Execution time Memory
237959 2020-06-09T13:16:37 Z Andrei_Cotor Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 5 ms 384 KB 
#include<iostream>

using namespace std;

//daca nu avem 2 cifre consecutive egale, sau o cifra cu 2 vecini egali nu avem palindrom;

long long solve(long long x)
{
    if(x<10)
        return x+1;

    long long p10=1;
    int nrc=1;
    while(p10<=x)
    {
        p10*=10LL;
        nrc++;
    }
    nrc--;
    p10/=10;

    //acelasi nr de cifre ca si c
    long long rez0=1; //pana acum cifrele din fata sunt identice cu x
    long long rez1=0; //am pus o cifra < cifra din x mai in fata, deci pot pune ce vreau
    int c1=-1,c2=-1;  //ultimele 2 cifre din x
    while(p10>=1)
    {
        int c=x/p10;
        long long _rez0=0,_rez1=0;

        //daca nu pot sa continui cu egalitatea
        if(c!=c1 && c!=c2 && rez0==1)
            _rez0=1;
        else
            _rez0=0;

        //a fost egal, acum pun o cifra mai mica decat c
        int nrpos=0;
        if(c1!=-1)
        {
            for(int j=0; j<c; j++)
            {
                if(j!=c1 && j!=c2)
                    nrpos++;
            }
        }
        else
        {
            for(int j=1; j<c; j++)
            {
                if(j!=c1 && j!=c2)
                    nrpos++;
            }
        }

        _rez1=_rez1+rez0*nrpos;

        //pot sa pun orice cifra (am rezolvat restrictia <)
        if(c1!=-1)
        {
            if(c2==-1) //a doua cifra
                _rez1=_rez1+rez1*9LL;
            else
                _rez1=_rez1+rez1*8LL;
        }

        x=x%p10;
        p10/=10LL;
        c2=c1;
        c1=c;
        rez0=_rez0;
        rez1=_rez1;
    }


    //nr de cifre mai mic
    long long rez3=1; //(0)
    for(int i=nrc-1; i>=1; i--)
    {
        long long nrpos=9;
        if(i>1)
            nrpos*=9LL;

        for(int j=3; j<=i; j++)
            nrpos*=8LL;

        rez3+=nrpos;
    }

    return rez0+rez1+rez3;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long a,b;
    cin>>a>>b;

    cout<<solve(b)-solve(a-1)<<"\n";
    return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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