제출 #1256894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256894		Thunnus	Palindrome-Free Numbers (BOI13_numbers)	C++20	0 / 100	0 ms	328 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int N = 10;
int dp[2 * N][N + 1][N + 1][2], len; // dp[pos][i][j][smaller] -> i sonrakine aktarılan 2 önceki, j -> sonrakine aktarılan 1 önceki eleman eğer i veya j 10 ise sonrakine eleman kısıtlaması aktarılmıyor (başlangıç) 
string s;

inline int calc(int a){
	if(a < 0) return 0ll;
    memset(dp, 0, sizeof(dp));
    dp[0][10][10][0] = 1;
    s.clear();
    do {
        s += ('0' + a % 10);
        a /= 10;
    } while(a);
    reverse(s.begin(), s.end());
    cout << "a: " << a << " s: " << s << "\n";
    len = sz(s) / 2 + (sz(s) & 1);
    for(int pos = 0; pos < sz(s); pos++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
				//if(i == j && i != 10) continue;
                for(int smaller = 0; smaller < 2; smaller++){
					if(dp[pos][i][j][smaller] == 0) continue;
                    for(int num = 0; num < 10; num++){
                        if(num == i || num == j || (!smaller && num > s[pos] - '0')) continue;
                        dp[pos + 1][num][i][smaller || num < s[pos] - '0'] += dp[pos][i][j][smaller];
                        //cout << "from: " << pos << " " << i << " " << j << " " << smaller << " dp: " << dp[pos][i][j][smaller] << " to: " << pos + 1 << " " << num << " " << i << " " << (smaller || num < s[pos] - '0') << "\n";
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i <= 10; i++){
        for(int j = 0; j <= 10; j++){
            //if(i == j) continue;
            ans += dp[sz(s)][i][j][0] + dp[sz(s)][i][j][1];
        }
    }
    return ans;
}

inline void solve(){
    int a, b;
    cin >> a >> b;
    int vala = calc(a - 1), valb = calc(b);
    int palnum = valb - vala;
    cout << palnum << "\n";
    return;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
	return 0;
}

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