Submission #237950

#	Time	Username	Problem	Language	Result	Execution time	Memory
237950		Andrei_Cotor	Palindrome-Free Numbers (BOI13_numbers)	C++11	7.50 / 100	5 ms	512 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;
    while(p10<=x)
        p10*=10LL;

    p10/=10;
    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;
        for(int j=0; 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;
    }

    return rez0+rez1;
}

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: 7.5 / 25
• Subtask 2: 0 / 75