Submission #546231

#	Time	Username	Problem	Language	Result	Execution time	Memory
546231		_martynas	Palindrome-Free Numbers (BOI13_numbers)	C++11	100 / 100	1 ms	308 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll solve(string a)
{
    // at i-th digit, last is d, before last is dd
    ll dp[20][11][11] = {};
    int n = a.size();
    bool hasPal = false;
    // take prefix + lower digit (or same at last turn)
    for(int i = 0; i < n; i++) {
        if(i)
        for(int d = 0; d <= 9; d++) {
            for(int dd = 0; dd <= 10; dd++) {
                if(dd == d) continue;
                for(int ddd = 0; ddd <= 10; ddd++) {
                    if(ddd == d) continue;
                    dp[i][d][dd] += dp[i-1][dd][ddd];
                }
            }
        }
        if(!hasPal) {
            for(int d = (i == 0); d < a[i]-'0' + (i == n-1); d++) {
                if((i >= 1 && d == a[i-1]-'0') || (i >= 2 && d == a[i-2]-'0')) {
                    continue;
                }
                dp[i][d][(i ? a[i-1]-'0' : 10)]++;
            }
        }
        if((i >= 1 && a[i] == a[i-1]) || (i >= 2 && a[i] == a[i-2])) {
            hasPal = true;
        }
    }

    ll ans = 0;
    for(int d = 0; d <= 9; d++)
    for(int dd = 0; dd <= 10; dd++)
        ans += dp[n-1][d][dd];

    return ans;
}

int main()
{
    string a, b;
    ll t;
    cin >> t >> b;
    t--;
    a = to_string(t);

    ll suma = 0, sumb;

    if(t > 0) {
        suma = solve(a);
        for(int i = 1; i < a.size(); i++) {
            suma += solve(string(i, '9'));
        }
        suma++; // 0
    }
    else if(t == 0) {
        suma++; // 0
    }

    sumb = solve(b);
    for(int i = 1; i < b.size(); i++) {
        sumb += solve(string(i, '9'));
    }
    sumb++; // 0
    cout << sumb - suma << "\n";
    return 0;
}
/*
10
99

11
22
33
44
55
66
77
88
99
= 9
90?

*/

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i = 1; i < a.size(); i++) {
      |                        ~~^~~~~~~~~~
numbers.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1; i < b.size(); i++) {
      |                    ~~^~~~~~~~~~

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