2024牛客暑期多校训练营10

难度梯度 ABH FK LJD ICE MG

A

题意

背景是英雄联盟的投票机制。

四个人同意则算投降成功。

两个人拒绝则算投降失败。

给出五个字符，表示每个人的状态。

'Y' 是同意，'N' 是拒绝，'-' 是未投票。

问根据当前的状态，是否能确定投降的结果。

解题思路

有四个 'Y' 则一定投降成功，有两个 'N' 则一定投降失败，否则结果不定。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string str;
    cin >> str;
    int Y = count(begin(str), end(str), 'Y');
    int N = count(begin(str), end(str), 'N');
    if (Y >= 4) {
        cout << 1 << "\n";
        return 0;
    }
    if (N >= 2) {
        cout << -1 << "\n";
        return 0;
    }
    cout << 0 << "\n";
    return 0;
}

B std::pair

题意

实现std::pair。

只有三种类型 pair、int 和 double。

解题思路

线性建树。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
struct Node {
    int base;
    Node *first;
    Node *second;
};
vector<Node*> type(5005);
string name[5005];
void print(Node *t) {
    if (t -> base == 1) {
        cout << "int";
    } else if (t -> base == 2) {
        cout << "double";
    } else {
        cout << "pair<";
        print(t -> first);
        cout << ",";
        print(t -> second);
        cout << ">";
    }
}
Node* build(const string &s, int &i) {
    Node *t = new Node;
    if (s[i] == 'i') {
        i += 3;
        t -> base = 1;
    } else if (s[i] == 'd') {
        i += 6;
        t -> base = 2;
    } else {
        i += 5;
        t -> first = build(s, i);
        i++;
        t -> second = build(s, i);
        i++;
    }
    return t;
}
int main() {
    int n, q;
    cin >> n >> q;
    map<string, int> idx;
    for (int i = 0 ; i < n ; i++) {
        string s;
        cin >> s >> name[i];
        name[i].pop_back();
        int cur = 0;
        type[i] = build(s, cur);
        idx[name[i]] = i;
    }
    while (q--) {
        string s;
        cin >> s;
        s += ".";
        vector<string> vec;
        for (int i = 0 ; i < (int) s.size() ; i++) {
            int j = s.find('.', i);
            vec.push_back(s.substr(i, j - i));
            i = j;
        }
        Node *t = type[idx[vec[0]]];
        for (int i = 1 ; i < (int) vec.size() ; i++) {
            if (vec[i] == "first") {
                t = t -> first;
            } else {
                t = t -> second;
            }
        }
        print(t);
        cout << "\n";
    }
    return 0;
}

D Is it rated?

题意

一共 $n$ 场比赛，每场比赛有一个表现分 $p_i$，你可以选择至多 $m$ 场比赛不计分，

给定系数 $k$ 和初始分值 $r_0$。

计分规则为 $r=k*p+(1-k)*r$， $r$ 为当前的分值。

问按顺序比赛后所能得到的最大分值。

$1\le m\le n\le10^5$，$0\le r_0,p_i\le10^5$。

$0.1\le k\le1.0$。

解题思路

我们观察式子中的 $(1-k)*r$。

假设我们进行 $320$ 场比赛，那么会得到 $(1-k)^{320}*r$，

我们可以发现 $(1-k)$ 是小于 $1$ 的数，那么 $320$ 次幂会特别特别小，

当 $k=0.1$ 时，式子最大，此时 $(1-k)=0.9$，$0.9^{320}\approx2.27826*10^{-15}$

这个时候 $0.9^{320}*r<10^9$，此时对答案没有影响。

所以我们可以设定一个阈值 $M=320$。

当 $n-m<M$ 时，此时 $n<M$，所以我们直接暴力 $dp$ 即可。

此时的时间复杂度为 $O(n*(n-m))$。

当 $n-m\ge M$ 时，我们发现至少要计分 $M$ 场比赛，

这个时候我们发现前面 $n-m-M$ 场比赛是对答案没有任何影响的，所以我们可以直接跳过这些比赛。

这样剩下的比赛只会有 $m+M$ 场，这个时候我们暴力 $dp$ 即可。

此时的时间复杂度为 $O((m+M)*M)$。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int M = 320;
void solve() {
    int n, m;
    cin >> n >> m;
    double k;
    cin >> k;
    int r;
    cin >> r;
    vector<int> p;
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        p.push_back(x);
    }
    if (n - m >= M) {
        p.erase(begin(p), begin(p) + n - m - M);
    }
    int N = min(n - m, M);
    vector<double> f(N + 1, -1e18);
    f[0] = r;
    for (auto &p : p) {
        auto g = f;
        for (int j = 0 ; j <= N ; j++) {
            if (f[j] < 0) continue;
            g[min(N, j + 1)] = max(g[min(N, j + 1)], k * p + (1 - k) * f[j]);
        }
        f.swap(g);
    }
    cout << fixed << setprecision(12) << f[N] << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F Collinear Exception

题意

$n*n$ 的二维平面，给出 $n*n$ 个点，每个点互不相同。

有一个点集 $S$，初始为空。

按顺序对每个点执行操作，

如果存在 $S$ 中的两点，与当前点，三点共线，则不操作。

否则将当前点加入 $S$。

问每个点是否在 $S$ 中。

$1\le n\le1000$。

解题思路

观察发现，$S$ 中的点不会超过 $2n$ 个。

对于每次加入的点，我们枚举 $S$ 中的所有点，对这个直线上的所有整点进行标记。

之后对于有标记的点，我们直接跳过。

这样我们最多枚举 $S$，枚举 $2n$ 次。

然后每次枚举 $S$，被标记的点数为 $\sum\dfrac{n}{\max(\Delta x,\Delta y)}$。

我们可以确定这个点数最坏不会超过 $10^5$，

所以时间复杂度通过。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int x[1000005], y[1000005];
bool vis[1000005];
bool stt[1005][1005];
int mpx[1005], mpy[1005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int m = n * n;
    set<array<int, 2>> st;
    for (int i = 0 ; i < m ; i++) {
        cin >> x[i] >> y[i];
        if (mpx[x[i]] >= 2 || mpy[y[i]] >= 2) continue;
        if (stt[x[i]][y[i]]) continue;
        vis[i] = true;
        mpx[x[i]]++;
        mpy[y[i]]++;
        for (auto &[x1, y1] : st) {
            if (x1 == x[i] || y1 == y[i]) continue;
            int tx = x[i] - x1;
            int ty = y[i] - y1;
            int g = abs(__gcd(tx, ty));
            tx /= g;
            ty /= g;
            {
                int ttx = x[i], tty = y[i];
                while (ttx >= 1 && ttx <= n && tty >= 1 && tty <= n) {
                    stt[ttx][tty] = true;
                    ttx += tx;
                    tty += ty;
                }
            }
            {
                int ttx = x[i], tty = y[i];
                while (ttx >= 1 && ttx <= n && tty >= 1 && tty <= n) {
                    stt[ttx][tty] = true;
                    ttx -= tx;
                    tty -= ty;
                }
            }
        }
        st.insert({x[i], y[i]});
    }
    for (int i = 0 ; i < m ; i++) {
        cout << vis[i];
    }
    cout << "\n";
    return 0;
}

H All-in at the Pre-flop

题意

$A,B$ 两人进行游戏。

刚开始 $A,B$ 分别有 $a,b$ 个筹码。

如果筹码多的赢了，就会直接赢得整局游戏。

如果筹码少的赢了，那么他就会从筹码多的拿里拿取与自己等量的筹码。

输赢的概率均为 $\frac{1}{2}$。

问 $A,B$ 赢得整局游戏的概率。

解题思路

可以知道整局游戏中 $a+b$ 固定。

令 $f(x)$ 表示拥有 $x$ 个筹码玩家的胜率，$n=a+b$。

初始 $f(0)=0$，$f(n)=1$。

当 $x<\dfrac{n}{2}$ 时，$f(x)=\dfrac{1}{2}*f(0)+\dfrac{1}{2}*f(2*x)$，

当 $x\ge\dfrac{n}{2}$ 时，$f(x)=\dfrac{1}{2}*f(2x-n)+\dfrac{1}{2}*f(n)$。

可以猜 $f(x)=\dfrac{x}{n}$。

验证后发现正确。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
i64 inv(i64 a, i64 b = P - 2, i64 res = 1) {
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    i64 a, b;
    cin >> a >> b;
    i64 sum = a + b; 
    cout << a * inv(a + b) % P << " " << b * inv(a + b) % P << "\n";
    return 0;
}

I Riffle Shuffle

题意

给定一个 $n$ 张牌的排列，使用 Riffle Shuffle 将 $1,2,…,n$ 洗成给定排列。

定义 Riffle Shuffle 为，将牌任意切成两叠，然后按照任意顺序归并。

最小化洗牌次数并输出方案。

$2\le n\le52$。

解题思路

我们可以知道将 $1,2,…,n$ 洗成排列 $p$ 的最小操作次数等于将排列 $p$ 洗成 $1,2,…,n$ 的最小操作次数。

因为是可逆的。

所以我们从排列 $p$ 洗成 $1,2,…,n$ ，最后把操作全部逆转即可。

那么我们可以每次操作可以把相邻的两个上升序列一个。第一个数字小的放到前面那叠，大的放到后面那叠，那么洗牌之后，这两个上升序列可以合并成一个上升序列。

即 $8,3,1,4,2,6,5,7$，相邻的上升序列为 $1,2$，$3,4,5$，$6,7$，$8$。

我们把第 $1$ 个和第 $3$ 个序列放在前面那叠，第 $2$ 个和第 $4$ 个序列放在后面那叠即：$1,2,6,7$ 和 $8,3,4,5$。

这样我们可以得到 $8,1,2,3,4,5,6,7$。

那么再洗一次即可得到 $1,2,…,8$。

所以我们暴力找出所有上升序列，然后按奇偶分叠，暴力模拟即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
void solve() {
    int n;
    cin >> n;
    vector<int> tar(n), p(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> p[i];
        p[i]--;
        tar[i] = i;
    }
    vector<string> ans;
    while (p != tar) {
        vector<int> pos(n);
        for (int i = 0 ; i < n ; i++) {
            pos[p[i]] = i;
        }
        vector<array<int, 2>> seq;
        for (int L = 0 ; L < n ; ) {
            int R = L;
            while (R + 1 < n && pos[R] < pos[R + 1]) {
                R++;
            }
            seq.push_back({L, R});
            L = R + 1;
        }
        string res = string(n, 'B');
        for (int i = 0 ; i < (int) seq.size() ; i += 2) {
            auto [L, R] = seq[i];
            for (int j = L ; j <= R ; j++) {
                res[pos[j]] = 'A';
            }
        }
        ans.push_back(res);
        vector<int> tp;
        for (int i = 0 ; i < n ; i++) {
            if (res[i] == 'A') {
                tp.push_back(p[i]);
            }
        }
        for (int i = 0 ; i < n ; i++) {
            if (res[i] == 'B') {
                tp.push_back(p[i]);
            }
        }
        p.swap(tp);
    }
    reverse(begin(ans), end(ans));
    cout << ans.size() << "\n";
    for (auto &x : ans) {
        cout << x << "\n";
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

J Doremy's Starch Trees

题意

给定一个无根树 $X$ 和有根树 $Y$，但是不确定根。

问 $Y$ 是否可以使 $X$ 的点分树，若是，则请输出符合条件的任意一个根。

如果 $Y$ 是 $X$ 的点分树，那么对于 $X$ 上任意一点 $u$，和它的任意儿子 $v$，至少在 $Y$ 存在 $v$ 的子树中有一点与 $u$ 有边。

解题思路

对于 $X$ 上的每一条边 $(u,v)$，

如果是从 $u\rightarrow v$，那么对于 $u$ 及 $u$ 以外的点，这条边都符合，

如果是从 $u\leftarrow v$，那么对于 $v$ 及 $v$ 以外的点，这条边都符合。

一共有 $n-1$ 条边，如果一个点被 $n-1$ 条边满足条件，那么就说明这个点可以使点分树的根。

我们可以使用树上差分来快速的进行子树加，

最后再树上前缀和计算权值并判断合法的根。

那么对于有根树，一条边有两种方向，我们只需要对边的两种方向打标记即可。

对于 $X$ 上一边 $(u,v)$，

如果 $p$ 是两点的最近公共祖先，

如果 $p=u$，那么对于 $u\rightarrow v$，那么我们需要对 $u$ 及 $u$ 以外的点，都需要 $+1$，

那么对于树上差分，令 $s$ 为 $v$ 到 $u$ 上距离 $u$ 最近但不等于 $u$ 的一点， $sum_1=sum_1+1$，$sum_p=sum_p-1$。

如果 $p=v$ 同理。

当 $(p\neq u)\wedge(p\neq v)$ 时，对于 $u\rightarrow v$，实际上是 $u\rightarrow p\rightarrow v$，这个时候是 $sum_u=sum_u+1$，

对于 $v\rightarrow u$，实际上是 $v\rightarrow p\rightarrow u$，这个时候是 $sum_v=sum_v+1$。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<int> adj[1000005];
int deep[1000005], fa[1000005][20];
bool vis[1000005][2]; // 0 表示 深度高到深度低, 1 相反
int sum[1000005];
void dfs1(int u, int p) {
    deep[u] = deep[p] + 1;
    fa[u][0] = p;
    for (int i = 1 ; i <= 19 ; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs1(to, u);
    }
}
array<int, 2> LCA(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    int t = x;
    for (int i = 19 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] >= deep[y]) x = fa[x][i];
        if (deep[fa[t][i]] > deep[y]) t = fa[t][i];
    }
    if (x == y) return {x, t};
    for (int i = 19 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] == deep[fa[y][i]]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return {fa[x][0], x};
}
void work(int x, int y) {
    auto [pfa, p] = LCA(x, y);
    if (pfa == x) {
        // 在有根树上 x 是 y 的祖宗
        { // 对于 x(深度低) -> y(深度高)
            // x 及 x 的祖宗都合法
            if (!vis[p][1]) {
                vis[p][1] = true;
                sum[1]++;
                sum[p]--;
            }
        }
        { // 对于 y(深度高) -> x(深度低)
            // 对于 y 及 y 的祖宗都合法
            if (!vis[y][0]) {
                vis[y][0] = true;
                sum[y]++;
            }
        }
        return;
    }
    if (pfa == y) {
        // 在有根树上 y 是 x 的祖宗
        { // 对于 x(深度高) -> y(深度低)
            // x 及 x 的祖宗都合法
            if (!vis[x][0]) {
                vis[x][0] = true;
                sum[x]++;
            }
        }
        { // 对于 y(深度低) -> x(深度高)
            // y 及 y 的祖宗都合法
            if (!vis[p][1]) {
                vis[p][1] = true;
                sum[1]++;
                sum[p]--;
            }

        }
        return;
    }
    // x 和 y 不在一条链上
    { // 对于 x(深度高) -> LCA(深度低) -> y
        // x 及 x 的祖宗都合法
        if (!vis[x][0]) {
            vis[x][0] = true;
            sum[x]++;
        }
    }
    { // 对于 y(深度高) -> LCA(深度低) -> x
        // y 及 y 的祖宗都合法
        if (!vis[y][0]) {
            vis[y][0] = true;
            sum[y]++;
        }
    }
}
int n, ans;
void dfs2(int u, int p) {
    sum[u] += sum[p];
    if (ans != -1) return;
    if (sum[u] == n - 1) {
        ans = u;
        return;
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs2(to, u);
        if (ans != -1) {
            return;
        }
    }
}
void solve() {
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        adj[i].resize(0);
        sum[i] = 0;
        vis[i][0] = vis[i][1] = false;
    }
    vector<array<int, 2>> edge;
    for (int i = 2 ; i <= n ; i++) {
        int x;
        cin >> x;
        edge.push_back({i, x});
    }
    for (int i = 2 ; i <= n ; i++) {
        int x;
        cin >> x;
        adj[i].push_back(x);
        adj[x].push_back(i);
    }
    dfs1(1, 0);
    for (auto &[x, y] : edge) {
        work(x, y);
    }
    ans = -1;
    dfs2(1, 0);
    cout << ans << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

K Doremy's IQ 2

题意

有 $n$ 场比赛，每场比赛有一个难度 $a_i$。

有 $n$ 天，每天举行一场比赛。

你的 $IQ$ 初始化为 $0$。

对于每场比赛，比赛的难度为 $x：

如果 $IQ>x$，则 $IQ--$。
如果 $IQ<x$，则 $IQ++$。
如果 $IQ=x$，则无事发生。

你现在可以任意安排比赛的顺序，问最多有几天无事发生。

解题思路

我们可以把题目转化为起点为 $0$，

我们可以消耗一个等于自己的值使答案 $+1$，

我们可以消耗一个大于自己的值往正方向走一步。

我们可以消耗一个小于自己的值往反方向走一步。

我们可以知道，我们的 $IQ$ 至多经过 $0$ 点 $1$ 次。

所以我们需要枚举最开始的方向，和回不回头即可。

对于一个方向，每走一步就判断回头能有多少贡献。

我们可以二分回头的步数，快速计算贡献。

时间复杂度 $O(n*\log n)$。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n;
    cin >> n;
    vector<int> a(1), b(1);
    int ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        if (x < 0) {
            a.push_back(x);
        } else {
            b.push_back(x);
        }
    }
    int res = 0;
    { // 往正方向
        int m = b.size() - 1;
        for (int i = 1 ; i <= m ; i++) {
            if (m - i >= b[i]) {
                int temp = i;
                if (a.size() > 1) {
                    int mm = a.size() - 1;
                    int L = 1 + b[i], R = mm;
                    if (L < R) {
                        while (L < R) {
                            int mid = L + R >> 1;
                            if ((mid - (1 + b[i])) >= -a[mid]) {
                                R = mid;
                            } else {
                                L = mid + 1;
                            }
                        }
                        if ((L - (1 + b[i])) >= -a[L]) {
                            temp += mm - L + 1;
                        }
                    }
                }
                res = max(res, temp);
            }
        }
    }
    { // 往负方向走
        int m = a.size() - 1;
        for (int i = m ; i >= 1 ; i--) {
            if ((i - 1) >= -a[i]) {
                int temp = m - i + 1;
                if (b.size() > 1) {
                    int mm = b.size() - 1;
                    int L = 1, R = mm + a[i];
                    if (L < R) {
                        while (L < R) {
                            int mid = L + R + 1 >> 1;
                            if (mm + a[i] - mid >= b[mid]) {
                                L = mid;
                            } else {
                                R = mid - 1;
                            }
                        }
                        if (mm + a[i] - L >= b[L]) {
                            temp += L;
                        }
                    }
                }
                res = max(res, temp);
            }
        }
    }
    cout << ans + res << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

L Tada!

题意

给出 $m$ 个长度为 $n$ 的数字为 $0$ 到 $9$ 的密码锁 $s_i$，每个密码锁给定一个操作步数 $t_i$。

每个锁都恰好操作 $t_i$ 次，问 $m$ 个密码锁最终状态全相同时的状态。

如果只有一个，则输出那一个，如果没有输出 "IMPOSSIBLE"，否则输出 "MANY"。

解题思路

我们可以发现操作是可逆的，也就是说从状态 $A$ 操作 $m$ 次到状态 $B$，那么状态 $B$ 也可以操作 $m$ 次到状态 $A$。

然后操作也是可加的，也就是说从状态 $A$ 操作 $m$ 次到状态 $B$，那么状态 $A+C$ 也可以操作 $m$ 次到状态 $B+C$。

那么我们可以暴力建边之后，从状态 $0$ 限制步长 $\le50$ 跑 $bfs$。

确定状态 $0$ 走 $t$ 步是否能到达状态 $k$。

本质上，符合最终状态，那么说明每个密码锁都能走 $t_i$ 步到达。

那么刚开始我们令所有状态都为可达的，只要有一个密码锁不可到达该状态，那么就一定不是最终状态。

那么之后，我们可以枚举每个密码锁，再枚举状态 $0$ 到 $10^{n}-1$，令 $j$ 为枚举的状态。

然后判断状态 $0$ 走 $t$ 步是否能到达 $j$，

如果不能到达说明，状态 $0+s$ 走 $t$ 步不能到达状态 $j+s$。

那么我们标记状态 $j+s$ 为 $0$ 表示不能到达。

处理完所有的密码锁之后，剩下的标记为可到达的状态就是最终答案。

我们分类讨论即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int p10[10];
vector<int> adj[6][100005];
bool dp[6][55][100005], vis[100005];
int n, m;
array<int, 5> toArray(int x) {
    array<int, 5> a{};
    for (int i = 0 ; i < n ; i++) {
        a[i] = x % 10;
        x /= 10;
    }
    return a;
};
int fromArray(array<int, 5> &a) {
    int res = 0;
    for (int i = n - 1 ; i >= 0 ; i--) {
        res = res * 10 + a[i];
    }
    return res;
}
void solve() {
    cin >> n >> m;
    for (int i = 0 ; i < p10[n] ; i++) {
        vis[i] = true;
    }
    for (int i = 1 ; i <= m ; i++) {
        int s, t;
        cin >> s >> t;
        auto b = toArray(s);
        for (int j = 0 ; j < p10[n] ; j++) {
            if (dp[n][t][j]) continue;
            auto a = toArray(j);
            for (int k = 0 ; k < n ; k++) {
                a[k] = (a[k] + b[k]) % 10;
            }
            vis[fromArray(a)] = false;
        }
    }
    vector<int> ans;
    for (int i = 0 ; i < p10[n] ; i++) {
        if (vis[i]) {
            ans.push_back(i);
        }
    }
    int k = ans.size();
    if (k == 0) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    if (k == 1) {
        string res = to_string(ans[0]);
        cout << string(n - res.size(), '0') << res << "\n";
        return;
    }
    cout << "MANY\n";
}
int main() {
    p10[0] = 1;
    for (int i = 1 ; i <= 6 ; i++) {
        p10[i] = p10[i - 1] * 10;
    }
    for (n = 1 ; n <= 5 ; n++) {
        for (int i = 0 ; i < p10[n] ; i++) {
            for (int L = 0 ; L < n ; L++) {
                auto a = toArray(i);
                auto b = a;
                for (int R = L ; R < n ; R++) {
                    a[R] = (a[R] + 1) % 10;
                    b[R] = (b[R] + 9) % 10;
                    adj[n][i].push_back(fromArray(a));
                    adj[n][i].push_back(fromArray(b));
                }
            }
        }
        dp[n][0][0] = true;
        for (int i = 0 ; i < 50 ; i++) {
            for (int j = 0 ; j < p10[n] ; j++) {
                if (!dp[n][i][j]) continue;
                for (auto &to : adj[n][j]) {
                    dp[n][i + 1][to] = true;
                }
            }
        }
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}