Submission #237957

#	Time	Username	Problem	Language	Result	Execution time	Memory
237957		Andrei_Cotor	Palindrome-Free Numbers (BOI13_numbers)	C++11	23.75 / 100	5 ms	384 KiB

numbers

#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
• Subtask 2: 5 / 75