---
# System prepended metadata

title: 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest

---

2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest
===
比賽鏈結
---
https://codeforces.com/gym/102460/ 

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

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


題解
---
### A. Rush Hour Puzzle
---
#### 題目摘要
有至多10台車，垂直或水平地擺放至6 $\times$ 6的平面中，並定義出口在第3列的最右邊，車子有分兩種，長度2或3的。而你的目標是在10步內將1號車(長度為2)出去，問能不能達成
#### 想法
隱式圖，把每一種車子擺列狀況當成狀態，題目可以轉換成把目標車移出去的最短路
首先，我們可以去掉最後移出的兩步，再來，觀察到車子的狀態不會太多，所以直接BFS亂做就好
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
 
void solve() {
    vector a(6, vector<int>(6, 0));
    int mx = 0;
    rep (i, 0, 6) rep (j, 0, 6) {
        cin >> a[i][j];
        mx = max(mx, a[i][j]);
    }
    vector<pair<pii, pii>> car(mx + 1); 
    pii h = {-1, -1}, t;
    rep (i, 0, 6) rep (j, 0, 6) {
        if (a[i][j] == 1) {
            t = {i, j};
            if (h.F == -1) h = t;
        }
    }
    if (h.F != 2 || t.F != 2) {
        cout << -1 << '\n';
        return;
    }
    if (a[2][4] == 1 && a[2][5] == 1) {
        cout << 2 << '\n';
        exit(0);
    }
    map<vector<vector<int>>, int> mp;
    queue<pair<vector<vector<int>>, int>> q;
    q.push({a, 0});
    mp[a] = 1;
    while (!q.empty()) {
        auto [cur, d] = q.front();
        q.pop();
        auto check = [&]() -> void {
            if (cur[2][4] == 1 && cur[2][5] == 1) {
                cout << d + 2 << '\n';
                exit(0);
            }
        };
        check();
        if (d == 8) continue;
        vector<pair<pii, pii>> car(mx + 1, {{-1, -1}, {-1, -1}});
        rep (i, 0, 6) rep (j, 0, 6) if (cur[i][j]) {
            car[cur[i][j]].S = {i, j};
            if (car[cur[i][j]].F.F == -1) car[cur[i][j]].F = {i, j};
        }
        d++;
        rep (i, 1, mx + 1) {
            auto [h, t] = car[i];
            if (h.F == t.F) {
                if (h.S != 0 && cur[h.F][h.S - 1] == 0) {
                    rep (i, h.S - 1, t.S) swap(cur[h.F][i], cur[h.F][i + 1]);
                    check();
                    if (mp[cur] == 0) {
                        q.push({cur, d});
                        mp[cur] = 1;
                    }
                    for (int i = t.S; i >= h.S; --i) swap(cur[h.F][i], cur[h.F][i - 1]);
                }
                if (t.S != 5 && cur[h.F][t.S + 1] == 0) {
                    for (int i = t.S + 1; i > h.S; --i) swap(cur[h.F][i], cur[h.F][i - 1]);
                    check();
                    if (mp[cur] == 0) {
                        q.push({cur, d});
                        mp[cur] = 1;
                    }
                    rep (i, h.S, t.S + 1) swap(cur[h.F][i], cur[h.F][i + 1]);
                }
            } else {
                if (h.F != 0 && cur[h.F - 1][h.S] == 0) {
                    rep (i, h.F - 1, t.F) swap(cur[i][h.S], cur[i + 1][h.S]);
                    check();
                    if (mp[cur] == 0) {
                        q.push({cur, d});
                        mp[cur] = 1;
                    }
                    for (int i = t.F; i >= h.F; --i) swap(cur[i][h.S], cur[i - 1][h.S]);
                }
                if (t.F != 5 && cur[t.F + 1][h.S] == 0) {
                    for (int i = t.F + 1; i > h.F; --i) swap(cur[i][h.S], cur[i - 1][h.S]);
                    check();
                    if (mp[cur] == 0) {
                        q.push({cur, d});
                        mp[cur] = 1;
                    }
                    rep (i, h.F, t.F + 1) swap(cur[i][h.S], cur[i + 1][h.S]);
                }
            }
        }
    }
    cout << -1 << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}
```
:::

### B. The Power Monitor System (待補)
---
#### 題目摘要


#### 想法


:::spoiler 實作

```cpp=
```
:::


### C. Are They All Integers?
---
#### 題目摘要
問對於一個序列，任取3項的兩項差除以第三項是否為整數

#### 想法
簽到，$N^3$爆做

:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
 
int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep (i, 0, n) cin >> a[i];
    bool f = 1;
    rep (i, 0, n) rep (j, 0, n) rep (k, 0, n) {
        if (i != j && j != k && i != k) f &= (((a[i] - a[j]) % a[k]) == 0);
    }
    cout << (f ? "yes" : "no");
}
```
:::

### D. Tapioka
---
#### 題目摘要
給定一坨字串s由空格分開，把所有"tapioka" 跟 "bubble" 刪掉後輸出
#### 想法
直接實作

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

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

int main() {
    string b = "bubble";
    string t = "tapioka";
    vector<string> ans;
    string s;
    while(cin >> s){
        if(s!=b && s!=t){
            ans.push_back(s);
        }
    }
    for(auto v : ans){
        cout << v << ' ';
    }
    if(ans.empty()){
        cout << "nothing";
    }
    
}
```
:::

### E. The League of Sequence Designers
---
#### 題目摘要
題目給一個要算序列中序列中最大的區間和乘區間長度的問題，並給一個錯誤的程式碼：當現在累積的和<0，就放棄這些和，否則拿這個和去更新答案。而你會拿到長度下界$L$與誤差值$k$，問你能不能構出一筆序列為$n(n>=L)$使得正確答案與錯誤答案差$k$。若能，請輸出序列，否則輸出-1
#### 想法
要滿足條件，一定要一些正數和負數，但一堆正數實在是太難想了，所以就往只有一個正數的方向想
假設$x$為那一正數，那$x$就是錯誤解的答案，而$x+k$就是正解，而只要讓序列長度為$x+k$的因數就能夠出解了。另外，序列元素的大小有限制，對於長度要找出適當$x$才行

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int lim=2000;
const ll MAX=1000000;
 
void solve(){
    ll k;
    int L;
    cin >> k >> L;
    for(int i=max(L, 3);i<=lim;i++){
        ll sum=(MAX+k)/i;
        ll x=sum*i-k;
        if (sum+2<=x){
            ll dif=x-sum;
            vector<int> ans(i, 0);
            ans[0]=x;
            for(int j=1;j<i;j++){
                if (dif>MAX){
                    ans[j]=-MAX;
                    dif-=MAX;
                }else{
                    ans[j]=-dif;
                    dif=0;
                }
            }
            if (dif!=0) continue;
            reverse(ans.begin(), ans.end());
            cout << i << '\n';
            for(auto x:ans){
                cout << x << ' ';
            }
            cout << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}

```
:::

### F. Miss Sloane (待補)
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=

```
:::

### G. Optimal Selection (待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=

```
:::


### H. Mining a
---
#### 題目摘要
給你數字$n$，輸出滿足$\frac{1}{n}=\frac{1}{a\oplus b}+\frac{1}{b}$的最大$a$
#### 想法
賽中盲猜$b=n+1$時$a$最大，但這題好像要拆成
\begin{array}
\\(a\oplus b)\times b=nb+n(a\oplus b)\\
n^2=((a\oplus b)-n)\times(b-n)
\end{array}
因此只要枚舉$n^2$的因數就能求答案了
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
void solve(){
    ll n;
    cin >> n;
    ll ans=n*(n+1);
    ans^=(n+1);
    cout << ans << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}
```
:::

### I. The Spectrum (待補)
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=


```
:::


### J. Automatic Control Machine
---
#### 題目摘要
給你$m$個長度為$n$的01序列，問能不能選一些序列使它們全or起來後的序列所有元素為1。若能，輸出選的最少個數，否則輸出-1
#### 想法
$2^m$枚舉，用bitset來確認有沒有全部覆蓋

:::spoiler 實作
```cpp=

#include <bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
 
void solve() {
    int n, m; cin >> n >> m;
    vector<bitset<505>> bst(m);
    rep (i, 0, m) rep (j, 0, n) {
        char c; cin >> c;
        bst[i][j] = c - '0';
    }
    // bitset<505> check;
    // rep (i, 0, n) check[i] = 1;
    int ans = m + 1;
    rep (bit, 0, 1 << m) {
        bitset<505> hehe;
        rep (i, 0, m) if (bit >> i & 1) hehe |= bst[i];
        if (hehe.count() == n) ans = min(ans, __builtin_popcount(bit));
    }
    if (ans == m + 1) ans = -1;
    cout << ans << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) {
        solve();
    }
}
```
:::


### K. Length of Bundle Rope
---
#### 題目摘要
裸霍夫曼編碼。

#### 想法
簽到，用Priority_queue實作
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
 
void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    rep (i, 0, n) cin >> a[i];
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    rep (i, 0, n) pq.push(a[i]);
    ll ans = 0;
    while (pq.size() > 1) {
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();
        ans += a + b;
        pq.push(a + b);
    } 
    cout << ans << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) {
        solve();
    }
}

```
:::

### L. Largest Quadrilateral
---
#### 題目大綱
給你二維座標上的一堆點(有重點)，求最大四邊形(若選的四個點讓四邊形退化成三角形也是合法的)
#### 想法
賽中想成枚舉四邊形的一個點，將與其他點的向量拿出來排序，考慮到兩向量在固定象限中，所夾的面積具單調性，所以能用deque去維護目前選的對角線應該拿哪條向量來外積，複雜度$O(n^2\log n)$，但被卡了QQ
而正解只要枚舉對角線用旋轉卡尺維護兩邊的最大面積，複雜度$O(n^2)$
:::spoiler 實作
```cpp=
pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define F first
#define S second
 
const int BUF_SZ = 1 << 15;
inline namespace Input {
    char buf[BUF_SZ];
    int pos;
    int len;
    char next_char() {
        if (pos == len) {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, stdin);
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }
 
    ll read_int() {
        ll x;
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
        return x * sgn;
    }
}// namespace Input
inline namespace Output {
    char buf[BUF_SZ];
    int pos;
 
    void flush_out() {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }
 
    void write_char(char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }
 
    void write_int(ll x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
        write_char((char)('0' + x));
        while (len) { write_char(num_buf[--len]); }
    }
 
    // auto-flush output when program exits
    void init_output() { assert(atexit(flush_out) == 0); }
}// namespace Output
 
inline pii operator-(pii x, pii y){return {x.F-y.F, x.S-y.S};}
inline ll dot(pii x, pii y){return x.F*y.F+x.S*y.S;}
inline ll cross(pii x, pii y){return x.F*y.S-x.S*y.F;}
inline ll area(pii x, pii y, pii z){return abs(cross(x-z, y-z));}
 
void output(ll x){
    write_int((x>>1));
    if (x&1) write_char('.'), write_char('5');
    write_char('\n');
}
 
int n;
inline int nex(int x, int d=1){
    x+=d;
    if (x>=n) x-=n;
    return x;
}
 
void solve(){
    n=read_int();
    vector<pii> pos(n);
    for(auto &[x, y]:pos){
        x=read_int();
        y=read_int();
    }
    sort(pos.begin(), pos.end());
    vector<pii> hull;
    for(int _=0;_<2;_++){
        for(int i=0;i<n;i++){
            while(hull.size()>=2&&cross(pos[i]-hull.end()[-2], hull.back()-hull.end()[-2])<0) hull.pop_back();
            hull.push_back(pos[i]);
        }
        hull.pop_back();
        reverse(pos.begin(), pos.end());
    }
    if (hull.size()<3) cout << 0 << '\n';
    else if (hull.size()==3){
        ll ans=0;
        ll A=area(hull[1], hull[2], hull[0]);
        for(int i=0;i<n;i++) if (pos[i]!=hull[0]&&pos[i]!=hull[1]&&pos[i]!=hull[2]) ans=max(ans, A-min({area(hull[0], hull[1], pos[i]), area(hull[1], hull[2], pos[i]), area(hull[0], hull[2], pos[i])}));
        output(ans);
    }else{
        ll ans=0;
        n=hull.size();
        for(int i=0;i<n;i++){
            int p1=nex(i);
            int p2=nex(i, 3);
            for(int j=nex(i, 2);nex(j)!=i;j=nex(j)){
                while(nex(p1)!=j&&area(hull[i], hull[j], hull[nex(p1)])>area(hull[i], hull[j], hull[p1])) p1=nex(p1);
                while(nex(p2)!=i&&area(hull[i], hull[j], hull[nex(p2)])>area(hull[i], hull[j], hull[p2])) p2=nex(p2);
                ans=max(ans, area(hull[i], hull[j], hull[p1])+area(hull[i], hull[j], hull[p2]));
            }
        }
        output(ans);
    }
}
 
int main(){
    init_output();
    int _t;
    _t=read_int();
    while(_t--) solve();
}
```
:::


### M. DivModulo (待補)
---
#### 題目大綱
定義 $dmod$ 如下 $A\ (dmod\ p)= a*p^x\ (dmod\ p) \equiv a \mod p$
給 $M,N,D$ 求 $\binom{N}{M}\ dmod\ D$ 的值
#### 想法

:::spoiler 實作
```cpp=

```
:::
