[TOI] 20200815 新手同好會－個人賽

不出所料地，
這種競賽果然一屆比一屆困難，
上次有人破台，
這次我雖以 $610/800$ 分拿到了第一名，
不過卻少了一點競爭感。
個人覺得難度大約如下：

$P1$	$P2$	$P3$	$P4$
★	★	★	★★★
$P5$	$P6$	$P7$	$P8$
★★	★★	★★★	★★

$P4$ 的基礎實作寫了快 100 行的 $struct$，
修修改改好幾次還是拿不到分數。
$P7$ 看到題目就沒有想法，
完全沒打算 $AC$ 那題。
$P8$ 幾本上就裸題，
容器 $priority\_queue$ 直接拿來用即可。
其餘題目沒有太大的困難。


< $P1.$ 同樂會($Party$) >
題意：
輸入只有一行包含兩個整數 $N, \ M$，
代表 $N$ 個人、$M$ 個披薩。
一個披薩可以切成 $8$ 片，
每個人可以吃 $2$ ~ $3$ 片披薩。
如果不會過多也不會過少，
輸出 $Yes$，
如果過少，
輸出 $Not \ enough$，
如果過多，
輸出 $Too \ much$。

範圍：
$0 \ ≤ \ N \ ≤ \ 1000$，
$0 \ ≤ M \ ≤ \ 500$。

範例輸入 $1.$：

25 8

範例輸出 $1.$：

Yes

範例輸入 $2.$：

10 5

範例輸出 $2.$：

Too much

範例輸入 $3.$：

50 10

範例輸出 $3.$：

Not enough

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    if (N * 2 <= M * 8 && M * 8 <= N * 3)
        cout << "Yes\n";
    else if (M * 8 <= N * 2)
        cout << "Not enough\n";
    else
        cout << "Too much\n";
}

< $P2.$ 后羿射日($Archer$) >
題意：
第一行有四個整數 $x_0, \ y_0, \ L_0, \ R$，
代表后羿所在的座標 $(x_0, \ y_0)$、后羿的等級 $L_0$、射程 $R$。
第二行有一個正整數 $N$，
接下來有 $N$ 行表示有 $N$ 個太陽，
每行包含三個整數 $x_i, \ y_i, \ L_i$，
如果太陽在后羿的射程範圍 $R$ 以內，
且太陽的等級 $L_i$ 小於等於后羿的等級 $L_0$，
才可把太陽射下，
求后羿可設下多少太陽。

範圍：
$-1000 \ ≤ \ x_0, \ y_0, \ x_i, \ y_i \ ≤ \ 1000$，
$1 \ ≤ L_0, \ L_i \ ≤ \ 5$，
$0 \ ≤ \ R \ ≤ \ 3000$，
$1 \ ≤ \ N \ ≤ \ 10$。

範例輸入 $1.$：

0 0 2 1000
1
500 0 4

範例輸出 $1.$：

0

範例輸入 $2.$：

10 10 5 50
3
20 10 1
-100 50 2
0 0 3

範例輸出 $2.$：

2

範例輸入 $3.$：

100 60 1 100
5
100 100 1
500 60 1
50 -20 1
200 60 1
120 70 3

範例輸出 $3.$：

3

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int x0, y0, L0, R, n, x, y, L, ans = 0;
    cin >> x0 >> y0 >> L0 >> R;
    cin >> n;
    while (n--) {
        cin >> x >> y >> L;
        if (L > L0)
            continue;
        if (sqrt(pow(x - x0, 2) + pow(y - y0, 2)) > R)
            continue;
        ans++;
    }
    cout << ans << '\n';
}

< $P3.$ 下雪的日子($Snow$) >
題意：
第一行有兩個正整數 $N$、$M$，
$N$ 代表道路總長(道路範圍$[0, \ N]$)、$M$ 代表道路資訊筆數，
接下來有 $M$ 行，
每行有兩個正整數 $S, \ E$，
表示路段 $[S, \ E]$ 是暢通的，
試問不暢通的路段有哪些，
並依序輸出其起左界和右界。

範圍：
$1 \ ≤ \ N \ ≤ \ 20$，
$1 \ ≤ \ M \ ≤ \ N$，
$0 \ ≤ \ S \ ≤ \ E \ ≤ \ N$。

範例輸入 $1.$：

7 5
0 1
1 3
4 5
5 6
6 7

範例輸出 $1.$：

3 4

範例輸入 $2.$：

5 2
0 1
3 4

範例輸出 $2.$：

1 3
4 5

範例輸入 $3.$：

10 4
1 2
3 4
5 6
7 8

範例輸出 $3.$：

0 1
2 3
4 5
6 7
8 10

範例輸入 $4.$：

6 3
3 5
1 4
5 6

範例輸出 $4.$：

0 1

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
using namespace std;

int main() {
    int n, m, l, r;
    cin >> n >> m;
    bool v[101] = {false};
    while (m--) {
        cin >> l >> r;
        for (int i = l; i < r; i++)
            v[i] = true;
    }
    for (int i = 0; i < n; i++) {
        if (v[i])
            continue;
        l = i;
        while (!v[i++] && i <= n);
        i -= 1;
        r = i;
        cout << l << ' ' << r << '\n';
    }
}

< $P4.$ 俄羅斯方塊($Tetris$) >
題意：
如題，
就是要模擬俄羅斯方塊。
方塊初始模型如下：
■■■

□■□
方塊初始位置 $([x \ / \ 2], \ y)$。
第一行有兩個正整數 $x, \ y$ 代表畫面大小(畫面左下角座標為 $(1, \ 1)$)。
第二行有一個正整數 $n$，
第三行有 $n$ 個數字代表不同指令。
指令 $0$ $\longrightarrow$ 無指令，
指令 $1$ $\longrightarrow$ 右移，
指令 $2$ $\longrightarrow$ 左移，
指令 $3$ $\longrightarrow$ 置底，
指令 $4$ $\longrightarrow$ 右旋，
每送出指令方塊都會下移一格，
若有不合法指令則視為指令 $0$。

範圍：
$3 \ ≤ \ x, \ y \ ≤ \ 100$，
$1 \ ≤ n \ < \ y$。

範例輸入 $1.$：

6 6
3
0 1 3

範例輸出 $1.$：

000000
000000
000000
000000
001110
000100

範例輸入 $2.$：

6 6
4
1 1 1 1

範例輸出 $2.$：

000000
000000
000000
000000
000111
000010

程式碼參考：
待補。

< $P5.$ 閱讀順序($Reading$) >
題意：
第一行有一串文字 $S$，
第二行有一串文字 $T$，
$S$ 字串必定包含 $T$ 字串。
將 $S$ 字串中，
以 $T$ 為翻轉軸(若不只出現一次，則以第一次出現的 $T$ 為翻轉軸)，
左右字串交換位置，
左右字串再各自顛倒順序。
輸出其翻轉後的字串。

範圍：
$\left| \ S \ \right| \ ≤ \ 50$。

範例輸入 $1.$：

apple
ppl

範例輸出 $1.$：

eppla

範例輸入 $2.$：

banana
na

範例輸出 $2.$：

annaab

範例輸入 $3.$：

split
t

範例輸出 $3.$：

tilps

範例輸入 $4.$：

what
wh

範例輸出 $4.$：

tawh

範例輸入 $5.$：

complex
ex

範例輸出 $5.$：

exlpmoc

範例輸入 $6.$：

overcome
overcome

範例輸出 $6.$：

overcome

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int pos = s.find(t);
    string l(s.begin(), s.begin() + pos), r(s.begin() + pos + t.size(), s.end());
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    cout << r << t << l << '\n';
}

< $P6.$ 居家管理機器人($Robot$) >
題意：
第一行有一個字串（不含空白）代表密碼，
第二行有一個字串（含空白）代表使用者輸入。
而使用者輸入必須符合句型「Password (或 password) is 密碼」(忽略單字前後標點符號)，
才可成功通過密碼測試。
而檢查方式如下：

• 句型與密碼皆正確，輸出 $Welcome \ home.$。
• 如果句型正確但密碼錯誤，輸出 $Wrong \ password.$。
• 其餘狀況，輸出 $Sorry?$。

範圍：
$\left| \ 單詞 \ \right| \ ≤ \ 20$，
單詞數量 $≤ \ 50$。

範例輸入 $1.$：

pewpew
This is Chris, password is pewpew, can you help me?

範例輸出 $1.$：

Welcome home.

範例輸入 $2.$：

123456789
Password is 12345678, I want to take a bath.

範例輸出 $2.$：

Wrong password.

範例輸入 $3.$：

neverlose
I am David, password neverlose.

範例輸出 $3.$：

Sorry?

範例輸入 $4.$：

okok
Password wow, is ook.

範例輸出 $4.$：

Sorry?

範例輸入 $5.$：

good
Password is what? Let me think. Well, password is good.

範例輸出 $5.$：

Welcome home.

範例輸入 $6.$：

test123
Password is,, test123.

範例輸出 $6.$：

Welcome home.

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
#include <sstream>
using namespace std;

string re, line, tmp;

int check(string s) {
    if (s == "Password" || s == "password")
        return 0;
    if (s == "is")
        return 1;
    if (s == re)
        return 2;
    return -1;
}

int main() {
    (cin >> re).get();
    getline(cin, line);
    stringstream ss(line);
    bool ok = false;
    int cur = 0, mx = 0;
    while (ss >> tmp) {
        while (!isdigit(tmp.back()) && !isalpha(tmp.back()))
            tmp.pop_back();
        while (!isdigit(tmp.front()) && !isalpha(tmp.front()))
            tmp.erase(tmp.begin());
        if (check(tmp) == cur)
            cur++, mx = max(mx, cur);
        else
            cur = 0;
        if (cur == 3)
            ok = true;
    }
    if (ok)
        cout << "Welcome home.\n";
    else if (mx == 2)
        cout << "Wrong password.\n";
    else
        cout << "Sorry?\n";
}

< $P7.$ 幼稚園($Kindergarten$) >
題意：
第一行有一個正整數 $N$ 代表有幾個小朋友，
接下來一行 $N$ 個數代表初始隊形（由前到後）的小朋友身高 $h_i$。
而現在要的任務就是整理隊形，
有三種可行的隊形規則：

• 非嚴格遞增數列，如 $(1, \ 1, \ 2, \ 3 )$。
• 非嚴格遞減數列，如 $(5, \ 3, \ 3, \ 1)$。
• 前段非嚴格遞增且後段非嚴格遞減，如 $(1, \ 2, \ 3, \ 3, \ 4, \ 7, \ 6, \ 6)$。

試問最小交換（只能連續的兩人做交換）次數。

範圍：
$1 \ ≤ \ N \ ≤ \ 5000$，
$1 \ ≤  \ h_1, \ h_2, \ ..., \ h_N  \ ≤ \ 200$。

範例輸入 $1.$：

3
2 1 3

範例輸出 $1.$：

1

範例輸入 $2.$：

4
1 3 2 4

範例輸出 $2.$：

1

範例輸入 $3.$：

3
1 2 3

範例輸出 $3.$：

0

範例輸入 $4.$：

7
3 1 4 1 7 20 2

範例輸出 $4.$：

3

程式碼參考：
待補。

< $P8.$ 運送隕石($Delivery$) >
題意：
第一行有兩個正整數 $N, \ M$ 表示有 $N$ 個隕石和 $M$ 個炸彈，
第二行有 $N$ 的正整數 $A_1, \ A_2, \ ..., \ A_N$，
分別代表隕石的重量。
每個炸彈可將一個顆石等分為兩顆重量相同的隕石，
計算最佳的情況下，
隕石重量上限的最小值。

範圍：
$1 \ ≤ N, \ M \ ≤ \ 10^5$，
$1 \ ≤ \ A_1, \ A_2, \ ..., \ A_N \ ≤ \ 10^9$。

範例輸入 $1.$：

1 3
4

範例輸出 $1.$：

1

範例輸入 $2.$：

4 3
2 5 7 30

範例輸出 $2.$：

8

程式碼參考：
$JUDGE\_RESULT$：$100/100$ 分

#include <iostream>
#include <iomanip>
#include <cmath>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    priority_queue<long double> pq;
    long double re;
    cin >> n >> m;
    while (n--) {
        cin >> re;
        pq.emplace(re);
    }
    while (m--) {
        re = pq.top();
        pq.pop();
        re /= 2;
        pq.emplace(re);
        pq.emplace(re);
    }
    cout << fixed << setprecision(0) << ceil(pq.top()) << '\n';
}

< 心得 >
比賽的時候，
智商真的會下降 > <，
$P6$、$P8$ 送了好幾次，
覺得沒什麼大問題卻一直無法全對，
後來發現，
$P6$ 是函數忘記想到所有狀況導致回傳值有錯，
$P8$ 看起來就是裸題卻一直拿不到分，
最後 $3$ 分鐘突然通靈，
在最後輸出的地方加上 $fixed$、$setprecision(0)$ 就突然跳出綠色的 $100/100$，
一整個就覺得好開心～
其實，
對於自己個人賽的表現，
並沒有很理想，
一直擔心時間不夠，
所以讀題很快，
卻一直漏掉一些數據範圍的細節，
只有拿 $610/800$ 分($10$ 分是 $P7$ 有 $10/100$ 分是 $N \ = \ 3$ 的情形而拿到的分數)，
實在不是很理想。
結果意外的拿到了第一，
心中湧起的不是喜悅，
而是許多感慨。
之前也在師大參加 $TOI$ 研習營初選，
做答狀況比較理想，
卻被電爛、電到起飛，
這次也是在師大參與同一個單位辦的競賽，
卻有截然不同的結果，
對於自己的實力，
只能說「比上不足比下餘」，
還有很多的努力空間。
回到正題，
今天的新手同好會其實蠻有趣的，
也認識了來自各地的電神 <(_ _)> ，
美中不足的地方是，
主辦單位沒能把氣氛帶嗨，
中午的抽獎沒有音樂有點尬，
稍微可惜了，
不過能參予這次的活動，
仍十分感激了。



以上，
若有更好的想法歡迎提出哦！