oj.uz

Submission #237957

# Submission time Handle Problem Language Result Execution time Memory
237957 2020-06-09T13:07:21 Z Andrei_Cotor Palindrome-Free Numbers (BOI13_numbers) C++11
23.75 / 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;
        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
18.75 / 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 Incorrect 4 ms 384 KB Output isn't correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 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 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Incorrect 5 ms 384 KB Output isn't correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 4 ms 384 KB Output isn't correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Incorrect 4 ms 384 KB Output isn't correct
20 Incorrect 4 ms 384 KB Output isn't correct

Subtask #2
5.0 / 75.0

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