Submission #859492

#	Time	Username	Problem	Language	Result	Execution time	Memory
859492		khueprovip	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	2 ms	388 KiB

numbers

#include<bits/stdc++.h>
#define int long long
#define double long double
#define PB push_back
#define maxn 100007
#define bit(x,i) ((x>>i)&1)
#define S second
#define F first
#define MP make_pair
#define epsilon 0.000001

using namespace std;

typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int inf = 1e18;
const int mod = 1e9+7;
const double PI = acos(-1);

int l,r,f[19][2][11][11][2];

void readData(){
    cin>>l>>r;
}

int dp(string s, int id, int smaller, int t1, int t2, int st){
    if (id==s.size()) return 1ll;
    if (f[id][smaller][t1][t2][st]!=-1) return f[id][smaller][t1][t2][st];
    int limit,res=0;
    if (smaller) limit=9;
    else limit=s[id]-'0';
    for (int i=0;i<=limit;i++){
        if (st==0){
            if (i==0) res+=dp(s,id+1,smaller||(i<s[id]-'0'),10,10,0);
            else res+=dp(s,id+1,smaller||(i<s[id]-'0'),i,10,1);
        }
        else{
            if (i==t1||i==t2) continue;
            res+=dp(s,id+1,smaller||(i<s[id]-'0'),i,t1,1);
        }
    }
    f[id][smaller][t1][t2][st]=res;
    return res;
}

int cal(int x){
    memset(f,-1,sizeof(f));
    string s=to_string(x);
    return dp(s,0,0,10,10,0);
}

void solve(){
    int ans=cal(r)-cal(l-1);
    cout<<ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("254.inp","r",stdin);
    //freopen(".out","w",stdout);
    readData();
    solve();
    return 0;
}
/*
               _oo0oo_
              o8888888o
              88" . "88
              (| -_- |)
              0\  =  /0
            ___/`---'\___
          .' \\|     |// '.
         / \\|||  :  |||// \
        / _||||| -:- |||||- \
       |   | \\\  -  /// |   |
       | \_|  ''\---/''  |_/ |
       \  .-\__  '-'  ___/-. /
     ___'. .'  /--.--\  `. .'___
  ."" '<  `.___\_<|>_/___.' >' "".
 | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 \  \ `_.   \_ __\ /__ _/   .-` /  /
=====`-.____`.___ \_____/___.-`___.-'=====
               `=---='
*/

Compilation message (stderr)

numbers.cpp: In function 'long long int dp(std::string, long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (id==s.size()) return 1ll;
      |         ~~^~~~~~~~~~

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