# CPTC001 Solutions (2020.12.16)

## A - Altitude Sickness
> 給 nxm grid，grid 上是每一格的高度，
> 多次 query ，給一個高度，
> 求低於此高度的面積
> [name=tracyliu1220]

因為這題只在意高度不在意位置，
所以只要將所有 input 輸入存進 array 中，
sort 之後每次使用二分搜搜尋 array 中小於等於 $h$ 與大於等於 $h$ 的臨界 index，
此 index + 1 就是每次查詢的答案（index 之前的 elements 都小於等於 $h$）。

願意使用 STL library 的同學可以參考 `sort()` 配上 `upper_bound()` 的作法。

## B - Towers

> 給一張無向簡單圖 $G = (V, E), |V| = n, |E| = m$ 和 長度為 $n$ 的 integer array A.
> 將 array 的值一對一賦予到點權重上, 在點 $v$ 的權重為 $B[v]$, 點 $v$ 的相鄰邊數為 $deg(v)$, 詢問$\sum_{v\in V}deg(v) \times B[v]$最小值
> [name=marmot0814]

題目抽象化成兩個給兩個 integer array, 一個是題目給訂的 A, 另一個是由圖中每個點的 degree 所構成的 array D. 求 $\sum_{i=0}^{n}D[i] \times A[i]$ 最小值。
由排序不等式可知道, 逆序會小於其他排列方式, 因此將權重按照點 $degree$ 數量逆序排列即可。

## C - Froggy and Froggo
> 給 grid，將左上角跟右下角切開，
> 只能切左下到右上的階梯狀（切的路線只能往右或往上），
> 目標是將兩邊的 sum 切成相同，
> 切的路線只能轉最多 5 次彎，
> 可以的話輸出 YES 跟最少需要幾次彎，
> 不行或超過 5 次彎的話輸出 NO
> [name=tracyliu1220]

### 枚舉位置

枚舉轉 1、3、5 次彎的情況分別可以用枚舉 1、2、3 個位置來達成，

### 計算灰色區塊總和

以 3 個位置（轉 5 次彎）的情況為例，

灰色區塊的 sum 就是 $a + b + c - d - e$，
字母代表上圖個別框起來區塊的 sum，
也就黃色圓形與綠色三角形的 prefix sum，
至於求 prefix sum 的方法請參考[這裡](https://www.geeksforgeeks.org/prefix-sum-2d-array/)。

### Special Cases

但是還有一些 case 要考慮，


第一個是若最右上側與最左下側的黃色圓形碰到上圖綠色的線的話轉彎次數就要各 -1 一次（用 5 去減），
所以答案 0、2、4 等答案就會從這種 case 出現。


第二個狀況是當其中兩個黃色圓形都碰到綠線的話，
4 個黃色圓形也可以造出 5 的答案，
但我們不能直接枚舉 4 個位置時間會不夠，
可能的解法有在枚舉 4 個位置時增加其中 2 位置要碰到綠線的限制，
或是將圖整個翻轉用上圖空心的黃色圓形位置（這時就只需要列舉 3 個點）再做一次。

### 複雜度

複雜度為 $n^6$，
但考慮枚舉點的相對位置限制與順序性（每個點都要在前一個點的左下方），
實際要枚舉的量為 $\frac{n^6}{3!3!}$

## D - Robust Eggs

> 1000層樓, 有3顆雞蛋, 兩種query
> - ? x, 從x層樓丟下去, 回傳有沒有破
> - ! x, 回傳雞蛋的最高從x樓丟下來不會破
> [name=marmot0814]

此題為經典[雙蛋問題](https://zh.wikipedia.org/wiki/%E5%8F%8C%E8%9B%8B%E9%97%AE%E9%A2%98)的延伸, 詢問策略滿多種, 在此給出一種策略。
分為三個階段
1. 將 1000 層樓分成 10 組, 每組 100 層。
- 分法 [1, 100], [101, 200], ..., [901, 1000]
- 每次依序由小到大詢問每組的最小樓層, (ex. 1, 101, 201, 301, 401, ..., 901)
- 可以找到破跟不破的交界點(以下舉例201層不破, 301層破裂。), 因此可以知道答案介於[201, 300]這 100 層之間。
- 這個階段最多需要問 10 次。
2. 將 100 層樓分成 10 組, 每組 10 層。
- 分法 [201, 210], [211, 220], ..., [291, 300]
- 每次依序由小到大詢問每組的最小樓層, (ex. 201, 211, 221, 231, ..., 291)
- 可以找到破跟不破的交界點(以下舉例251層不破, 261層破裂。), 因此可以知道答案介於[251, 260]這 10 層之間。
- 這個階段最多需要問 10 次。
3. 剩下 10 層樓,
- 直接由小到大一層一層問, 問到破跟不破的交界極為答案。
- 這個階段最多需要問 10 次。
總共最多需要問 30 次

:::info
此題有策略可以在最多19詢問次數找到答案
:::
## E - Rainbow Numbers
> 給 Rainbow Numbers 定義。
> 給一區間 [L, R] 問這之間的數有幾個 Rainbow Numbers。
> [name=hanayukii]
### 先備知識
此題使用的技巧為經典的 [數位DP](https://oi-wiki.org/dp/number/)。
### 轉為求前綴
我們想求 [L,R] 中有幾個滿足條件的數，可透過求 [1, R] 扣掉 [1, L - 1]得到。
### 求解前綴
現在要求解 [1, X] 有幾個解，先求得 X 每一位的數字。
套用數位 DP 格式。
定數位 DP 狀態為 dp[pos][lim][last][use]
- pos : 目前在的位數
- lim : 高位是否皆用至上限
- last : pos + 1 位置使用的數字
- use : 高位是否用過非 0 數字

若 lim 為 0，則此位可使用 [0, 9]，否則僅可使用[0, x 此位值]
若 use 為 0，此位可任意使用，否則須與 last 不同。

### 複雜度
數字長度僅至 100, dp表的大小為 dp[100][2][10][2], 轉移也僅需O(1)枚舉下一位使用數字
複雜度 $O(log{N})$