A. Valera and Plates
題意: Valera 要吃東西,吃 A 時用bowl , 吃 B 時可用bowl/plate 。一開始n 個 bowl 和 m 個 plate 。如果沒有餐具 Valera
就要洗餐具,一次只能洗一個。問 Valera 最少要洗幾個。
題解: 吃 A 只能用 bowl ,所以先將 bowl 用完。因為 A只能用 bowl ,不夠的話,就要洗。 若還剩下 nb 個 bowl 可留下來裝 B。
接下來考慮 B 的情況,若 m + nb 大於 B 的使用量,就不用洗,若小於,就要洗差值。
B. Valera and Contest
題意: 有 n 個數,已知前 k 大的數合是 sk ,總合是 sn。每個數字一定是在[l,r] 這個範圍。
現在想要還原符合條件的n 個數各是多少?
題解: 用到平均數的概念, 前 k 大每個數至少是 sk/k ,(sk%k) 個數在加 1。同樣的道理也用在後 (n-k)個數。
C. Valera and Elections
題意: 有 n 個 district , n - 1 個 road 去連接,這 n 個 district 形成一個 tree 。 road 的 type 分
成2種,一種是 good road ,另一是 bad road 。現在有 n 個 candidate 要參與競選,若 ni 當選,則
他會去修 district i 到 district 的 road 。問最少幾個人當選,可以讓所有的 road 都修好?
題解:將 district 1 當成 root ,接下來可以有以下推論:
f( i ) =
1. if edge (i,neighbor(i)) is bad
A. f(neighbor(i) ) > 0 then add f(neighbor(i))。
B. f(neighbor(i) ) = 0 then add 1.
2. add f(neighbor(i))
