Submission #309390

#	Time	Username	Problem	Language	Result	Execution time	Memory
309390		nicolaalexandra	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	384 KiB

numbers

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