ZOJ 3816 by Chen Rui

zoj_3816.cpp

#include "cstdio"
#include "iostream"
#include "algorithm"
#include "cmath"
#include "cstring"
#include "ctime"
#include "cstdlib"
#include "vector"
#include "queue"
#include "set"
#include "map"
#define ms(a, x) memset(a, x, sizeof(a))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define repd(i, r, l) for (int i = r; i >= l; --i)
#define getint(x) scanf("%d", &x)
#define lowbit(x) (x & -x)
#define LOG 16
#define N 50010
#define P 10007
#define M 1000010

using namespace std;

long long n, ans;
int a[20], b[20], tt, c[20];

long long get(int x) {
    long long now = 0;
    rep(i, 1, tt) {
        now *= 10; if (i <= x) now += b[i];
    }
    int num = 1; c[1] = b[x];
    long long flip = b[x], f2 = 0;
    repd(i, x - 1, 1)
        if (b[i] != b[i + 1])
            flip = flip * 10 + b[i], f2 = f2 * 10 + b[i], num++;
    if (num + x < tt) return now + flip;
    
}

void solve() {
    cin >> n; n--; tt = 0; int tmp = n;
    while (tmp) {
        a[++tt] = tmp % 10; tmp /= 10;
    }
    rep(i, 1, tt / 2) swap(a[i], a[n - i + 1]);
    if (a[1] == 1) {
        ans = 0; rep(i, 1, tt - 1) ans = ans * 10 + 9;
    } else {
        ans = a[1] - 1; rep(i, 1, tt - 2) ans = ans * 10 + 9; ans += a[1] - 1;
    }
    rep(i, 1, tt) repd(j, a[i], 0) {
        b[i] = j; long long now = get(i);
        if (now <= n) { ans = max(ans, now); break; }
    }
    cout << ans << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}