1

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

void solve(){
    int n;
    string s;
    cin>>n>>s;
    vector<int> nums(n+1);
    cout<<s;
    if (n<=1) {
        cout<<"\n";
        return;
    }
    for (int i=1;i<=n;i++) nums[i] = s[n-i] - '0';
    for (int i=1;i<=n;i++){
        if (nums[i]<=4){
            nums[i] = 0;
        }else {
            nums[i] = 0;
            nums[i+1]++;
            for (int j=i+1;j<n;j++){
                if (nums[j]>9){
                    nums[j] = 0;
                    nums[j+1]++;
                }
            }
        }
        cout<<" -> ";
        for (int i=n;i>=1;i--) cout<<nums[i];  
        if (i==n-1) break;
    }
    cout<<"\n";
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}

2

#include <iostream>
#include <set>
using namespace std;
using ll = long long;
void solve() {
    int a;
    ll n, m;
    cin >> a >> n >> m;
    set<ll> red;
    for (int i = 0; i < a; ++i) {
        ll s;
        cin >> s;
        red.insert(s);
    }
    for (ll s : red) {
        ll r = (s - 1) / m;
        ll c = (s - 1) % m;
        ll mirror = r * m + m - c;
        if (red.find(mirror) == red.end()) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

3

#include<iostream>
//#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int V = 1000;

int dp[N][V + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    cin >> k >> n;
    for (int i = 1; i <= n; i++) {
        // 不让当前行的数进入 LIS，继承前 i-1 行的答案
        for (int v = 0; v <= V; v++) {
            dp[i][v] = dp[i - 1][v];
        }

        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;

            int len = 1;

            if (x > 0) {
                // 严格上升：前驱值必须小于 x
                len = dp[i - 1][x - 1] + 1;
            }

            dp[i][x] = max(dp[i][x], len);
        }

        // 维护“结尾值不超过 v”的前缀最大值
        for (int v = 1; v <= V; v++) {
            dp[i][v] = max(dp[i][v], dp[i][v - 1]);
        }
    }

    cout << dp[n][V] << '\n';
    return 0;
}

4

#include<iostream>
#include<iomanip>
//#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

int n;
ll k;
vector<ld> x, y, b;

bool check(ld v) {
    for (int i = 0; i < n; ++i) {
        b[i] = x[i] * (y[i] - v);
    }

    sort(b.begin(), b.end());

    ll cnt = 0;

    for (int i = 0; i < n - 1; ++i) {
        int l = i + 1;
        int r = n - 1;
        int pos = n;  // 没有合法位置时，贡献为 0

        // 找到第一个满足 b[i] + b[j] >= 0 的 j
        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (b[i] + b[mid] >= 0) {
                pos = mid;
                r = mid - 1;  // 尝试找更靠左的合法位置
            } else {
                l = mid + 1;
            }
        }

        cnt += n - pos;

        if (cnt >= k) {
            return true;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    x.resize(n);
    y.resize(n);
    b.resize(n);

    ld low = 1e9L;
    ld high = 0;

    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        low = min(low, y[i]);
        high = max(high, y[i]);
    }

    // 外层二分第 k 大的函数值
    for (int iter = 0; iter < 45; ++iter) {
        ld mid = (low + high) / 2;

        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }

    cout << fixed << setprecision(6)
         << (low + high) / 2 << '\n';

    return 0;
}