Submission #1246985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246985		clementine	Palindrome-Free Numbers (BOI13_numbers)	C++20	23.75 / 100	1 ms	328 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
void _debug_cerr(const char* name, T&& value) {
    cerr << name << ": " << value << '\n';
}

template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
    const char* comma = strchr(names, ',');
    cerr.write(names, comma - names) << ": " << value << ", ";
    _debug_cerr(comma + 1, forward<Args>(args)...);
}

#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)


ll dp[10][10][20];
ll dp2[10][10][20];

void whole()
{
// base case
// l ==1
    for(int a = 0; a <=9; a ++)
    {
        for(int b = 0; b <=9; b++)
        {
            if(a != b)
            {
                dp[a][b][1] = 1;
            }
            else
            {
                dp[a][b][1] = 0;
            }
        }
    }
   
// recursion
    for(int l = 2; l <=19; l++)
    {
        for(int a = 0; a <=9; a++)
        {
            for(int b = 0; b <=9; b ++)
            {
                dp[a][b][l] = 0; // initialize
                for(int x = 0; x <=9; x ++)
                {
                    if (a !=b && a !=x && b !=x)
                        dp[a][b][l] += dp[b][x][l-1];
                }
                //if(l <=4)
                    //debug(a, b, l, dp[a][b][l]);
            }
        }
    }
}

void solve(string s)
{
    // base case l = 1
    if(s[1] != s[0])
        dp2[s[1]-'0'][s[0]-'0'][1] = 1;
    else
        dp2[s[1]-'0'][s[0]-'0'][1] = 0;
    //recursion
    for(int i = 2; i < s.length(); i ++)
    {
        
       // calculating dp2[s[i]][s[i-1]][i]
       int si = s[i] - '0';
       int si1 = s[i-1] - '0';
       int si2 = s[i-2] - '0';
       dp2[si][si1][i] = 0;
       for(int x = 0; x <s[i-2] - '0'; x ++)
       {
            if(s[i]!= s[i-1] && s[i-1] - '0' != x && s[i] - '0' != x)
            {
                dp2[si][si1][i] += dp[si1][x][i-1];
                //debug(x);
                //debug(si1, x, i-1, dp[si1][x][i-1]);
            }
       }

       dp2[si][si1][i] += dp2[si1][si2][i-1];
       //debug(si, si1, dp2[si][si1][i]);
    }
   
}ll total(string s)
{
    ll tot = 10; // start at 10 for 0 to 9 
    int slen = s.length();
    // the amount of pfs from 0 - 99
    //
    for(int i = 1; i <= slen - 2; i ++)
    {
        for(int a = 1; a <=9; a ++)
        {
            for(int b = 0; b <=9; b ++)
            {
                tot += dp[a][b][i];
                //debug(a, b, i, dp[a][b][i]);
            }
        }
    }
    for(int a = 1; a < s[slen-1] - '0'; a ++)
    {
        for(int b = 0; b <=9; b ++)
        {
            tot += dp[a][b][slen-1];
            //debug(a, b, slen-1, dp[a][b][slen-1]);
        }
    }
    for(int b = 0; b < s[slen-2] - '0'; b ++)
    {
        tot += dp[s[slen-1] - '0'][b][slen-1];
        //debug(s[slen-1] - '0', b, slen - 1, dp[s[slen-1] - '0'][b][slen-1]);
    }
    //debug(tot);
    return tot;
}

ll force(int a)
{
    int temp = 0;
    for(int i = 0; i <= a; i ++)
    {
        string s = to_string(i);
       
        bool pf = true;
        for(int j = 0; j <= (int)s.length() - 2; j ++)
        {
            
            if(s[j] == s[j+1]){pf = false; break;}
        }
        for(int j = 0; j < (int)s.length() - 2; j ++)
        {
            if(s[j] == s[j+2]){pf = false; break;}
        }
        temp += pf;
    }
    return temp;
}

int main()
{
    string u, v;
    cin >> u >> v;
    whole();
    ll ans;
    if(stoll(v) <200)
    {
        ans = force(stoll(v));
    }
    else
    {
        reverse(v.begin(), v.end());
        //debug(v);
        solve(v); 
        int slen = v.length();
        ans = dp2[v[slen-1]- '0'][v[slen-2] - '0'][slen-1] + total(v);
        //cout << ans << '\n';   
    }
    ll ans2 = 0;
    if(stoll(u) < 200)
    {
        ans2 = force(stoll(u));
    }
    else
    {
        reverse(u.begin(), u.end());
        solve(u);
        int slen2 = u.length();
        ans2 = dp2[u[slen2-1]- '0'][u[slen2-2] - '0'][slen2-1] + total(u);    
    }
    cout << ans - ans2 + 1;
}

• Subtask 1: 18.75 / 25
• Subtask 2: 5 / 75