# 2023 高雄市賽題目
## 規則
賽制：使用CMS系統，賽中沒有計分板，分上、下午場，各2小時
[詳細賽程表](https://www.pmsh.khc.edu.tw/activity/112%e5%ad%b8%e5%b9%b4%e5%ba%a6%e9%ab%98%e4%b8%ad%e8%b3%87%e8%a8%8a%e5%ad%b8%e7%a7%91%e8%83%bd%e5%8a%9b%e7%ab%b6%e8%b3%bdcms%e7%b3%bb%e7%b5%b1/)

## 原題pdf檔
[連結](https://drive.google.com/file/d/1PkAnECpaBp_TBjJnyO8pnOsVKHOE8IJD/view)

11/10 UPD：抱歉！我把p2、p3的範圍記反了！

## 題目
### 上午場第一題（guess）
滿分：100分
時限：0.1s
已知$A\cdot y \equiv x (mod~M_1), B\cdot y \equiv x (mod~M_2), 1\leq x\leq n, 1\leq y\leq m$，$(M_1,M_2)=(2023110403,2023110407)$都是質數，題目保證有解。
輸入四個數字 $A,B,n,m$ ，求最小可能的 $x$。
$(A\leq M_1，B\leq M_2，n,m\leq {10}^9)$

$Subtask~1$（1分）：$n,m\leq 1000$
$Subtask~2$（1分）：$n,m\leq {10}^5$
$Subtask~3$（32分）：$n\leq 1000,m\leq {10}^9$
$Subtask~4$（66分）：$n,m\leq {10}^9$
### 上午場第二題（comm）
滿分：150分
時限：1s
有 $n$ 個間諜，每個間諜必須選擇要回報給 $A$ 還是 $B$，每個間諜回報給 $A$ 或 $B$ 的訊息傳遞時間可能不同，有 $m$ 個pair，這些pair的間諜必須回報給不同人，無解要輸出$-1$， $A,B$ 之間的訊息傳遞時間為 $D$。
給定 $n,m,D$、每位間諜分別回報給 $A,B$ 的時間跟 $m$ 個pair，求任意兩個間諜傳遞訊息的最大時間的最小值。
（$n,m\leq{10}^5$，任意一個間諜與 $A,B$ 之間的訊息傳遞時間和 $D$ 皆介於 $[0, {10}^9]$ 之間）
$Subtask~1$（10分）：$D=0,n\leq50,m=0$
$Subtask~2$（12分）：$D\leq{10}^9,n\leq10,m\leq10$
$Subtask~3$（14分）：$D=0,n\leq50,m\leq50$
$Subtask~4$（16分）：$D\leq{10}^9,n\leq50,m\leq50$
$Subtask~5$（23分）：$D\leq{10}^9,n\leq{10}^5,m\leq{10}^5$
$Subtask~6$（24分）：$D=0,n\leq{10}^5,m\leq{10}^5$
$Subtask~7$（25分）：$D\leq{10}^9,n\leq{10}^3,m\leq{10}^3$
$Subtask~8$（26分）：$D\leq{10}^9,n\leq{10}^5,m\leq{10}^5$
### 上午場第三題（defense）
滿分：150分
數線上有 $n$ 個炮台，每個炮台都有他的座標跟防禦範圍長度 $pos_i$ 跟$len_i$ ，每個炮台可以選擇兩個方向：正向或是負向，負向的炮台的防禦區間是 $[pos-len,pos]$ ，正向是的炮台的防禦區間則是 $[pos,pos+len]$ ，求最大防禦區間線段聯集長度。 （$n\leq 5000, 0\leq pos_i,len_i\leq {10}^9$）
$Subtask~1$（10分）：$n\leq4$
$Subtask~2$（20分）：$n\leq10$
$Subtask~3$（20分）：$n\leq30$
$Subtask~4$（48分）：$n\leq100$
$Subtask~5$（19分）：$n\leq400$
$Subtask~6$（33分）：$n\leq5000$
### 下午場第一題（egg）
互動題。
滿分：100分
時限：2s

簡易題敘：
請你透過盡量少的實驗成本，測出一種雞蛋的堅固程度，如果一種雞蛋的堅固程度是$x$，那麼只要從高度不超過$x$的地方丟雞蛋，這種雞蛋就不會破。

第一行輸入一個數字 $T$ ，代表有 $T$ 筆測資$（T \leq 1000）$。
每筆測資一開始會輸入四個整數，依序為 $v, p, wall, egg$ （都介於 $[0, {10}^9]$ 之間），代表你如果在高度 $h$ （$h$ 必須是正整數）的地方丟下雞蛋，你必須付出 $p+h\cdot wall$ 的成本，而且如果雞蛋破了，你就要再額外付出 $egg$ 的成本。
互動方式：
如果你輸出一個正數，judge會回答你從這個高度丟雞蛋是否會破 （如果破了，那你的成本就會增加$egg$）。
如果你輸出了 $x$ 且 $x\leq0$ ，那表示你認為這種雞蛋的堅固程度是 $-x$ ，隨後就會進入下一筆測資，但如果你輸出了錯誤的答案，你的程式會直接被停止，而且verdit可能不會是WA。
另外，如果你詢問（做實驗）的次數超過${10}^5$次，你的程式碼會被judge強制中止。

評分方式：
如果官解的成本是 $S$ ，你的成本是 $T$ ，那麼你得到的分數就是$(那個子題的分數) \times \frac{S}{T}$。
（註：我不確定他多筆測資的成本是不是直接加起來的，也有可能是分開算然後直接取最小值）
$Subtask~1$（13分）：$p=1,wall=egg=0,v\leq1000$
$Subtask~2$（17分）：$wall=0,v\leq1000$
$Subtask~3$（21分）：$wall=0$
$Subtask~4$（26分）：$v\leq1000$
$Subtask~5$（23分）：$wall>0$
### 下午場第二題（fire）
滿分：150分
時限：0.5s
有一間 $N$ 個人的公司，編號 $1$ 是老闆（老闆沒有上司），除了老闆以外的人分別編號 $2～N$。
輸入格式：
$N$
$par_2$ $type_2$
$par_3$ $type_3$
$\dots$
$par_N$ $type_N$
解釋：
$par_i$ 代表編號 $i$ 的人原本的直屬上司是 $par_i$，
$type_i$ 代表編號 $i$ 的人的能力類別（$1\leq type_i \leq N$），而$type_1=0$。
（$N\leq {10}^5$）
要求：
你可以選擇幾個人然後把它開除掉，如果一個人的上司已經被開除了，那麼他「原本的上司」的上司就變成了他新的上司，依此類推。
（想像一個有根樹而老闆就是根，那如果一個點 $u$ 原本的祖先被拔掉了，那麼從這個點沿著原圖一直向上直到有一個點 $v$ 沒有被拔掉為止，則$v$ 就是 $u$ 新的祖先）
請輸出「最少需要開除掉幾個人，才能讓每個人的直接下屬的$type$都一樣」，無須構造解。
（直接下屬的定義：如果 $u$ 是 $v$ 的直接下屬，那麼在對應的有根樹中， $u$ 和 $v$ 以一條邊相連，且 $u$ 是 $v$ 的兒子）

$Subtask~1$（20分）：$n\leq 10$
$Subtask~2$（20分）：$n\leq 100$
$Subtask~3$（48分）：$n\leq 5000$
$Subtask~4$（19分）：$n\leq {10}^5$且總層數（樹高）不超過$20$
$Subtask~4$（43分）：$n\leq {10}^5$
### 下午場第三題（wall）
滿分：150分
給定一個$n\times m$方格的圖，方格的四個邊有各自的邊權（介於$[0,{10}^9]$之間），共有 $(n+1)\times m + (m+1)\times n$ 條邊，有的方格中心有軍事基地（保證最左上角的方格中一定有軍事基地），你必須用最小成本加一些圍欄，使得從方格外部的人，無法在不通過圍欄的情況下到達任意一個軍事基地。（$n,m\leq 500$）
舉例：
下圖是一個 $n = 3, m = 4$ 的圖，圖中有三個軍事基地。

邊角點：方格的四角都是邊角點，一張圖上共有 $(n+1)\times (m+1)$ 個邊角點。
圍圍欄的方法：
選定一個邊角點，依序走過一些邊，最後要回到起點，則走過的每條邊就會有圍欄，花費是走過的走過的邊的邊權和，一條邊如果走過了兩次，那他的邊權就要算兩次。

下圖是一種合法的圍圍欄的方式，其中有一條邊的邊權要被算兩次，其餘的都只被算到一次：

下圖的圍圍欄方式是不合法的，因為用上方規定的圍圍欄方法不可能圍出這種圍欄：

下圖的圍圍欄方式是不合法的，因為從方格外部的人可以經由綠線的方向在不通過圍欄的情況下到達其中一個軍事基地。
$Subtask~1$（31分）：$n,m\leq 5$
$Subtask~2$（43分）：$n,m\leq 50$
$Subtask~3$（76分）：$n,m\leq 500$