---
# System prepended metadata

title: 2022-2023 ACM-ICPC German Collegiate Programming Contest

---

2022-2023 ACM-ICPC German Collegiate Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/104059

比賽影片
---
{%youtube Ha2ssG90SQo%}

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



題解
---
### A. Alternative Architecture
---
#### 題目摘要
給樂高的長寬，問可以擺出多少不同方向，擺放的方位必須讓樂高角角的圓對到後面超大樂高的圓
#### 想法
就是兩邊要做出相似直角三角形，直接報搜，注意邊長矩形的，三角形的斜邊要減1

:::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++)

map<ll, bool> mp;

void solve() {
    ll a, b;
    cin >> a >> b;
    a--, b--;
    ll g=__gcd(a, b);
    if (a<b) swap(a, b);
    ll aa=a/g, bb=b/g;
    for(ll i=1;i<=a;i++) mp[i*i]=1;
    ll ans=0;
    for(ll i=1;i<=b;i++){
        ll c=b*b-i*i;
        if (mp[c]){
            c=sqrtl(c);
            if ((i%bb==0)&&(c%bb==0)){
                ll ii=i/bb*aa;
                ll cc=c/bb*aa;
                if (ii*ii+cc*cc==a*a) ans++;
            }
        }
    }
    ans++;
    if (a!=b) ans<<=1;
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### B. Breeding Bugs
---
#### 題目摘要
給一堆數字，找到一個集合使當中兩兩元素和不為質數
#### 想法

去除掉$1 + 1 = 2$的case，發現可以奇偶建二分圖，最大獨立集 = N - 最小點覆蓋，最小點覆蓋又等於最大匹配，因此跑一次最大匹配就好，至於1的case可以選擇在一堆1中只留下一個1建圖

實作寫了一般圖最大匹配，但其實不需要

:::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 int ll

struct Matching {
    int n, tk;
    vector<vector<int>> g;
    vector<int> fa, pre, match, s, t;
    queue<int> q;
    int find(int u) {
        return u == fa[u] ? fa[u] : fa[u] = find(fa[u]);
    }
    int lca(int a, int b) {
        tk++;
        a = find(a), b = find(b);
        for (;;swap(a, b)) {
            if (a != n) {
                if (t[a] == tk) return a;
                t[a] = tk;
                a = find(pre[match[a]]);
            }
        }
    }
    void blossom(int x, int y, int l) {
        while (find(x) != l) {
            pre[x] = y;
            y = match[x];
            if (s[y] == 1) q.push(y), s[y] = 0;
            if (fa[x] == x) fa[x] = 1;
            if (fa[y] == y) fa[y] = 1;
            x = pre[y];
        }
    }
    bool bfs(int r) {
        iota(all(fa), 0);
        fill(all(s), -1);
        while (!q.empty()) q.pop();
        q.push(r);
        s[r] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int u : g[x]) {
                if (s[u] == -1) {
                    pre[u] = x;
                    s[u] = 1;
                    if (match[u] == n) {
                        for (int a = u, b = x, last; b != n; a = last, b = pre[a]) {
                            last = match[b], match[b] = a, match[a] = b;
                        }
                        return true;
                    }
                    q.push(match[u]);
                    s[match[u]] = 0;
                } else if (!s[u] && find(u) != find(x)) {
                    int l = lca(u, x);
                    blossom(x, u, l);
                    blossom(u, x, l);
                }
            }
        }
        return false;
    }
    int solve() {
        int res = 0;
        for (int x = 0; x < n; x++) {
            if (match[x] == n) res += bfs(x);
        }
        return res;
    }
    void add_edge(int u, int v) {
        g[u].pb(v);
        g[v].pb(u);
    }
    Matching (int _n) : n(_n), tk(0), g(n), fa(n + 1), pre(n + 1, n), match(n + 1, n), s(n + 1), t(n) {}
};

const int N=2e7+10;
bool isp[N];
vector<int> prime;

void solve() {
    for(int i=2;i<=20000000;i++){
        if (!isp[i]) prime.push_back(i);
        for(auto x:prime){
            if (x*i>20000000) break;
            isp[x*i]=1;
            if (i % x==0) break;
        }
    }
    int n; cin >> n;
    vector<int> p;
    int one = 0;
    rep (i, 0, n) {
        int a; cin >> a;
        if (a == 1 && one) continue;
        p.pb(a);
        if (a == 1) one = 1;
    }
    n = p.size();
    vector<vector<int>> adj(n);
    Matching G(n);
    rep (i, 0, n) {
        rep (j, i + 1, n) {
            if (!isp[p[i] + p[j]]) {
                G.add_edge(i, j);
            }
        }
        if (p[i] == 1) one = 1;
    }
    cout << n - G.solve()  << '\n';
}

main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### C. Chaotic Construction
---
#### 題目摘要
給一環狀區間，有兩種操作
1. 把某個點破壞或回複
2. 詢問兩個位置是不是連通的
#### 想法
將每個點設為1，用BIT單點修改區間詢問
檢查順著跑或逆著跑有沒有區間和等於區間長度就好

:::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 int MAXN = 1e5 + 5;
int n;

int BIT[MAXN];

void mod(int x, int val) {
    while (x <= n) {
        BIT[x] += val;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += BIT[x];
        x -= x & -x;
    }
    return res;
}

void solve() {
    int m; cin >> n >> m;
    rep (i, 0, n) mod(i + 1, 1);
    while (m--) {
        char c; cin >> c;
        if (c == '?') {
            int a, b; cin >> a >> b;
            if (a > b) swap(a, b);
            int ch = query(b) - query(a - 1), ch2 = query(n) - query(b - 1) + query(a);
            if (ch == b - a + 1 || ch2 == n - (b - a + 1) + 2) cout << "possible\n";
            else cout << "impossible\n";
        } else {
            int a; cin >> a;
            mod(a, c == '+' ? 1 : -1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### D. Diabolic Doofenshmirtz
---
#### 題目摘要
互動題，每次詢問n會回傳n除以x的餘數，求x
(詢問最多42次，詢問的點要遞增)
#### 想法
42好log，來二分搜
二分搜$x$，若沒有要遞增，直接搜到第一個$n \ \% \ x\not=n$的$n$就好
然而要遞增，可以再每次$n \ \% \ x\not=n$時，將新的起點設成$b=n-(n \ \% \ x)$，每次再檢查$b+mid$是否為$b+((b+mid) \ \% \ x)$就好

:::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++)
 
ll query(ll x){
    cout << "? " << x << endl;
    ll res;
    cin >> res;
    return res;
}
 
void solve() {
    ll l=1, r=1e12+1;
    ll b=0;
    while(l<r){
        ll m=(l+r>>1);
        ll x=query(b+m);
        if (b+x!=b+m) r=m ,b=b+m-x;
        else l=m+1;
    }
    cout << "! " << l << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### E. Enjoyable Entree
---
#### 題目摘要
有A湯與B湯，第一天A湯有100，B湯0，第二天A湯有0，B湯100，之後兩湯的量是前一天湯加前二天湯的平均，求第$n$天兩碗湯分別的量
#### 想法
兩湯和為100，所以只要做一邊
A湯的遞迴是為
\begin{cases}
F(1)=100\\
F(2)=0\\
F(n)=\frac{F(n-1)+F(n-2)}{2}\ (n>2)
\end{cases}
注意到$n$到$10^6$時已經收斂了，只要遞迴跑到$10^6$，剩下都是$\frac{100}{3}$，B湯就是100-A湯
:::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 int N=1e6+10;
long double f[N];

void solve() {
    ll n; cin >> n;
    f[1]=100, f[2]=0;
    for(int i=3;i<=1000000;i++){
        f[i]=(f[i-1]+f[i-2])/2;
    }
    cout << fixed << setprecision(10);
    if (n>1000000){
        cout << 100.0/3 << ' ' << 200.0/3 << '\n';
    }else{
        cout << f[n] << ' ' << 100.0-f[n] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### F. Formula Flatland
---
#### 題目摘要
找所有點度數不小於3的圖的最小環

#### 想法
每次從度數最小點建外指的邊能構出出入不大於5的DAG，並且環的可能答案只有3、4、5(我也不知道為什麼QAQ)，找出3環4環的所有case再做有限bfs就好

:::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, m; cin >> n >> m;
    rep (i, 0, n) {
        int x, y; cin >> x >> y;
    }
    vector<vector<int>> tmp(n), adj(n);
    vector<pii> edge;
    vector<int> deg(n, 0);
    rep (i, 0, m) {
        int a, b; cin >> a >> b;
        a--, b--;
        edge.pb({a, b});
        tmp[a].pb(i);
        tmp[b].pb(i);
        deg[a]++;
        deg[b]++;
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<bool> vis(m, 0);
    rep (i, 0, n) pq.push({deg[i], i});
    while (!pq.empty()) {
        auto [d, i] = pq.top();
        pq.pop();
        if (d != deg[i] || d == 0) continue;
        for (int id : tmp[i]) {
            if (vis[id]) continue;
            vis[id] = 1;
            int v = (i ^ edge[id].F ^ edge[id].S);
            adj[i].pb(v);
            deg[v]--;
            if (deg[v]) pq.push({deg[v], v});
        }
        deg[i] = 0;
    }
    vector dis(n, vector<int>(4, 0));
    int ans = 5;
    rep (i, 0, n) {
        queue<pii> q;
        set<int> reach;
        q.push({i, 0});
        dis[i][0] = 1;
        reach.insert(i);
        while (!q.empty()) {
            auto [u, d] = q.front();
            q.pop();
            for (int v : adj[u]) {
                reach.insert(v);
                rep (k, 1, 4) if (dis[v][k]) {
                    chmin(ans, d + 1 + k);
                }
                dis[v][d + 1] = 1;
                if (d < 2) q.push({v, d + 1});
            }
        }
        for (int v : reach) rep (j, 0, 4) dis[v][j] = 0;
    }
    set<pii> st;
    rep (i, 0, n) {
        int sz = adj[i].size();
        rep (j, 0, sz) rep (k, 0, j) {
            if (st.count({minmax(adj[i][j], adj[i][k])})) {
                chmin(ans, 4);
            }
            st.insert(minmax(adj[i][j], adj[i][k]));
        } 
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::
### G. Guessing Game
---
#### 題目摘要
題目狗幹長，總之有$n$個人，有七天每天有$d_i$場比賽，每個人會對每天的其中一場比賽做出預測(yes or no)，猜對會得一分，你會預測最後兩天的各一場比賽，問你有沒有機會贏其他人。
#### 想法
首先先觀察到我要贏的話要讓兩場都猜對，那麼代表其他人的答對題數不能超過一場，因此會發現這是一個2-SAT問題。
對於每一個人，要求其不能贏超過一場，意思就是他猜的七場中任兩場取反的or不能是0也就是：
$\Rightarrow\bigwedge\limits_{1\le i<j\le7}(\neg P_i \ \vee \ \neg P_j)$
那整個題目加上一定要取那兩個的條件就可以寫成：
$\Rightarrow P_1 \ \wedge \ P_2 \wedge \bigwedge\limits_{k=1}^n\bigwedge\limits_{i=1}^7\bigwedge\limits_{j=i+1}^7(\neg P_{ki} \ \vee \ \neg P_{kj})$
根據2-SAT的概念來建圖跑SCC就好。
其中一定要取的那兩個點可以用$(P_1 \vee P_1) \wedge (P_2 \vee P_2)$來表示

:::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<int> d(8, 0);
    rep (i, 1, 8) cin >> d[i];
    rep (i, 1, 8) d[i] += d[i - 1];
    int m = d[7];
    auto op = [&](int x) -> int {
        return x >= m ? x - m : x + m;
    };
    vector b(n, vector<int>(7));
    rep (i, 0, n) {
        rep (j, 0, 7) {
            cin >> b[i][j];
            if (b[i][j] < 0) b[i][j] = -b[i][j] + m;
            b[i][j]--;
            b[i][j] += d[j]; 
        }
    }
    vector<vector<int>> adj(m << 1);
    int px, py; cin >> px >> py;
    if (px < 0) px = -px + m;
    px--;
    px += d[5]; 
    if (py < 0) py = -py + m;
    py--;
    py += d[6]; 
    adj[op(px)].pb(px);
    adj[op(py)].pb(py);
    rep (i, 0, n) {
        int pre = 0;
        rep (j, 0, 7) rep (k, 0, 7) if (j != k) {
            adj[b[i][j]].pb(op(b[i][k]));
        }
    }
    int cnt = 0, sccid = 0;
    vector<int> dfn(m << 1, 0), low(m << 1, 0), scc(m << 1, 0);
    vector<bool> inst(m << 1, 0);
    stack<int> st;
    auto dfs = [&](auto self, int u) -> void {
        st.push(u);
        inst[u] = true;
        dfn[u] = low[u] = ++cnt;
        for(int v : adj[u]){
            if(!inst[v] && dfn[v]) continue;
            if(!dfn[v]) self(self, v);
            chmin(low[u], low[v]);
        }
        if(low[u] == dfn[u]){
            sccid++;
            while(st.top() != u){
                inst[st.top()] = false;
                scc[st.top()] = sccid;
                st.pop();
            }
            scc[u] = sccid;
            inst[u] = false;
            st.pop();
        }
    };
    rep(i, 0, m << 1){
        if(!dfn[i]) dfs(dfs, i);
    }
    rep (i, 0, m) {
        if (scc[i] == scc[i + m]) {
            cout << "impossible\n";
            return;
        }
    }
    cout << "possible\n";
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::
### H. Hardcore Hangman
---
#### 題目摘要
有一個答案字串，由小寫字母組成，可以做7次詢問，每次可以詢問多個字母，會給你出現的位置，猜答案算是一個操作
#### 想法
有點分治的概念，可以用交集來找出現的數字，然後不斷的往下切，可以參考一下圖片。
![image](https://hackmd.io/_uploads/ryDbkbsAA.png)
但賽中debug太慢，哭了
`後來發現可以好好的切塊(用bit看)，不用用我的怪切法`

:::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++)
set<int> st1[26], st2[26], st3[26], st4[26];
void solve() {
    int n;
    cout << "? abcdefghijklvwx" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a; a--;
        st1[0].insert(a);
    }
    cout << "? ghijklmnopqr" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a; a--;
        if(st1[0].find(a)!=st1[0].end()){
            st1[0].erase(a);
            st1[1].insert(a);
        }else{
            st1[2].insert(a);
        }
    }
    cout << "? defghi" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a;a--;
        if(st1[0].find(a)!=st1[0].end()){
            st2[1].insert(a);
            st1[0].erase(a);
        }else{
            st2[2].insert(a);
            st1[1].erase(a);
        }
    }
    for(auto v : st1[0]) st2[0].insert(v);
    for(auto v : st1[1]) st2[3].insert(v);
    cout << "? pqrstuvwx" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a;a--;
        if(st1[2].find(a)!=st1[2].end()){
            st2[5].insert(a);
            st1[2].erase(a);
        }else{
            st2[6].insert(a);
        }
    }
    for(auto v : st1[2]) st2[4].insert(v);
    vector<int> todel;
    for(auto v : st2[6]){
        if(st2[0].find(v)!=st2[0].end()){
            st2[0].erase(v);
            todel.push_back(v);
            st2[7].insert(v);
        }
    }
    for(auto v : todel){
        st2[6].erase(v);
    }
    // rep(i,0,8){
    //     for(auto v : st2[i]) cout << v << ' ';
    //     cout << '\n';
    // }
    // good above
    cout << "? bcefhiklnoqrtuwxz" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a;
        a--;
        if(st2[0].find(a)!=st2[0].end()){
            st2[0].erase(a);
            st3[1].insert(a);
        }else if(st2[1].find(a)!=st2[1].end()){
            st2[1].erase(a);
            st3[3].insert(a);
        }else if(st2[2].find(a)!=st2[2].end()){
            st2[2].erase(a);
            st3[5].insert(a);
        }else if(st2[3].find(a)!=st2[3].end()){
            st2[3].erase(a);
            st3[7].insert(a);
        }else if(st2[4].find(a)!=st2[4].end()){
            st2[4].erase(a);
            st3[9].insert(a);
        }else if(st2[5].find(a)!=st2[5].end()){
            st2[5].erase(a);
            st3[11].insert(a);
        }else if(st2[6].find(a)!=st2[6].end()){
            st2[6].erase(a);
            st3[13].insert(a);
        }else if(st2[7].find(a)!=st2[7].end()){
            st2[7].erase(a);
            st3[15].insert(a);
        }else{
            st4[25].insert(a);
        }
    }
    rep(i,0,8){
        for(auto v : st2[i]) {st4[i*3].insert(v);}
    }
    // rep(i,0,18){
    //     cout << 30+i << ' ';
    //     for(auto v : st3[i]){
    //         cout << v << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << "? behknqtwy" << endl;
    cin >> n;
    rep(i,0,n){
        int a; cin >> a;
        a--;
        if(st3[1].find(a)!=st3[1].end()){
            st3[1].erase(a);
            st4[1].insert(a);
        }else if(st3[3].find(a)!=st3[3].end()){
            st3[3].erase(a);
            st4[4].insert(a);
        }else if(st3[5].find(a)!=st3[5].end()){
            st3[5].erase(a);
            st4[7].insert(a);
        }else if(st3[7].find(a)!=st3[7].end()){
            st3[7].erase(a);
            st4[10].insert(a);
        }else if(st3[9].find(a)!=st3[9].end()){
            st3[9].erase(a);
            st4[13].insert(a);
        }else if(st3[11].find(a)!=st3[11].end()){
            st3[11].erase(a);
            st4[16].insert(a);
        }else if(st3[13].find(a)!=st3[13].end()){
            st3[13].erase(a);
            st4[19].insert(a);
        }else if(st3[15].find(a)!=st3[15].end()){
            st3[15].erase(a);
            st4[22].insert(a);
        }else{
            st4[24].insert(a);
        }
    }
    int cnt =1;
    rep(i,1,16){
        for(auto v : st3[i]) {st4[i+cnt].insert(v);}
        i+=1;
        cnt++;
    }
    vector<int> ans(100000,-1);
    // rep(i,0,26){
    //     for(auto v : st4[i]){
    //         cout << v << ' ';
    //     }
    //     cout << '\n';
    // }
    rep(i,0,26){
        for(auto v: st4[i]){
            ans[v]=i;
        }
    }
    cout << "! ";
    for(auto v:ans){
        if(v==-1) break;
        cout << char('a'+v);
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
// 4 2 5 6 7
// 4 1 3 4 6
// 2 2 6
// 3 1 3 4
// 1 2
// 2 2 8
```
:::
### I. Improving IT
---
#### 題目摘要
有$n$個月，每個月會有一個CPU能買，在$m$個月內要賣出(不含買它的月)，若要買新的CPU要先把手上的賣掉再買，第$n+1$個月會賣出手上的CPU。你每個月都要有一個CPU，求最小成本
#### 想法
先設$a_{i,\ j}$為第$i$個CPU買後$j$月的售價，當$j=0$時是買入價格，$dp_{i}$為第$i$的最小成本，能列出轉移式
\begin{equation}
dp_{i}=\min\limits_{max(1,\ i-m)\le j<i}dp_{j}-a_{i,\ i-j}+a_{i,\ 0}
\end{equation}
跑完在把第$n+1$月賣掉就好
:::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 LINF=1e18+10;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> a(n+1, vector<ll>(m+1));
    for(int i=1;i<=n;i++){
        cin >> a[i][0];
        for(int j=1;j<=min(m, n-i+1);j++){
            cin >> a[i][j];
        }
    }
    vector<ll> dp(n+1, LINF);
    dp[1]=a[1][0];
    for(int i=2;i<=n;i++){
        for(int j=max(1, i-m);j<i;j++){
            dp[i]=min(dp[i], dp[j]-a[j][i-j]);
        }
        dp[i]+=a[i][0];
    }
    ll ans=LINF;
    for(int j=max(1, n+1-m);j<n+1;j++){
        ans=min(ans, dp[j]-a[j][n-j+1]);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### J. Jesting Jabberwocky
---
#### 題目摘要
給長度為$N$的字串，有四種花色，你要做些交換讓他一樣花色的都排在一起，排序的方法是把一個花色拿出來移動到任意位置，求最小交換次數
#### 想法

由於花色沒有大小之分，可以把每一種排列都枚舉過一次
要最小交換次數，可以觀察到等於最大化不需要移動的點，也就是非嚴格的LIS
答案就會是最小的N-LIS
:::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 int ll

const int MAXN = 1e5 + 5;
const ll LINF = 1e18 + 5;

string t = "hdsc";

void solve() {
    string s; cin >> s;
    int n = s.size();
    vector<int> rk(4);
    iota(all(rk), 0);
    map<char, int> mp;
    ll ans = LINF;
    do {
        rep (i, 0, 4) mp[t[i]] = rk[i];
        vector<int> lis;
        rep (i, 0, n) {
            auto it = upper_bound(all(lis), mp[s[i]]);
            if (it == lis.end()) lis.pb(mp[s[i]]);
            else *it = mp[s[i]];
        }
        ans = min(ans, n - (int)lis.size());
    } while (next_permutation(all(rk)));
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}
```
:::
### K. K.O. Kids
---
#### 題目摘要
給你一個2xn的矩陣，每個矩陣只有一個是安全(可能左邊或右邊)，每次都會走另外一邊，除非他不安全就繼續往前，如果有一個人失敗就換下一個，給你安全的路徑，問一開始先選左邊的話會有幾個小孩安全過去。
#### 想法
直接實作，想清楚下一次的case就好。

:::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 n,k;
void solve() {
    string s;
    cin >> n >> k >> s;
    char now = 'L'; int cnt = 0;
    for(auto c : s){
        if(now=='L'){
            if(c=='R'){
                cnt++;
                now='L';
            }else{
                now='R';
            }
        }else{
            if(c=='L'){
                cnt++;
                now='R';
            }else{
                now='L';
            }
        }
    }
    k<cnt?cout<<0:cout<<k-cnt;
}

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

```
:::
### L. Lots of Land
---
#### 題目摘要
$ℓ\times w$的土地要平均分給$n$人，求其中一組解，若無解輸出IMPOSSIBLE
#### 想法
先判$ℓ\times w$是否整除$n$，若否則無解。再求$ℓ與n的gcd$，代表$ℓ$要放多少人，$\frac{n}{gcd}$的部分是$w$要放多少人，因此只要讓$n$個人都有$\frac{ℓ}{gcd}\times \frac{w}{\frac{n}{gcd}}$面積就好

:::spoiler 實作

```cpp=
```
:::
### M. Mirror Madness
---
#### 題目摘要
給一個多邊形，它的每條邊都是平行$x$軸或$y$軸，並且邊上點的數量不超過$10^6$。給一個起點(保證在邊上)，你會往$(1,\ 1)$的方向射光線，當碰到邊就會反射，題目保證光線不會碰到多邊形角落，問前$m$次碰到邊的點為何

#### 想法
光束只會有$x+y=k與x-y=k$的形式，並且一碰到牆就會換成另一種直線，可以讓每條線記錄所有在這條邊上的多邊形上的點(因為最多只有$10^6$個)並排序，接下來直接從起點直接跑就好。對於一條線從一個點下一次撞牆的點要算一下，當我目前位置是那條線的奇數項(0-base)，我下一個點是我前一位，反之後一位

:::spoiler 實作

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

const int N=4e6+10, B=2000000;
vector<int> v1[N], v2[N];
pii p[500005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> p[i].F >> p[i].S;
    for(int i=0;i<n;i++){
        int j=(i+1)%n;
        if (p[i].F==p[j].F){
            int d=(p[i].S<p[j].S)?1:-1;
            for(int k=p[i].S;k!=p[j].S;k+=d){
                v1[p[i].F-k+B].push_back(p[i].F);
                v2[p[i].F+k+B].push_back(p[i].F);
            }
        }else{
            int d=(p[i].F<p[j].F)?1:-1;
            for(int k=p[i].F;k!=p[j].F;k+=d){
                v1[k-p[i].S+B].push_back(k);
                v2[k+p[i].S+B].push_back(k);
            }
        }
    }
    for(int i=0;i<=4000000;i++){
        sort(v1[i].begin(), v1[i].end());
        sort(v2[i].begin(), v2[i].end());
    }
    int x, y;
    cin >> x >> y;
    for(int i=0;i<m;i++){
        if (i&1){
            int tmp=x+y+B;
            int j=lower_bound(v2[tmp].begin(), v2[tmp].end(), x)-v2[tmp].begin();
            if (j&1) j--;
            else j++;
            x=v2[tmp][j];
            y=tmp-x-B;
        }else{
            int tmp=x-y+B;
            int j=lower_bound(v1[tmp].begin(), v1[tmp].end(), x)-v1[tmp].begin();
            if (j&1) j--;
            else j++;
            x=v1[tmp][j];
            y=x+B-tmp;
        }
        cout << x << ' ' << y << '\n';
    }
}
```
:::
