---
# System prepended metadata

title: 2020-2021 ACM-ICPC Nordic Collegiate Programming Contest

---

2020-2021 ACM-ICPC Nordic Collegiate Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105444/

比賽影片
---
{%youtube_w-7YBJZHdA%}

記分板
---
![image](https://hackmd.io/_uploads/S1tDMGFbke.png)


題解
---
### A. Array of Discord
---
#### 題目摘要
給一組非嚴格遞增的序列，問能不能改變一個數字的一個位數使得序列不非嚴格遞增並輸出解

#### 想法
$n^2$枚舉長度相同的數字，在枚舉位數看能不能讓兩個大小關係改變

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)

int len(ll x){
    int res=0;
    while(x){
        res++;
        x/=10;
    }
    return res;
}

void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    for(auto &x:a) cin >> x;
    for(int i=0;i<n;i++) for(int z=i-1;~z;--z){
        if (len(a[i])<=1&&len(a[z])<=1){
            if (a[z]!=0){
                for(int k=0;k<n;k++){
                    if (i==k) cout << 0 << ' ';
                    else cout << a[k] << ' ';
                }
                cout << '\n';
                return;
            }else if (a[i]!=9){
                for(int k=0;k<n;k++){
                    if (z==k) cout << 9 << ' ';
                    else cout << a[k] << ' '; 
                }
                cout << '\n';
                return;
            }
            continue;
        }
        if (len(a[i])==len(a[z])){
            int m=len(a[i]);
            ll div=10;
            for(int j=0;j<m;j++){
                ll tmp1=a[z]%div;
                ll tmp2=a[i]%div;
                tmp1/=(div/10);
                tmp2/=(div/10);
                tmp1*=(div/10);
                tmp2*=(div/10);
                if (tmp1!=0){
                    ll tmp=a[i]-tmp2+tmp1-(div/10);
                    if (len(tmp)!=m) continue;
                    if (tmp<a[z]){
                        for(int k=0;k<n;k++){
                            if (k==i) cout << tmp << ' ';
                            else cout << a[k] << ' ';
                        }
                        cout << '\n';
                        return;
                    }
                }else if (tmp2!=9*(div / 10)){
                    ll tmp=a[z]-tmp1+tmp2+(div/10);
                    if (len(tmp)!=m) continue;
                    if (tmp>a[i]){
                        for(int k=0;k<n;k++){
                            if (k==z) cout << tmp << ' ';
                            else cout << a[k] << ' '; 
                        }
                        cout << '\n';
                        return;
                    }
                }
                div*=10;
            }
        }
    }
    cout << "impossible\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### B. Big Brother
---
#### 題目摘要
求半平面交面積和

#### 想法
套模板

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll __int128
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define double long double

const ll LINF = 1e18 + 5;

struct pt {
    ll x, y;
};

struct Line {
    pt a, b;
};

pt operator + (pt a, pt b) {
    return {a.x + b.x, a.y + b.y};
}

pt operator - (pt a, pt b) {
    return {a.x - b.x, a.y - b.y};
}

ll operator ^ (pt a, pt b) {
    return a.x * b.y - a.y * b.x;
}

ll operator * (pt a, pt b) {
    return a.x * b.x + a.y * b.y;
}

pair<ll, ll> ap(Line a, Line b) {
    return {(a.b - a.a) ^ (b.a - a.a), (a.b - a.a) ^ (b.b - a.a)};
}

bool isin(Line l0, Line l1, Line l2) {
    auto [a02x, a02y] = ap(l0, l2);
    auto [a12x, a12y] = ap(l1, l2);
    if (a12x - a12y < 0) a12x *= -1, a12y *= -1;
    return a02y * a12x - a02x * a12y > 0;
}

const double eps = 1e-9;

int sign(double x) {
    return fabs(x) <= eps ? 0 : (x > 0 ? 1 : -1);
}

int pos(pt a) {
    return sign(a.y) == 0 ? sign(a.x) < 0 : a.y < 0;
}

int ori(pt o, pt a, pt b) {
    return sign((o - a) ^ (o - b));
}

vector<Line> HPI(vector<Line> arr) {
    sort(all(arr), [&](Line a, Line b) {
        pt A = a.b - a.a, B = b.b - b.a;
        if (pos(A) != pos(B)) return pos(A) < pos(B);
        if (sign(A ^ B) != 0) return sign(A ^ B) > 0;
        return ori(a.a, a.b, b.b) < 0;
    });
    deque<Line> dq(1, arr[0]);
    auto same = [&](pt a, pt b) {
        return sign(a ^ b) == 0 && pos(a) == pos(b);
    };
    for (auto p : arr) {
        if (same(dq.back().b - dq.back().a, p.b - p.a)) continue;
        while (dq.size() >= 2 && !isin(p, dq.end()[-2], dq.back())) dq.pop_back();
        while (dq.size() >= 2 && !isin(p, dq[0], dq[1])) dq.pop_front();
        dq.pb(p);
    }
    while (dq.size() >= 3 && !isin(dq[0], dq.end()[-2], dq.back())) dq.pop_back();
    while (dq.size() >= 3 && !isin(dq.back(), dq[0], dq[1])) dq.pop_front();
    return vector<Line>(all(dq));
}

void solve() {
    int n; cin >> n;
    vector<pt> p(n);
    for (auto &[x, y] : p) {
        int a, b; cin >> a >> b;
        x = a, y = b;
    }
    vector<Line> li;
    rep (i, 0, n) {
        if (p[i].x == p[(i - 1 + n) % n].x && p[i].y == p[(i - 1 + n) % n].y) continue;
        li.pb({p[i], p[(i - 1 + n) % n]});
    }
    if (li.size() <= 2) {
        cout << "0.00000\n";
        return;
    }
    // cout << li.size() << '\n';
    auto hull = HPI(li);
    // for (auto l : hull) cout << l.a.x << ' ' << l.a.y << " & " << l.b.x << ' ' << l.b.y << '\n';
    double A = 0;
    int sz = hull.size();
    auto calc = [&](Line x, Line y) -> pair<double, double> {
        if (x.a.x == x.b.x) {
            double m2 = 1.0 * (y.a.y - y.b.y) / (y.a.x - y.b.x);
            double k2 = y.a.y - m2 * y.a.x;
            return {x.a.x, m2 * x.a.x + k2};
        }
        if (y.a.x == y.b.x) {
            double m = 1.0 * (x.a.y - x.b.y) / (x.a.x - x.b.x);
            double k = x.a.y - m * x.a.x;
            return {y.a.x, m * y.a.x + k};
        }
        double m = 1.0 * (x.a.y - x.b.y) / (x.a.x - x.b.x);
        double m2 = 1.0 * (y.a.y - y.b.y) / (y.a.x - y.b.x);
        double k = x.a.y - m * x.a.x;
        double k2 = y.a.y - m2 * y.a.x;
        double X = 1.0 * (k - k2) / (m2 - m);
        double Y = m * X + k;
        return {X, Y};
    };
    vector<pair<double, double>> P;
    rep (i, 0, sz) {
        auto [x, y] = calc(hull[i], hull[(i + 1) % sz]);
        P.pb({x, y});
        // cout << x << ' ' << y << '\n';
    }
    rep (i, 0, sz) {
        auto [x, y] = P[i];
        auto [x2, y2] = P[(i + 1) % sz];
        A += x * y2 - x2 * y;
    }
    A = fabs(A);
    cout << fixed << setprecision(10) << 1.0 * A / 2 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### C. Coin Stacks
---
#### 題目摘要
給很多疊硬幣，每次可以選不同的兩疊各移除掉一個，問最後是否能移除全部，並輸出步驟
#### 想法
優先取現在能取的最大跟次大，這樣是好的，但我不會證明

小心他給你一疊大小為0的
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    rep (i, 0, n) cin >> a[i];
    vector<pii> ans;
    priority_queue<pii> pq;
    rep (i, 0, n) {
        if (a[i]) {
            pq.push({a[i], i});
        }
    }
    while (pq.size() > 1) {
        auto [b, i] = pq.top();
        pq.pop();
        auto [b2, i2] = pq.top();
        pq.pop();
        ans.pb({i, i2});
        b--, b2--;
        if(b) pq.push({b, i});
        if (b2) pq.push({b2, i2});
    }
    if (pq.empty()) {
        cout << "yes\n";
        for(auto [a, b] : ans) cout << min(a, b) + 1 << ' ' << max(a, b) + 1 << '\n';
    } else {
        cout << "no\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### D. Dams in Distress
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>

const ll LINF = 1e18 + 5;

void solve() {
    int n; ll w; cin >> n >> w;
    n++;
    vector<vector<int>> adj(n);
    vector<ll> d(n, 0), c(n, 0);
    c[0] = w;
    rep (i, 1, n) {
        int p; cin >> p >> c[i] >> d[i];
        adj[p].pb(i);
    }
    vector<ll> mx(n, 0), sum(n, 0);
    mx[0] = w;
    auto dfs = [&](auto self, int u) -> void {
        for (int v : adj[u]) {
            mx[v] = max(mx[u] - d[v], c[v] - d[v]);
            self(self, v);
        }
    };
    dfs(dfs, 0);
    ll ans = LINF;
    rep (i, 0, n) {
        ans = min(ans, mx[i]);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### E. Exhaustive Experiment
---
#### 題目摘要

#### 想法
將他給的範圍x擴大兩倍，發現他就是一個轉置45度後的四個象限，先處理一下變成熟悉的象限。
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n; cin >> n;
    vector<tuple<ll, ll, int>> pt(n);
    for (auto &[x, y, t] : pt) {
        ll X, Y; char c; cin >> X >> Y >> c;
        X *= 2;
        x = Y - X, y = X + Y;
        t = (isupper(c) ? (c == 'P' ? 1 : -1) : 0);
    }
    sort(all(pt));
    ll ln = LINF;
    map<pll, int> no; 
    for (auto [x, y, t] : pt) {
        if (t == 1) {
            if (ln <= y) {
                cout << "impossible\n";
                return;
            }
        } else if (t == -1) {
            chmin(ln, y);
        } else {
            if (y >= ln) {
                no[{x, y}] = 1;
            }
        }
    }
    sort(all(pt), greater<tuple<ll, ll, int>>());
    ll hp = -LINF, ans = 0, hnt = -LINF;
    for (auto [x, y, t] : pt) {
        if (t == 1) {
            if (chmax(hp, y)) {
                ans++;
                chmax(hp, hnt);
            }
        } else if (t == 0 && !no[{x, y}]) {
            chmax(hnt, y);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### F. Film Critics
---
#### 題目摘要
給長度$n$的序列$a$，可以任意排列$a$，並有一套評分系統，若在第$i$項之前的分數平均小於$a_i$會得到$0$分，否則得到$m$分，問能不能找到一組排列能拿到恰$k$分

#### 想法
先判掉$k$不是$m$的倍數，並將$p$設成$\frac{k}{m}$。
先將評分系統改成問$i\times a_i$(0-base)是否大於等於$i$之前的分數和，再觀察$a$，能發現會得到$m$分的要是前$p$大的數(若比較小的數在某位置能得到$m$分，那比較大的數在相同位置也能得到$m$分)，並將$a_i$分成兩組，前$p$大要從小到大排序，前$(n-p)$小是由大到小，最後再從位置由小到大跑，並記錄這位置之前的分數和，若能放下前$p$大的就放，否則就放前$(n-p)$小的，若連前$(n-p)$小的也放不下的就無解

前$p$大能由小到大排序：
假設有兩數$a_k與a_{k+1},\ a_k<a_{k+1}$並兩數都屬於前$p$大，倘若$a_{k+1}放在p_1,\ a_k放在p_2且p_1<p_2$，則$\exists p_3\in (p_1,\ p2),\ p_4\in (p_3, p_2]$使條件滿足，因為$p_4$有機率比$p_2$小，所以從小到大的排序比較好

:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second

void _solve(){
    int n, m, k;
    cin >> n >> m >> k;
    set<pii> st;
    vector<int> a(n+1);
    vector<pii> vec(n);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        vec[i-1]={a[i], i};
    }
    if (k%m!=0){
        cout << "impossible\n";
        return;
    }
    sort(vec.begin(), vec.end(), greater<pii>());
    vector<pii> g1, g2;
    k/=m;
    for(int i=0;i<k;i++) g1.push_back(vec[i]);
    for(int i=k;i<n;i++) g2.push_back(vec[i]);
    sort(g1.begin(), g1.end(), greater<pii>());
    sort(g2.begin(), g2.end());
    int d=0;
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        if (!g1.empty()&&i*g1.back().F>=d){
            ans[i]=g1.back().S;
            g1.pop_back();
            d+=m;
        }else{
            if (g2.empty()||i*g2.back().F>=d){
                cout << "impossible\n";
                return;
            }
            ans[i]=g2.back().S;
            g2.pop_back();
        }
    }
    for(int i=0;i<n;i++) cout << ans[i] << ' ';
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}
```
:::

### G. Gig Combinatorics
---
#### 題目摘要
給一序列元素只有1, 2, 3，問有多少子序列滿足頭是1，尾是3，且中間數字都是2

#### 想法
先算頭是1尾是3且中間可以有2或沒2的數量，再減掉頭1尾3中間沒東西的數量就好

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)

const ll mod=1e9+7;

void solve() {
    int n; cin >> n;
    vector<int> a(n+1, 0);
    for(int i=1;i<=n;i++) cin >> a[i];
    ll ans=0, sum=0;
    for(int i=1;i<=n;i++){
        if (a[i]==1){
            sum=(sum+1)%mod;
        }else if (a[i]==2){
            sum=sum*2%mod;
        }else{
            ans=(ans+sum)%mod;
        }
    }
    sum=0;
    for(int i=1;i<=n;i++){
        if (a[i]==1){
            sum=(sum+1)%mod;
        }else if (a[i]==3){
            ans=(ans-sum+mod)%mod;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### H. Hiring and Firing
---
#### 題目摘要
每天都有一個HR員工開除人或招募人，為避免尷尬不能讓HR員工開除他招募的人，問在開除順序是後招募先開除的情況下，最少需要多少位HR員工

#### 想法

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n; cin >> n;
    vector<vector<int>> adj(n), adj2(n);
    vector<int> st;
    vector<int> h(n);
    rep (i, 0, n) {
        int f; cin >> f >> h[i];
        while (f) {
            int tmp = min(f, h[st.back()]);
            f -= tmp;
            h[st.back()] -= tmp;
            adj[st.back()].pb(i);
            adj2[st.back()].pb(i);
            adj2[i].pb(st.back());
            if (h[st.back()] == 0) st.pop_back();
        }
        if (h[i]) st.pb(i);
    }
    auto check_one = [&]() -> bool {
        bool f = 1;
        rep (i, 0, n) f &= adj[i].empty();
        if (f) {
            cout << 1 << '\n';
            rep (i, 0, n) cout << 1 << ' ';
            return true;
        }
        return false;
    };
    auto check_two = [&]() -> bool {
        vector<int> col(n, -1);
        bool f = 0;
        auto dfs = [&](auto self, int u, int pa) -> void {
            for (int v : adj2[u]) {
                if (v == pa) continue;
                if (col[v] == -1) {
                    col[v] = col[u] ^ 1;
                    self(self, v, u);
                } else if (col[v] == col[u]) f = 1;
            }
        };
        rep (i, 0, n) if (col[i] == -1) {
            col[i] = 0;
            dfs(dfs, i, -1);
            if (f) return false;
        }
        cout << 2 << '\n';
        rep (i, 0, n) cout << col[i] + 1 << ' ';
        return true;
    };
    if (check_one()) return;
    if (check_two()) return;
    vector<int> col(n, -1), it(n);
    rep (i, 0, n) it[i] = adj[i].size() - 1;
    auto work = [&](auto self, int st) -> void {
        while (it[st] >= 0) {
            int nxt = adj[st][it[st]];
            if (col[nxt] == -1) {
                if (it[nxt] >= 0 && col[adj[nxt][it[nxt]]] != -1) {
                    col[nxt] = ((col[st] + 1) ^ (col[adj[nxt][it[nxt]]] + 1)) - 1;
                    if (col[nxt] == -1) {
                        col[nxt] = (col[st] + 1) % 3;
                    }
                } else {
                    col[nxt] = (col[st] + 1) % 3;
                }
            }
            it[st]--;
            self(self, nxt);
        }
    };
    rep (i, 0, n) if (col[i] == -1) {
        if (it[i] >= 0 && col[adj[i][it[i]]] != -1) {
            col[i] = (col[adj[i][it[i]]] + 1) % 3;
        } else {
            col[i] = 0;
        }
        work(work, i);
    }
    cout << 3 << '\n';
    rep (i, 0, n) cout << col[i] + 1 << ' ';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### I. Infection Estimation
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=
```
:::

### J. Joining Flows
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>

const ll LINF = 1e18 + 5;

void solve() {
    int n;
    cin >> n;
    vector<tuple<ll, ll, ll>> v(n);
    for(auto &[t, a, b]:v) cin >> t >> a >> b;
    int q;
    cin >> q;
    vector<tuple<ll, ll, int>> qry(q);
    for(int i=0;i<q;i++){
        auto &[b, a, c]=qry[i];
        cin >> a >> b;
        a*=b;
        c=i;
    }
    sort(qry.begin(), qry.end());
    vector<ll> ans(q);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq2;
    priority_queue<pair<ll, ll>> pq;
    for (auto [t, a, b] : v) {
        pq.push({t, b - a});
        pq2.push({t, b - a});
    }
    ll F = 0, L = 0, R = 0, mxxxxf = 0;
    for (auto [t, a, b] : v) {
        L += t * a;
        R += t * a;
        mxxxxf += b;
        F += a;
    }
    for(auto [f, t, idx]:qry){
        if (f < F || F > mxxxxf) {
            ans[idx] = 0;
            continue;
        }
        ll d=f-F, tmp = d;
        while(!pq.empty() && tmp){
            auto [t, l] = pq.top();
            pq.pop();
            ll mi = min(l, tmp);
            R += t * mi;
            tmp -= mi;
            l -= mi;
            if (l) pq.push({t, l});
        }
        tmp = d;
        while(!pq2.empty() && tmp) {
            auto [t, l] = pq2.top();
            pq2.pop();
            ll mi = min(l, tmp);
            L += t * mi;
            tmp -= mi;
            l -= mi;
            if (l) pq2.push({t, l});
        }
        ans[idx] = (t >= L && t <= R);
        F=f;
    }
    rep (i, 0, q) cout << (ans[i] ? "yes\n" : "no\n");

}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::

### K. Keep Calm And Carry Off
---
#### 題目摘要
給兩大數，問讓兩數加減$X$使得最後兩數相加不進位的最小$X$

#### 想法
找到被進位影響的最高位，將小於等於最高位的位數都設0，最高位數+1的數+1，在用大數減法求$X$，兩個大數都做一遍取min

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    string a, b; cin >> a >> b;
    reverse(all(a));
    reverse(all(b));
    while (a.size() < b.size()) a.pb('0');
    while (b.size() < a.size()) b.pb('0');
    int n = a.size();
    string ans = "";
    rep (PEPPA, 0, 2) {
        int car = n;
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] - '0' + b[i] - '0' >= 10) {
                car = i;
                break;
            }
        }
        if (car == n) {
            cout << '0' << '\n';
            return;
        }
        while (car + 1 < n && a[car + 1] - '0' + b[car + 1] - '0' == 9) car++;
        string sub(car + 1, '0'), res = "";
        if (car == n - 1) sub.pb('1');
        else sub.pb(a[car + 1] + 1);
        rep (i, car + 2, n) sub.pb(a[i]);
        int carry = 0;
        rep (i, 0, n) {
            if (sub[i] - a[i] - carry < 0) res.pb(sub[i] - a[i] - carry + 10 + '0'), carry = 1;
            else res.pb(sub[i] - a[i] - carry + '0'), carry = 0;
        }
        while (res.back() == '0') res.pop_back();
        reverse(all(res));
        if (ans.empty()) ans = res;
        else {
            if (res.size() < ans.size()) ans = res;
            else if (res.size() == ans.size()) {
                rep (i, 0, res.size()) {
                    if (res[i] != ans[i]) {
                        ans = (res[i] < ans[i] ? res : ans);
                        break;
                    } 
                }
            }
        }
        swap(a, b);
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### L. Language Survey
---
#### 題目摘要
給一個n\*m的圖，有三種顏色，若圖上的點為1，代表他要恰被一個顏色塗；若為2，代表他要被至少兩個顏色塗，並且每個顏色塗過的區域要洽為一個連通塊，輸出著色方法

#### 想法
考慮另一個問題：能不能將這張圖切成三個顏色的連通塊，並且沒有一個點的周圍沒有與自己顏色不同的點。

假設能做到這個問題，那麼原來的問題就變很簡單了。

將那張圖畫上去，對於一個2的點，去找他四周其中一個與他顏色不同的點將那個顏色塗到這個點，因為這張的圖的性質因此一定找的到一個點，如此一來就結束了。

要能構造上面的圖，也許有很多方法，總之我跟官解一樣。先特判n = 1或m = 1，將最左邊一列塗上A，將B指在右上角， C指在右下角，開始繞一個螺旋，特別注意要好好繞，不要讓邊邊疊兩行一樣顏色的爛掉

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
 
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};

void solve() {
    int n, m; cin >> n >> m;
    vector<string> g(n);
    vector<vector<string>> G(3, vector<string>(n, string(m, '.')));
    rep (i, 0, n) cin >> g[i];
    if (n == 1) {
        int cnt = 0;
        rep (i, 0, m) {
            if (g[0][i] == '2' && (i == 0 || g[0][i - 1] == '1')) cnt++;
            if (cnt >= 3) break;
            if (g[0][i] == '2') G[cnt][0][i] = 'A' + cnt;
            G[0][0][i] = 'A';
        }
        if ((cnt == 0 && n * m < 3) || cnt >= 3) {
            cout << "impossible\n";
            return;
        }
        if (cnt == 0) {
            G[1][0][0] = 'B';
            G[2][0][1] = 'C';
            G[0][0][0] = G[0][0][1] = '.';
        } else if (cnt == 1) {
            rep (i, 0, m) if (g[0][i] == '2') {
                G[1][0][i] = 'B';
                G[2][0][i] = 'C';
            }
        }
        rep (i, 0, 3) {
            rep (j, 0, n) cout << G[i][j] << '\n';
            cout << '\n';
        }
        return;
    }
    if (m == 1) {
        int cnt = 0;
        rep (i, 0, n) {
            if (g[i][0] == '2' && (i == 0 || g[i - 1][0] == '1')) cnt++;
            if (cnt >= 3) break;
            if (g[i][0] == '2') G[cnt][i][0] = 'A' + cnt;
            G[0][i][0] = 'A';
        }
        if ((cnt == 0 && n * m < 3) || cnt >= 3) {
            cout << "impossible\n";
            return;
        }
        if (cnt == 0) {
            G[1][0][0] = 'B';
            G[2][1][0] = 'C';
            G[0][0][0] = G[0][1][0] = '.';
        } else if (cnt == 1) {
            rep (i, 0, n) if (g[i][0] == '2') {
                G[1][i][0] = 'B';
                G[2][i][0] = 'C';
            }
        }
        rep (i, 0, 3) {
            rep (j, 0, n) cout << G[i][j] << '\n';
            cout << '\n';
        }
        return;
    }
    rep (i, 0, n) G[2][i][0] = 'C';
    rep (i, 1, m) G[0][0][i] = 'A';
    rep (i, 1, n) G[1][i][m - 1] = 'B';
    int x = 1, y = m - 1, cur = 0;
    vector<int> d(2);
    d[0] = m - 3, d[1] = n - 3;
    while (d[0] > 0 || d[1] > 0) {
        rep (i, 0, d[cur & 1]) {
            x += dx[cur];
            y += dy[cur];
            G[1][x][y] = 'B';
        }
        d[cur & 1] -= 2;
        cur = (cur + 1) % 4;
    }
    rep (i, 0, n) rep (j, 0, m) if (G[1][i][j] == '.' && G[2][i][j] == '.') G[0][i][j] = 'A';
    rep (i, 0, n) rep (j, 0, m) if (g[i][j] == '2') {
        rep (k, 0, 4) {
            int nx = i + dx[k], ny = j + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            rep (l, 0, 3) if (G[l][i][j] == '.' && G[l][nx][ny] != '.') {
                G[l][i][j] = 'A' + l;
            }
        }
    }
    rep (i, 0, 3) {
        rep (j, 0, n) cout << G[i][j] << '\n';
        cout << '\n';
    }
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### M. Methodic Multiplication
---
#### 題目摘要
x\*S(y) = S(y\*x)，x+S(y) = S(x+y)
#### 想法
觀察水題，每\*一次會複製一次x或y，加法會把兩邊的S()數量加在一起形成一坨S()，所以總共會有x數量\*y數量個S()
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for(int a = b; a < c; a++)
string a, b;
int cnt1 =0, cnt2=0, cnt;
void solve() {
    cin >> a >> b;
    rep(i,0,a.size()){
        if(a[i]=='S'){
            cnt1++;
            i++;
        }else if(a[i]==0){
            break;
        }
    }
    rep(i,0,b.size()){
        if(b[i]=='S'){
            cnt2++;
            i++;
        }else if(b[i]==0){
            break;
        }
    }
    if(cnt1 > cnt2) swap(cnt1,cnt2);
    cnt2*=cnt1;
    rep(i,0,cnt2) cout << "S(";
    cout << 0;
    rep(i,0,cnt2) cout << ")";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::