2023-2024 ICPC East North America Regional Contes
===
比賽鏈結
---
https://codeforces.com/gym/104757

比賽影片
---
{%youtube 3QJwOU6foY4 %}

記分板
---

題解
---
### A. A Pivotal Question
---
#### 題目摘要
給一個序列$a$，看有多少位置滿足在$i$之前的所有元素$\le a_i$，在$i$之後所有元素$>a_i$，超過100個的話只要輸出前100項

#### 想法
只要維護前綴max和後綴min就好，但我記成都是區間的了QAQ

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int a[N];
int mx[30][N], mn[30][N];
int lg[N];

int _MAX(int l, int r){
    int t=lg[r-l];
    return max(mx[t][l], mx[t][r-(1<<t)]);
}

int _MIN(int l, int r){
    int t=lg[r-l];
    return min(mn[t][l], mn[t][r-(1<<t)]);
}

void solve(){
    int n;
    cin >> n;
    lg[1]=0;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=0;i<n;i++){
        cin >> a[i];
        mn[0][i]=mx[0][i]=a[i];
    }
    for(int i=1;i<25;i++){
        for(int j=0;j<n;j++) if (j+(1<<i)<=n){
            mx[i][j]=max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]);
            mn[i][j]=min(mn[i-1][j], mn[i-1][j+(1<<(i-1))]);
        }
    }
    vector<int> ans;
    if (_MIN(1, n)>a[0]) ans.push_back(a[0]);
    for(int i=1;i<n-1;i++){
        if (_MIN(i+1, n)>a[i]&&_MAX(0, i)<=a[i]) ans.push_back(a[i]);
    }
    if (_MAX(0, n-1)<=a[n-1]) ans.push_back(a[n-1]);
    if (ans.size()>=100){
        cout << ans.size() << ' ';
        for(int i=0;i<100;i++) cout << ans[i] << ' ';
        cout << '\n';
    }else{
        cout << ans.size() << ' ';
        for(auto x:ans) cout << x << ' ';
        cout << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### B. B Road Band
---
#### 題目摘要
兩條道路上面分別有些房子，道路相距$s$，兩條道路正中間會有$k$個存取點，題目要最小化距離$\sum ((房子x座標-最近的存取點x座標)^2+(\frac{s}{2})^2)$
#### 想法
首先，能把$(\frac{s}{2})^2$提出來，所以僅需處理剩下的部分。可以先對所有房子的x座標排序，再設$dp_{i,\ j}$為第$i$個房子前用了$j$個存取點的距離，因此能列出轉移式$dp_{i,\ j}=\min_\limits{0\le k<i}dp_{k,\ j-1}+\sum_\limits{k<t\le i}(x_t-p_j)^2\ (x是房子座標，p是存取點要放哪)$
而目前問題是$p$要放哪，注意到$\sum (x_t-p_j)^2$，僅與變異數差一個倍數，因此也能將$p_j帶x的平均數$，化減後變$\sum x_t^2-(i-j)*\mu^2,\ \mu=\frac{\sum x_t}{i-j}$，因此僅需記座標的前綴和與座標平方的前綴和就好，複雜度$O(k(n+m)^2)$
:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
typedef long double ld;

const int N=2005;
ld dp[N][105], p[N], pre[N], sq[N];

void solve(){
    int n, m, k;
    ld s;
    cin >> n >> m >> k >> s;
    p[0]=0;
    for(int i=1;i<=n+m;i++) cin >> p[i];
    sort(p+1, p+n+m+1);
    for(int i=1;i<=n+m;i++) pre[i]=pre[i-1]+p[i], sq[i]=sq[i-1]+p[i]*p[i];
    for(int i=0;i<=n+m;i++) for(int j=0;j<=k;j++) dp[i][j]=1e18;
    for(int j=0;j<=k;j++) dp[0][j]=0.0;
    for(int c=1;c<=k;c++){
        for(int i=1;i<=n+m;i++){
            for(int j=0;j<i;j++){
                ld avg=(pre[i]-pre[j])/(i-j);
                dp[i][c]=min(dp[i][c], dp[j][c-1]+(sq[i]-sq[j])-(i-j)*avg*avg);
            }
        }
    }
    cout << dp[n+m][k]+(s/2)*(s/2)*(n+m) << '\n';
}

int main(){
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### C. Convex Hull Extension
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### D. Cornhusker
---
#### 題目摘要
超長閱讀水題。
#### 想法

$\lfloor\frac{N \times\lfloor\frac{\sum\limits^5_{i = 0}A_iL_i}{5}\rfloor}{KWF}\rfloor$

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long

const int N=1e6+10;

void solve(){
    ll sum = 0;
    rep (i, 0, 5) {
        ll a, b; cin >> a >> b;
        sum += a * b;
    }
    sum /= 5;
    int s, t; cin >> s >> t;
    sum *= s;
    sum /= t;
    cout << sum << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### E. Prof.~Fumblemore and the Collatz Conjecture
---
#### 題目摘要
\begin{equation}
C(n)=
\begin{cases}
\frac{n}{2} & \text{n is even} \\
3n + 1 & \text{n is odd} \\
\end{cases}
\end{equation}

$CS(n) = n,\ C(n),\ C(C(n)),\ \cdots$
$CST(n)$是第一個出現二的次方前的$CS(n)$以EO代表偶奇的字串
給你一個字串$s$求最小可能的$n$使得$CST(n) = s$
若無法則輸出INVALID
#### 想法
先將一看就不可能的字串排除(結尾是E/有連續兩個O)
由於知道最後要是2的次方倍
枚舉所有有機會的結尾反著推出原本的n
只要過程中都符合沒有二的次方以及都是正整數就是一個可能的答案
把所有可行答案取最小的
最後檢查答案有沒有在題目要求的$2^{47}$內
注意檢查的時候可能會噴到int128

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define all(x) (x).begin(), (x).end()

const int N=1e6+10;
const ll LINF = 1e18 + 5;

void solve(){
    string s; cin >> s;
    auto out = [&]() -> void {
        cout << "INVALID\n";
        exit(0);
    };
    if (s.back() == 'E') {
        out();
    }
    int n = s.size();
    rep (i, 0, n - 1) {
        if (s[i] == s[i + 1] && s[i] == 'O') out();
    }
    ll cur = 3;
    reverse(all(s));
    auto check = [&](__int128 cur) -> ll {
        bool f = 1;
        rep (i, 0, n) {
            if (s[i] == 'E') {
                int cnt = 0;
                cur *= 2;
                __int128 pp = cur;
                while (pp) {
                    cnt += pp & 1;
                    pp >>= 1;
                }
                if (cnt == 1) {
                    f = 0;
                    break;
                }
            }
            else {
                cur--;
                if (cur % 3) {
                    f = 0;
                    break;
                }
                else cur /= 3;
                if (cur <= 1) {
                    f = 0;
                    break;
                }
            }
        }
        if (cur > __int128(1) << 47) f = 0;
        if (f) return cur;
        else return 0;
    };
    ll ans = LINF, tmp = 0;
    rep (i, 0, 70) if (tmp = check(__int128(1) << i)) {
        ans = min(ans, tmp);
        tmp = 0;
    }
    if (ans == 0) out();
    else cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### F. Double Up
---
#### 題目摘要
給你一個陣列裡面值全是2的次方
你有兩種操作：
1. 將相鄰相同的數字合起來變原先值的兩倍
2. 刪掉這個數字

可以執行任意次，求最後能夠造出來最大的值。
#### 想法

值域超級大，要開int128
枚舉次方從小到大，將現在開到的次方可以合就合，不能就刪掉
最後剩下那個數字就會是最大的
我是用link-list做的，但應該隨便暴力亂開陣列都行

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long

const int N=1e6+10;

void read(__int128 &x) {
    x = 0;
    int f = 1;
    char ch;
    if((ch = getchar()) == '-') f = -f;
    else x = x * 10 + ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9')
        x = x * 10 + ch - '0';
    x *= f;
}

void print(__int128 x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

void solve(){
    __int128 n; read(n);
    vector<__int128> a(n + 2, 0);
    rep (i, 1, n + 1) read(a[i]);
    // rep (i, 1, n + 1) print(a[i]);
    vector<int> pre(n + 2, -1), nxt(n + 2, 0);
    rep (i, 1, n + 1) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[0] = 1;
    pre[n + 1] = n;
    int len = n;
    __int128 cur = 1;
    while (len > 1) {
        int st = nxt[0];
        while (st != n + 1) {
            // cerr << st << '\n';
            if (a[st] == cur) {
                if (a[nxt[st]] == a[st]) {
                    a[st] *= 2;
                    pre[ nxt[ nxt[st] ] ] = st;
                    nxt[st] = nxt[nxt[st]];
                } else {
                    pre[ nxt[ st ] ] = pre[st];
                    nxt[ pre[ st ] ] = nxt[st];
                }
                len--;
            }
            st = nxt[st];
        }
        cur *= 2;
    }
    print(a[nxt[0]]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### G. Forest for the Trees
---
#### 題目摘要
有$n_s$棵樹並給所有樹的座標，有個機器人會從一點往四方位其中一方向觀察曼哈頓距離$\le r$的樹，並已知觀察到的所有樹有$n_t$個並給所有相對於機器人的相對座標，問機器人的所在位置在哪(要判無解及多組解)，並且機器人位置不能有樹
#### 想法
枚舉$n_s$代表一個觀察到的樹的位置，並用相對座標看原本的位置有沒有樹，最後再檢查曼哈頓距離$\le r$的樹是否都被觀察到，若以上都符合，則這是其中一組解。接下來再對$n_t$左轉$90°$重複以上動作4次就好，注意判有沒有點時要用unordered_map，不然會吃T

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define all(x) (x).begin(), (x).end()
typedef pair<ll, ll> pii;
#define F first
#define S second

const int N=5005;

pii operator +(const pii a, const pii b){return {a.F+b.F, a.S+b.S};}
pii operator -(const pii a, const pii b){return {a.F-b.F, a.S-b.S};}

inline int dis(pii a, pii b){return abs(a.F-b.F)+abs(a.S-b.S);}

inline ll H(pii a){
    a = a + make_pair(300000, 300000);
    return a.F * 600000 + a.S;
}

pii p1[N], p2[N];
bool vis[N];
unordered_map<ll, int> mp;

int ns, nt, r;
int cnt=0;
pii ans;
void _solve(){
    for(int i=0;i<ns;i++){
        bool phlag=1;
        for(int j=0;j<nt;j++){
            pii tmp=p1[i]+p2[j]-p2[0];
            if (mp[H(tmp)] == 0) phlag=0;
            else{
                vis[mp[H(tmp)] - 1]=1;
            }
        }
        if (phlag){
            bool flag=1;
            pii o=p1[i]-p2[0];
            for(int j=0;j<ns;j++) if (!vis[j]){
                if (dis(o, p1[j])<=r) flag=0;
            }
            if (flag){
                cnt++;
                ans=o;
                if (cnt >= 2) return;
            }
        }
        for(int j=0;j<ns;j++) vis[j]=0;
    }
}

void solve(){
    cin >> ns >> nt >> r;
    for(int i=0;i<ns;i++) cin >> p1[i].F >> p1[i].S;
    for(int j=0;j<nt;j++) {
        cin >> p2[j].F >> p2[j].S;
        if (p2[j].F == 0 && p2[j].S == 0) {
            cout << "Impossible\n";
            return;
        }
    }
    for(int i=0;i<ns;i++) mp[H(p1[i])]=i + 1;
    rep (i, 0, 2) {
        rep (j, 0, 2) {
            _solve();
            rep (k, 0, nt) swap(p2[k].F, p2[k].S);
            rep (k, 0, nt) p2[k].S = -p2[k].S;
        }
    }
    if (cnt==0){
        cout << "Impossible\n";
    }else if (cnt==1){
        cout << ans.F << ' ' << ans.S << '\n';
    }else{
        cout << "Ambiguous\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::

### H. Impartial Strings
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### I. ISBN Conversion
---
#### 題目摘要
先判斷輸入是否符合ISBN-10，若符合，輸出它的ISBN-13
#### 想法
噁心人的實作，把case判好就好

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    string s;
    cin >> s;
    int cnt=0;
    int n=s.size();
    bool phlag=(s[0]!='-'&&s.back()!='-');
    vector<int> d;
    for(int i=0;i<n;i++){
        if (s[i]=='-'){
            cnt++;
            if (i!=n-1&&s[i+1]=='-') phlag=0;
        }else if (s[i]=='X'){
            if (i!=n-1) phlag=0;
        }else{
            d.push_back(s[i]-'0');
        }
    }
    if (cnt==3){
        if (s[n-2]!='-') phlag=0;
    }else if (cnt>3) phlag=0;
    if (d.size()==9){
        ll sum=0;
        for(int i=2;i<=10;i++){
            sum+=1LL*i*d[10-i];
        }
        int x=0;
        for(;x<=10;x++){
            if ((sum+x)%11==0) break;
        }
        if (x!=10) phlag=0;
    }else if (d.size()==10){
        ll sum=0;
        for(int i=1;i<=10;i++){
            sum+=1LL*i*d[10-i];
        }
        if (sum%11!=0) phlag=0;
        d.pop_back();
    }else{
        phlag=0;
    }
    if (!phlag){
        cout << "invalid" << '\n';
        return;
    }
    cout << "978-";
    for(int i=0;i<n-1;i++) cout << s[i];
    ll sum=0;
    d.insert(d.begin(), 8);
    d.insert(d.begin(), 7);
    d.insert(d.begin(), 9);
    n=d.size();
    for(int i=0;i<n;i++){
        if (i&1) sum+=3*d[i];
        else sum+=d[i];
    }
    int x=0;
    for(;x<10;x++) if ((sum+x)%10==0) break;
    cout << x << '\n';
}

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

:::

### J. Pearls
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### K. Split Decisions
---
#### 題目摘要
問$n$個字串中有幾對字串$s,\ t$滿足長度相同，且有一個$j$滿足$s_j\not =t_j且s_{j-1}\not =t_{j-1}且若i\not =j,\ j-1，則s_i=t_i$，並只有一對解滿足上述情況。像若5個字串CELL, GULL, GUSH, HALL, HASH，[CE/GU]__ 成立因為__只能填LL，而__[SH/LL]不成立因為__能填GU或HA

#### 想法
用tuple+map算數量

:::spoiler 實作

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

const int N=1505;
string s[N];

map<tuple<int, int, char, char, char, char>, int> mp;

void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> s[i];
    for(int a=0;a<n;a++){
        for(int b=a+1;b<n;b++) if(s[a].size()==s[b].size()){
            int sz=s[a].size();
            int cnt=0;
            for(int i=0;i<sz;i++) cnt+=(s[a][i]==s[b][i]);
            if (cnt==(sz-2)){
                for(int i=1;i<sz;i++){
                    if (s[a][i]!=s[b][i]&&s[a][i-1]!=s[b][i-1]){
                        pair<char, char> p1, p2;
                        p1={s[a][i-1], s[a][i]};
                        p2={s[b][i-1], s[b][i]};
                        if (p1.F>p2.F) swap(p1, p2);
                        else if (p1.F==p2.F&&p1.S>p2.S) swap(p1, p2);
                        mp[{sz, i, p1.F, p1.S, p2.F, p2.S}]++;
                        break;
                    }
                }
            }
        }
    }
    ll ans=0;
    for(auto it:mp) if (it.second==1) ans++;
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

:::
### L. A (Fast) Walk in the Woods
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::