# 【題解】110 南一中校內初選題解 B, C

## TOJ 628. prob B - **國中會考分發**

> 給定每個人的成績以及他們的志願序，求分發結果。
>

直接按照題目的描述模擬即可。按照給定的順序為每個學生找學校。為一個學生找學校時，按志願高到低遍歷志願序中的學校，一但找到還塞的進人的學校，就分配至該所學校。

## TOJ 629. prob C - GAMAGAMA

> 對兩條有 ${+a, *a}$ 的路徑進行以下操作
>
> - 輸出以 $k$ 開始的最大值
> - 將 ${+a, *a}$ 接在路徑 $i$ 的後方
> - 輸出唯一整數解 $m$ 滿足以 $m$ 開始則兩條路徑結果相同

假設一開始為 $x$，經過隧道：

1. 經過 $+a_1$ 後變成 $x + a_1$
2. 經過 $\times a_2$ 後變成 $a_2 x + a_1 a_2$
3. 經過 $+a_3$ 後變成 $a_2x + a_1 a_2 + a_3$
4. 經過 $\times a_4$ 變成 $a_2 a_4 x + a_1 a_2 a_4 + a_3 a_4$

可以發現，我們永遠可以通過 $kx + b$ 來描述 $x$ 經過一條隧道後的值。

- 接上 $+a$： $b := b + a$
- 接上 $\times a$： $k := ka, b := ba$

那麼我們可以處理 $O(1)$ 處理操作一、二；對於操作三：

$$
k_1 x + b_1 = k_2 x + b_2 \\
x = \frac {b_2 - b_1} {k_1 - k_2}
$$

按題意，若 $x$ 非整數或分母為 $0$ 輸出無解。