CSP-J 复赛真题集训手册

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

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    string s;
    cin >> s;                 // 长度固定为 8
    int ans = 0;
    for (int i = 0; i < 8; ++i)
        if (s[i] == '1') ++ans;
    cout << ans << endl;

    return 0;
}

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

int main() {
    freopen("power.in", "r", stdin);
    freopen("power.out", "w", stdout);

    int n;
    scanf("%d", &n);

    if (n % 2 == 1) {          // 奇数不可能
        printf("-1\n");
        return 0;
    }
    for (int i = 24; i >= 1; --i) {      // 从大到小枚举 2^i
        if (n >= (1 << i) && (n >> i & 1)) {
            printf("%d ", 1 << i);
        }
    }
    printf("\n");
    return 0;
}

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

int main() {
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);

    long long n, L, R;
    scanf("%lld%lld%lld", &n, &L, &R);

    if (R / n > L / n)          // 区间跨过了 n 的倍数
        printf("%lld\n", n - 1);
    else                        // 同一段内，取最大的 k
        printf("%lld\n", R % n);

    return 0;
}

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

const ll LIMIT = 1000000000LL;

int main() {
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);

    ll a, b;
    scanf("%lld%lld", &a, &b);

    ll ans = 1;
    for (ll i = 1; i <= b; ++i) {
        ans *= a;              // 最多到 1e9 * 1e9 = 1e18，long long 安全
        if (ans > LIMIT) {     // 一旦超过 1e9 立即报告
            printf("-1\n");
            return 0;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);

    ll n;
    scanf("%lld", &n);

    ll m = n, p = n;      // m: 当前苹果总数; p: 目标苹果当前位置
    ll day = 0, ansDay = 0;

    while (m > 0) {
        ++day;
        if (p % 3 == 1 && ansDay == 0) ansDay = day;   // 本轮被拿走

        m -= (m + 2) / 3;          // 每轮拿走 ceil(m/3) 个
        p -= (p + 2) / 3;          // 目标的新位置（减去排在它前面被拿走的）
    }
    printf("%lld %lld\n", day, ansDay);
    return 0;
}

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

int main() {
    freopen("poker.in", "r", stdin);
    freopen("poker.out", "w", stdout);

    int n;
    scanf("%d", &n);

    set<string> cards;
    char s[5];
    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        cards.insert(string(s));
    }
    printf("%d\n", 52 - (int)cards.size());
    return 0;
}

/* ---- 另一种写法：把牌编码成 0~51 的整数 ----
#include <bits/stdc++.h>
using namespace std;
bool have[55];
int main() {
    freopen("poker.in", "r", stdin);
    freopen("poker.out", "w", stdout);
    const string COL = "DCHS";          // 花色
    const string RANK = "A23456789TJQK"; // 点数
    int n; scanf("%d", &n);
    char s[5]; int cnt = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        int c = COL.find(s[0]);
        int r = RANK.find(s[1]);
        int id = c * 13 + r;
        if (!have[id]) { have[id] = true; ++cnt; }
    }
    printf("%d\n", 52 - cnt);
    return 0;
}
*/

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

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    string s, d;
    cin >> s;
    for (char c : s)
        if (c >= '0' && c <= '9')
            d.push_back(c);

    // 数字从大到小降序，保证拼出的数最大
    sort(d.begin(), d.end(), greater<char>());

    // 处理前导 0：把开头连续的 0 挪到第一个非零数字之后
    int p = 0;
    while (p < (int)d.size() && d[p] == '0') p++;
    if (p > 0 && p < (int)d.size()) {
        swap(d[0], d[p]);
    }

    cout << d << endl;
    return 0;
}

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

const int MAXN = 100005;
int type[MAXN], price[MAXN], t[MAXN];
int stopTime[MAXN];      // 优惠票失效时刻 = 乘地铁时刻 + 45
bool used[MAXN];         // 优惠票是否已被使用

int main() {
    freopen("transfer.in", "r", stdin);
    freopen("transfer.out", "w", stdout);

    int n;
    scanf("%d", &n);
    long long ans = 0;   // 总花费可能较大，用 long long 更稳
    int head = 1, tail = 0;   // 队列头尾指针

    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &type[i], &price[i], &t[i]);
        if (type[i] == 0) {                 // 坐地铁：花钱并产出一张优惠票
            ans += price[i];
            ++tail;
            stopTime[tail] = t[i] + 45;
            price[tail]   = price[i];
            used[tail]    = false;
        } else {                            // 坐公交
            while (head <= tail && stopTime[head] < t[i]) ++head;  // 丢弃过期票
            bool ok = false;
            for (int j = head; j <= tail; ++j) {
                if (!used[j] && price[j] >= price[i]) {  // 未用 + 票价足够
                    used[j] = true; ok = true; break;    // 用最早的那张
                }
            }
            if (!ok) ans += price[i];       // 无可用票则自费
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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

int cnt[605];   // 成绩桶：0 ~ 600

int main() {
    freopen("live.in", "r", stdin);
    freopen("live.out", "w", stdout);

    int n, w;
    scanf("%d%d", &n, &w);

    for (int p = 1; p <= n; ++p) {
        int x; scanf("%d", &x);
        cnt[x]++;

        int k = p * w / 100;          // 整数除法，避免浮点误差
        if (k < 1) k = 1;             // max(1, ...)

        int s = 0, ans = 0;
        for (int sc = 600; sc >= 0; --sc) {   // 从高到低累计
            s += cnt[sc];
            if (s >= k) { ans = sc; break; }
        }
        printf("%d ", ans);
    }
    printf("\n");
    return 0;
}

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

const int MAXN = 8005;
ll a[MAXN];
int rk[MAXN];      // rk[i]: 下标 i 的元素在稳定排序后的名次（1-based）
int ord[MAXN];     // 排序用的临时下标数组

int main() {
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);

    int n, Q;
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

    // 初始化：按 key(i) = (a[i], i) 稳定排序，得到初始名次
    for (int i = 1; i <= n; ++i) ord[i] = i;
    sort(ord + 1, ord + n + 1, [](int x, int y) {
        if (a[x] != a[y]) return a[x] < a[y];
        return x < y;
    });
    for (int r = 1; r <= n; ++r) rk[ord[r]] = r;

    while (Q--) {
        int op; scanf("%d", &op);
        if (op == 2) {
            int x; scanf("%d", &x);
            printf("%d\n", rk[x]);
        } else {
            int x; ll v; scanf("%d%lld", &x, &v);
            ll oldv = a[x];

            // 计算 delta：对每个 y != x，判断 x 是否跨过了 y
            int cntSmaller = 0;   // 新的 key(x) 之前有多少个元素
            for (int y = 1; y <= n; ++y) {
                if (y == x) continue;
                // cmp(va, ia, vb, ib): (va,ia) < (vb,ib)
                auto lessKey = [](ll v1, int i1, ll v2, int i2) {
                    if (v1 != v2) return v1 < v2;
                    return i1 < i2;
                };
                bool oldBefore = lessKey(oldv, x, a[y], y);   // 旧 key(x) < key(y)
                bool newBefore = lessKey(v,    x, a[y], y);   // 新 key(x) < key(y)

                if (oldBefore && !newBefore) rk[y] -= 1;      // x 从前面挪到了后面
                if (!oldBefore && newBefore) rk[y] += 1;      // x 从后面挪到了前面

                if (lessKey(a[y], y, v, x)) ++cntSmaller;     // 统计比新 key(x) 小的
            }
            rk[x] = cntSmaller + 1;   // x 的新名次
            a[x] = v;                 // 更新数组
        }
    }
    return 0;
}

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

// 返回 x 的整数平方根（向下取整），保证精确
ll isqrt(ll x) {
    if (x < 0) return -1;
    ll s = (ll)sqrtl((long double)x);
    while (s > 0 && s * s > x) --s;
    while ((s + 1) * (s + 1) <= x) ++s;
    return s;
}

int main() {
    freopen("decode.in", "r", stdin);
    freopen("decode.out", "w", stdout);

    int k;
    scanf("%d", &k);
    while (k--) {
        ll n, d, e;
        scanf("%lld%lld%lld", &n, &d, &e);

        ll m = n - e * d + 2;          // = p + q
        ll delta = m * m - 4 * n;      // = (p - q)^2

        if (delta < 0) { printf("NO\n"); continue; }
        ll s = isqrt(delta);
        if (s * s != delta) { printf("NO\n"); continue; }   // 不是完全平方数

        ll p = (m - s) / 2, q = (m + s) / 2;
        if ((m - s) % 2 != 0 || (m + s) % 2 != 0) { printf("NO\n"); continue; }
        if (p <= 0 || q <= 0) { printf("NO\n"); continue; }

        printf("%lld %lld\n", p, q);
    }
    return 0;
}

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

const int MAXN = 100005;
ll v[MAXN];       // 站点 i 到 i+1 的距离
ll a[MAXN];       // 站点 i 的油价
ll pre[MAXN];     // 距离前缀和
int nxt[MAXN];    // 右边第一个更便宜的站点

int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);

    int n; ll d;
    scanf("%d%lld", &n, &d);
    for (int i = 1; i <= n - 1; ++i) scanf("%lld", &v[i]);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

    for (int i = 1; i <= n - 1; ++i) pre[i] = pre[i - 1] + v[i];

    // 单调栈：求 i 右边第一个油价严格更低的站点
    stack<int> st;
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        nxt[i] = st.empty() ? n + 1 : st.top();
        st.push(i);
    }

    ll ans = 0, cur = 0;      // cur: 当前还能行驶的公里数
    for (int i = 1; i < n; ++i) {
        int j = nxt[i];                       // 目标站（可能是 n+1 表示终点）
        ll dist = pre[j - 1] - pre[i - 1];    // 从 i 到 j 的总距离
        if (cur < dist) {
            ll liters = (dist - cur + d - 1) / d;   // 需要补的整升油
            ans += liters * a[i];
            cur += liters * d;
        }
        cur -= v[i];                          // 开到下一站
    }
    printf("%lld\n", ans);
    return 0;
}

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

const int MAXN = 1005;
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
// 东(d=0) 南(d=1) 西(d=2) 北(d=3)
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int main() {
    freopen("explore.in", "r", stdin);
    freopen("explore.out", "w", stdout);

    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                vis[i][j] = false, mp[i][j] = 0;
        for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);

        int ans = 0;
        vis[x][y] = true; ++ans;              // 起点算经过

        for (int step = 0; step < k; ++step) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.') {
                x = nx; y = ny;               // 前进
                if (!vis[x][y]) { vis[x][y] = true; ++ans; }
            } else {
                d = (d + 1) % 4;              // 右转，原地不动
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

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

int main() {
    freopen("seat.in", "r", stdin);
    freopen("seat.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<int> a(n * m);
    for (int i = 0; i < n * m; ++i) cin >> a[i];

    int me = a[0];
    // 排名 = 严格大于 a1 的个数 + 1
    int rank = 1;
    for (int i = 0; i < n * m; ++i)
        if (a[i] > me) rank++;

    int k = rank - 1;        // 0 起始编号
    int c = k / n + 1;       // 第几列
    int t = k % n + 1;       // 列内从第 1 行数起的位置
    int r;
    if (c % 2 == 1) r = t;   // 奇数列：从上往下
    else            r = n - t + 1;  // 偶数列：从下往上（蛇形）

    cout << c << " " << r << endl;
    return 0;
}

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

const int MAXT = 105, MAXN = 105, MAXP = 10005;
int T, N, M;
int p[MAXT][MAXN];   // p[day][item]
int dp[MAXP];        // 完全背包

int main() {
    freopen("souvenir.in", "r", stdin);
    freopen("souvenir.out", "w", stdout);

    scanf("%d%d%d", &T, &N, &M);
    for (int i = 1; i <= T; ++i)
        for (int j = 1; j <= N; ++j)
            scanf("%d", &p[i][j]);

    for (int day = 1; day < T; ++day) {          // T-1 个子问题
        memset(dp, 0, sizeof(dp));
        for (int j = 1; j <= N; ++j) {           // 第 j 种纪念品
            int cost = p[day][j];
            int gain = p[day + 1][j] - p[day][j];
            if (gain <= 0) continue;             // 无收益不买
            for (int k = cost; k <= M; ++k)      // 完全背包：正序！
                dp[k] = max(dp[k], dp[k - cost] + gain);
        }
        M += dp[M];                              // 金币累积
    }
    printf("%d\n", M);
    return 0;
}

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

const int MAXS = 1000005;
int val[MAXS];        // 每个结点的值
int lc[MAXS], rc[MAXS];   // 左右儿子（0 表示无）
char op[MAXS];        // 结点的运算符：'&' '|' '!' 或 0 表示叶子
bool dead[MAXS];      // dead=1 表示该结点的值变化不影响根结点
int a[MAXS];          // 变量初值
char s[MAXS];

// 自顶向下打标记
void dfs(int u, bool flag) {   // flag: 该结点是否“无关”
    if (dead[u]) return;
    if (flag) { dead[u] = true; }
    if (lc[u] == 0 && rc[u] == 0) { if (flag) dead[u] = true; return; }
    if (op[u] == '!') {
        if (flag) dead[u] = true;
        dfs(lc[u], flag);
    } else if (op[u] == '&') {
        if (val[lc[u]] == 0) dfs(rc[u], true);   // 右儿子无关
        else                 dfs(rc[u], flag);
        if (val[rc[u]] == 0) dfs(lc[u], true);   // 左儿子无关
        else                 dfs(lc[u], flag);
    } else { // '|'
        if (val[lc[u]] == 1) dfs(rc[u], true);   // 右儿子无关
        else                 dfs(rc[u], flag);
        if (val[rc[u]] == 1) dfs(lc[u], true);   // 左儿子无关
        else                 dfs(lc[u], flag);
    }
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    // 读入整行表达式（第一行）
    int len = 0, c;
    while ((c = getchar()) != '\n' && c != EOF) s[++len] = (char)c;

    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    int cnt = 0;                 // 结点编号
    int st[MAXS], top = 0;       // 栈

    for (int i = 1; i <= len; ++i) {
        if (s[i] == ' ') continue;
        if (s[i] == 'x') {                       // 变量：读下标
            int k = 0, j = i + 1;
            while (j <= len && isdigit(s[j])) k = k * 10 + (s[j] - '0'), ++j;
            i = j - 1;
            int u = k;                           // 直接用变量下标作叶结点编号
            val[u] = a[k];
            op[u] = 0; lc[u] = rc[u] = 0;
            st[++top] = u;
        } else if (s[i] == '!') {                // 单目
            ++cnt;
            int u = MAXS - cnt;                  // 从数组尾部倒着分配编号
            lc[u] = st[top--]; rc[u] = 0;
            op[u] = '!';
            val[u] = !val[lc[u]];
            st[++top] = u;
        } else {                                 // 双目 & 或 |
            ++cnt;
            int u = MAXS - cnt;
            int b = st[top--], aa = st[top--];   // 先弹出的是右操作数
            lc[u] = aa; rc[u] = b;
            op[u] = s[i];
            val[u] = (s[i] == '&') ? (val[aa] & val[b]) : (val[aa] | val[b]);
            st[++top] = u;
        }
    }
    int root = st[top];
    int origin = val[root];

    dfs(root, false);

    int q; scanf("%d", &q);
    while (q--) {
        int x; scanf("%d", &x);
        if (dead[x]) printf("%d\n", origin);        // 翻转无影响
        else         printf("%d\n", origin ^ 1);    // 翻转根也翻转
    }
    return 0;
}

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

string s;

// 判断地址串 ad 是否规范
bool check(const string &ad) {
    int len = ad.size(), p = 0;
    int seg[5];

    for (int i = 0; i < 4; ++i) {
        int st = p;
        while (p < len && isdigit(ad[p])) ++p;
        if (p == st) return false;                       // 空段
        if (p - st > 1 && ad[st] == '0') return false;   // 前导 0
        long long v = 0;
        for (int k = st; k < p; ++k) v = v * 10 + (ad[k] - '0');
        if (v > 255) return false;
        seg[i] = (int)v;

        if (i < 3) {                                     // 前 3 段后必须是 '.'
            if (p >= len || ad[p] != '.') return false;
            ++p;
        }
    }
    if (p >= len || ad[p] != ':') return false;          // 第 4 段后必须是 ':'
    ++p;

    int st = p;
    while (p < len && isdigit(ad[p])) ++p;
    if (p == st) return false;                           // 端口为空
    if (p != len) return false;                          // 端口后不能有多余字符
    if (p - st > 1 && ad[st] == '0') return false;       // 端口前导 0
    long long e = 0;
    for (int k = st; k < p; ++k) e = e * 10 + (ad[k] - '0');
    if (e > 65535) return false;

    return true;
}

int main() {
    freopen("network.in", "r", stdin);
    freopen("network.out", "w", stdout);

    int n;
    scanf("%d", &n);

    unordered_map<string, int> server;   // 地址 -> 成功建立连接的服务机编号

    for (int i = 1; i <= n; ++i) {
        char op[20];
        scanf("%s", op);
        cin >> s;

        bool ok = check(s);
        if (!strcmp(op, "Server")) {
            if (!ok) { printf("ERR\n"); continue; }
            if (server.count(s)) { printf("FAIL\n"); }
            else { server[s] = i; printf("OK\n"); }
        } else {
            if (!ok) { printf("ERR\n"); continue; }
            if (server.count(s)) printf("%d\n", server[s]);
            else printf("FAIL\n");
        }
    }
    return 0;
}

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

const int MAXN = 2000005;
char s[MAXN];
int lc[MAXN], rc[MAXN], val[MAXN];
char op[MAXN];              // '0' '1' '&' '|'，0 表示叶子
int cnt = 0;                // 结点计数（叶子与内部结点共用编号，子结点编号一定小于父结点）
char ops[MAXN]; int optop = 0;      // 运算符栈，用 '(' 作分隔标记
int nodeStk[MAXN]; int ntop = 0;    // 操作数（结点）栈
bool reach[MAXN];           // 该结点是否真的会被求值（未被短路）
ll cntAnd = 0, cntOr = 0;

int prec(char c) { return c == '&' ? 2 : (c == '|' ? 1 : 0); }

void reduce() {             // 出栈一个运算符，合并两个操作数
    char c = ops[optop--];
    int r = nodeStk[ntop--];
    int l = nodeStk[ntop--];
    ++cnt;
    lc[cnt] = l; rc[cnt] = r; op[cnt] = c;
    val[cnt] = (c == '&') ? (val[l] & val[r]) : (val[l] | val[r]);
    nodeStk[++ntop] = cnt;
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    scanf("%s", s);
    int n = strlen(s);

    // ===== 第一步：中缀转表达式树（处理优先级与左结合）=====
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        if (c == '0' || c == '1') {
            ++cnt; op[cnt] = c; val[cnt] = c - '0';
            lc[cnt] = rc[cnt] = 0;
            nodeStk[++ntop] = cnt;
        } else if (c == '(') {
            ops[++optop] = '(';
        } else if (c == ')') {
            while (optop > 0 && ops[optop] != '(') reduce();
            --optop;                       // 弹出 '('
        } else {                           // '&' 或 '|'
            while (optop > 0 && ops[optop] != '('
                   && prec(ops[optop]) >= prec(c)) reduce();
            ops[++optop] = c;
        }
    }
    while (optop > 0) reduce();
    int root = nodeStk[ntop];

    // ===== 第二步：自顶向下标记“哪些结点会被真正求值” =====
    reach[root] = true;
    for (int u = cnt; u >= 1; --u) {       // 编号从大到小 => 先父后子
        if (!reach[u]) continue;
        if (lc[u] == 0 && rc[u] == 0) continue;   // 叶子，无子可标
        reach[lc[u]] = true;                      // 左操作数总要算
        if (op[u] == '&') {
            if (val[lc[u]] == 0) { ++cntAnd; reach[rc[u]] = false; }  // a=0 → &型短路
            else                 { reach[rc[u]] = true; }
        } else {                                  // '|'
            if (val[lc[u]] == 1) { ++cntOr;  reach[rc[u]] = false; }  // a=1 → |型短路
            else                 { reach[rc[u]] = true; }
        }
    }

    printf("%d\n%lld %lld\n", val[root], cntAnd, cntOr);
    return 0;
}

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

ll a, b, c, sigma;   // sigma = 较大根对应的符号

ll gcdll(ll x, ll y) { return y == 0 ? x : gcdll(y, x % y); }

// 输出有理数 num/den（已保证 den > 0），要求约分
string frac2str(ll num, ll den) {
    if (num == 0) return "0";
    ll g = gcdll(abs(num), abs(den));
    num /= g; den /= g;
    if (den < 0) { num = -num; den = -den; }
    if (den == 1) return to_string(num);
    return to_string(num) + "/" + to_string(den);
}

// 判断完全平方数并返回其平方根
bool perfectSqrt(ll x, ll &root) {
    if (x < 0) return false;
    ll s = (ll)sqrtl((long double)x);
    while (s > 0 && s * s > x) --s;
    while ((s + 1) * (s + 1) <= x) ++s;
    if (s * s == x) { root = s; return true; }
    return false;
}

int main() {
    freopen("uqe.in", "r", stdin);
    freopen("uqe.out", "w", stdout);

    int T; ll M;
    scanf("%d%lld", &T, &M);

    while (T--) {
        scanf("%lld%lld%lld", &a, &b, &c);
        sigma = (a > 0 ? 1 : -1);

        ll delta = b * b - 4 * a * c;
        if (delta < 0) { printf("NO\n"); continue; }

        ll root;
        if (perfectSqrt(delta, root)) {
            // ===== 有理根 =====
            ll num = -b + sigma * root;
            ll den = 2 * a;
            if (num == 0) { printf("0\n"); continue; }
            ll g = gcdll(abs(num), abs(den));
            num /= g; den /= g;
            if (den < 0) { num = -num; den = -den; }
            if (den == 1) printf("%lld\n", num);
            else          printf("%lld/%lld\n", num, den);
        } else {
            // ===== 无理根：拆分 Δ = s^2 * r =====
            ll rr = delta, s = 1;
            for (ll i = 2; i * i <= rr; ++i) {
                while (rr % (i * i) == 0) { rr /= i * i; s *= i; }
            }
            ll r = rr;                    // 无平方因子部分，r > 1

            // q1 = -b / (2a)，q2 = sigma * s / (2a)
            ll q1n = -b,        q1d = 2 * a;
            ll q2n = sigma * s, q2d = 2 * a;

            string out = "";
            if (q1n != 0) out += frac2str(q1n, q1d) + "+";

            // 约分 q2
            if (q2n != 0) {
                ll g = gcdll(abs(q2n), abs(q2d));
                q2n /= g; q2d /= g;
            }
            if (q2d < 0) { q2n = -q2n; q2d = -q2d; }

            if (q2n == 1 && q2d == 1) {
                out += "sqrt(" + to_string(r) + ")";
            } else if (q2d == 1) {
                out += to_string(q2n) + "*sqrt(" + to_string(r) + ")";
            } else if (q2n == 1) {
                out += "sqrt(" + to_string(r) + ")/" + to_string(q2d);
            } else {
                out += to_string(q2n) + "*sqrt(" + to_string(r) + ")/" + to_string(q2d);
            }
            printf("%s\n", out.c_str());
        }
    }
    return 0;
}

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

// 每个数字需要的小木棍数
const int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main() {
    freopen("sticks.in", "r", stdin);
    freopen("sticks.out", "w", stdout);

    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);

        if (n == 1) { printf("-1\n"); continue; }

        int d = (n + 6) / 7;              // 最少位数 = ceil(n / 7)
        string ans;
        int left = n;
        for (int i = 0; i < d; ++i) {
            int rest = d - i - 1;          // 后面还剩多少位
            for (int c = (i == 0 ? 1 : 0); c <= 9; ++c) {   // 首位从 1 开始
                int nl = left - cost[c];
                if (nl >= 2 * rest && nl <= 7 * rest) {     // 剩余木棍可被消化
                    ans += char('0' + c);
                    left = nl;
                    break;
                }
            }
        }
        printf("%s\n", ans.c_str());
    }
    return 0;
}

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

int main() {
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    unordered_set<int> S;
    S.insert(0);          // 空前缀异或为 0

    int cur = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        cur ^= x;
        if (S.count(cur ^ k)) {   // 存在 p 使 pre[p] = cur ^ k
            ans++;                // 得到一段异或和为 k 的区间
            S.clear();            // 重置：区间不能相交
            S.insert(0);
            cur = 0;
        } else {
            S.insert(cur);
        }
    }

    cout << ans << endl;
    return 0;
}

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

const int MAXN = 100005;
const int INF  = 0x3f3f3f3f;

vector<int> g[MAXN];
int dist[MAXN][2];      // dist[v][0]: 从 1 到 v 的偶最短路; [1]: 奇最短路

int main() {
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);

    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(dist, 0x3f, sizeof(dist));
    queue<pair<int,int>> Q;          // (点, 奇偶)
    dist[1][0] = 0;
    Q.push({1, 0});
    while (!Q.empty()) {
        int u = Q.front().first, p = Q.front().second; Q.pop();
        for (int v : g[u]) {
            if (dist[v][p ^ 1] > dist[u][p] + 1) {
                dist[v][p ^ 1] = dist[u][p] + 1;
                Q.push({v, p ^ 1});
            }
        }
    }

    while (q--) {
        int a, L; scanf("%d%d", &a, &L);
        int p = L & 1;                        // 需要的奇偶性
        if (L >= dist[a][p]) printf("Yes\n");
        else                 printf("No\n");
    }
    return 0;
}

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

const int MAXN = 1005;
const ll NEG = -(1LL << 60);

int n, m;
int a[MAXN][MAXN];
ll f[MAXN][MAXN][3];

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);

    // 第 1 列：只能自上而下
    f[1][1][0] = f[1][1][1] = f[1][1][2] = a[1][1];
    for (int i = 2; i <= n; ++i) {
        f[i][1][0] = f[i][1][1] = f[i][1][2] = f[i - 1][1][0] + a[i][1];
    }

    for (int j = 2; j <= m; ++j) {
        // 状态 0：自上而下到 (i,j)
        f[1][j][0] = f[1][j - 1][2] + a[1][j];
        for (int i = 2; i <= n; ++i)
            f[i][j][0] = max(f[i][j - 1][2], f[i - 1][j][0]) + a[i][j];

        // 状态 1：自下而上到 (i,j)
        f[n][j][1] = f[n][j - 1][2] + a[n][j];
        for (int i = n - 1; i >= 1; --i)
            f[i][j][1] = max(f[i][j - 1][2], f[i + 1][j][1]) + a[i][j];

        // 状态 2：两者取 max
        for (int i = 1; i <= n; ++i)
            f[i][j][2] = max(f[i][j][0], f[i][j][1]);
    }

    printf("%lld\n", f[n][m][2]);
    return 0;
}

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

const int MAXN = 200005;
int a[MAXN];
int nxt[MAXN], pre[MAXN];   // 双向链表，0 表示空
bool alive[MAXN];

int main() {
    freopen("fruit.in", "r", stdin);
    freopen("fruit.out", "w", stdout);

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i) {
        nxt[i] = (i == n ? 0 : i + 1);
        pre[i] = i - 1;
        alive[i] = true;
    }
    a[0] = -1;                 // 哨兵颜色，保证 1 号一定是块头

    // 初始所有块头
    vector<int> cur, nxtRound;
    for (int i = 1; i <= n; ++i)
        if (a[i] != a[pre[i]]) cur.push_back(i);

    while (!cur.empty()) {
        // 本轮块头即答案（编号天然递增）
        for (size_t k = 0; k < cur.size(); ++k)
            printf("%d%c", cur[k], k + 1 == cur.size() ? '\n' : ' ');

        // 按编号升序删除本轮块头；此时 pre[x] 一定指向“仍然存活”的前驱
        for (size_t k = 0; k < cur.size(); ++k) {
            int x = cur[k];
            int nx = nxt[x], pr = pre[x];
            if (pr) nxt[pr] = nx;      // pr 存活，安全
            else    nxt[0]  = nx;
            if (nx) pre[nx] = pr;
            alive[x] = false;          // 删除 x（x 的 nxt 保持不变，供回溯用）
        }

        // 为每个被删块头找“右边第一个存活元素”，它可能是下一轮的块头
        nxtRound.clear();
        for (size_t k = 0; k < cur.size(); ++k) {
            int y = nxt[cur[k]];
            while (y && !alive[y]) y = nxt[y];     // 跳过本轮被删的块头
            if (y == 0) continue;
            if (pre[y] == 0 || a[pre[y]] != a[y])  // 与新的前驱颜色不同 → 新块头
                nxtRound.push_back(y);
        }
        sort(nxtRound.begin(), nxtRound.end());
        nxtRound.erase(unique(nxtRound.begin(), nxtRound.end()), nxtRound.end());
        cur.swap(nxtRound);
    }
    return 0;
}

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

const int MAXN = 505, MAXK = 105;
struct Pt { ll x, y; } pt[MAXN];
int f[MAXN][MAXK];    // f[i][j]: 以 i 结尾、共使用 j 个自由点的最长链长

int main() {
    freopen("point.in", "r", stdin);
    freopen("point.out", "w", stdout);

    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &pt[i].x, &pt[i].y);

    sort(pt + 1, pt + n + 1, [](const Pt &A, const Pt &B) {
        if (A.x != B.x) return A.x < B.x;
        return A.y < B.y;
    });

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            f[i][j] = j + 1;               // 初值：从自由点一路走到 i
            for (int p = 1; p < i; ++p) {
                if (pt[p].x > pt[i].x || pt[p].y > pt[i].y) continue;   // 不可达
                ll d = (pt[i].x - pt[p].x) + (pt[i].y - pt[p].y);       // 曼哈顿距离
                int need = (int)d - 1;                                  // 需要补的点数
                if (need < 0) need = 0;
                if (need <= j)
                    f[i][j] = max(f[i][j], f[p][j - need] + (int)d);
            }
            ans = max(ans, f[i][j] + (k - j));   // 剩余自由点全部接在末尾
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

const int MAXN = 10005, MAXK = 105;
const ll INF = (1LL << 60);

struct Edge { int to; ll a; };
vector<Edge> g[MAXN];          // 原图：正向道路 u -> v，开放时间 a

// f[v][r]：倒着走时走到 v、当前时刻 t ≡ r (mod k)，则 t 至少要多大，
//          才能保证一路正着通过道路的时刻都不早于各自的开放时间。
ll f[MAXN][MAXK];

struct Node {
    ll t; int v, r;
    bool operator<(const Node &o) const { return t > o.t; }   // 小根堆
};

// 求最小的 >= x 且满足 ≡ r (mod k) 的数
ll ceilToMod(ll x, int r, int k) {
    ll add = ((r - x % k) % k + k) % k;
    return x + add;
}

int main() {
    freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);

    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i) {
        int u, v; ll a;
        scanf("%d%d%lld", &u, &v, &a);
        g[u].push_back({v, a});
    }

    for (int i = 1; i <= n; ++i)
        for (int r = 0; r < k; ++r)
            f[i][r] = INF;

    priority_queue<Node> pq;
    f[1][0] = 0;                     // 倒着走到入口且余数为 0：已完成，下界为 0
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int u = cur.v, r = cur.r;
        ll t = cur.t;
        if (t > f[u][r]) continue;   // 懒惰删除

        for (const Edge &e : g[u]) {
            int nv = e.to;
            int nr = (r + 1) % k;    // 往前退一步，余数 +1
            // 在 v 处的下界：既满足开放时间（t >= a），又比 u 处多走一步
            ll cand = ceilToMod(max(e.a + 1, t + 1), nr, k);
            if (cand < f[nv][nr]) {
                f[nv][nr] = cand;
                pq.push({cand, nv, nr});
            }
        }
    }

    if (f[n][0] >= INF) printf("-1\n");
    else                printf("%lld\n", f[n][0]);
    return 0;
}

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

const int MAXV = 200005, MAXR = 105;

vector<int> S[100005];
int buf1[MAXV], buf2[MAXV];      // 滚动数组：dp[r-1]、dp[r]
char ok[MAXR][MAXV];             // ok[r][v] = (dp[r][v] != -1)

int main() {
    freopen("chain.in", "r", stdin);
    freopen("chain.out", "w", stdout);

    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k, q;
        scanf("%d%d%d", &n, &k, &q);

        int maxv = 1;
        for (int i = 1; i <= n; ++i) {
            int l; scanf("%d", &l);
            S[i].resize(l);
            for (int j = 0; j < l; ++j) {
                scanf("%d", &S[i][j]);
                maxv = max(maxv, S[i][j]);
            }
        }

        int *pre = buf1, *cur = buf2;
        fill(pre, pre + maxv + 2, -1);
        pre[1] = -2;                                  // 第 0 轮：起点为 1，任何玩家都可以开第一轮

        memset(ok, 0, (size_t)MAXR * (maxv + 2));

        for (int r = 1; r <= 100; ++r) {
            fill(cur, cur + maxv + 2, -1);

            for (int i = 1; i <= n; ++i) {
                int l = (int)S[i].size();
                int cnt = 0;                          // 窗口内合法起点的个数
                for (int j = 0; j < l; ++j) {
                    if (j - 1 >= 0) {                 // 加入位置 j-1
                        int pv = pre[S[i][j - 1]];
                        if (pv == -2 || (pv >= 1 && pv != i)) ++cnt;
                    }
                    if (j - k >= 0) {                 // 移除位置 j-k
                        int pv = pre[S[i][j - k]];
                        if (pv == -2 || (pv >= 1 && pv != i)) --cnt;
                    }
                    if (cnt > 0) {                    // 第 i 个人可以让本轮以 S[i][j] 结尾
                        int v = S[i][j];
                        if (cur[v] == -1)                 cur[v] = i;
                        else if (cur[v] != i && cur[v] != -2) cur[v] = -2;
                    }
                }
            }

            for (int v = 1; v <= maxv; ++v)
                ok[r][v] = (cur[v] != -1) ? 1 : 0;

            swap(pre, cur);                           // 进入下一轮
        }

        while (q--) {
            int r, c;
            scanf("%d%d", &r, &c);
            if (r >= 1 && r <= 100 && c >= 1 && c <= maxv && ok[r][c]) printf("1\n");
            else                                                       printf("0\n");
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 5005;

int n;
ll a[MAXN], dp[MAXN];   // dp[j]: 当前前缀中选子集、和为 j 的方案数（j 截断到 maxA+1）

ll qpow(ll base, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    freopen("polygon.in", "r", stdin);
    freopen("polygon.out", "w", stdout);

    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; mx = max(mx, (int)a[i]); }
    sort(a + 1, a + n + 1);

    int M = mx + 1;        // 截断上界：任何和 > mx 都并到 mx+1
    dp[0] = 1;
    ll ans = 0, tot = 1;   // tot = 2^(i-1)，当前前缀子集总数

    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        // 不合法方案：和 <= x 的方案数（含选 0/1 根，它们都 <= x）
        ll bad = 0;
        for (int j = 0; j <= x; ++j) bad = (bad + dp[j]) % MOD;
        ll add = (tot - bad + MOD) % MOD;   // 合法方案 = 总方案 - 不合法
        ans = (ans + add) % MOD;

        // 把 a[i] 加入背包（逆序，超过 M 的并入 M）
        for (int j = M; j >= 0; --j) {
            if (!dp[j]) continue;
            int u = j + x;
            if (u > M) u = M;
            dp[u] = (dp[u] + dp[j]) % MOD;
        }
        tot = tot * 2 % MOD;
    }

    cout << ans % MOD << endl;
    return 0;
}