Codeforces Round #289 (Div. 2) (pA ~ pC)

這場比賽同時也是俄羅斯某個營隊的資格賽，採 ICPC 制，就我看來 pC~pF 難度沒有太大差別。

Problem A --- Maximum in Table

題意：有一個 $n \times n$ 表格 $a$，第一行和第一列所有格子都是 $1$，而其它的格子都滿足 $a_{i,j} = a_{i-1,j} + a_{i,j-1}$ ，求此張表格內最大的數。

數據範圍：$1 \le n \le 10$

tag：[ dp ] [ 數學 ]

就是個希望所有人都 AC 的題目，由於 $n$ 很小，直接從左到又再從上到下 dp 就行了，你只要這麼做之後再從表格中找最大的數就可以 AC。

但你可以再進一步的推論出

1. 表格中最大的數一定在右下角 (why?)

2. 表格中每個數會對應到巴斯卡三角形的某一個數。(想想看 $a_{i,j}$ 會對應到 $C^?_?$？)

所以實際上題目變成 $n$ 若高達 $1,000,000$ 並求最大的數 mod $1,000,000,007$ 也是可解的。

Problem B --- Painting Pebbles

題意：有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 顆石子，你有 $k$ 種不同顏色的油漆，要把所有石子都塗上顏色，使得同一種顏色的石子個數在不同堆裡至多差 $1$。若有辦法塗就給出一種塗法。否則輸出 NO 即可。(可以有顏色在某堆個數為 $0$)

數據範圍：$1 \le n, t \le 100$，$1 \le a_i \le 100$

tag：[ greedy ]

乍看之下可能會不知道從何想起，這種時候我們就從簡單的 case 想起吧！怎樣叫做簡單的 case ?例如說，當只有一堆的時候，但在這題只有一堆的結論太顯然了 XD，所以我們從兩堆開始考慮。我們會發現，當兩堆的個數差不超過 $k$ 時總是可以構造出解 (how?)，並且你可以推出不等式 $\sum_1^k{b_{1,c}} - \sum_1^k{b_{2,c}} \le k$，於是當 $n$ 為 $2$ 時我們會做了！

接著考慮有 $n$ 堆的情形，不難想像結論就是最大堆的個數和最小堆的個數不超過 $k$，至於怎麼構造呢～就留給大家自己想吧～

我的構造法：(以下反白) 設最小堆的石子個數為 $mi$，則每堆石子都先塗上 $mi$ 個第一種顏色，之後若某堆石子數還有 $s$ 顆石子尚未塗色，就分別塗上第 $1$ 至第 $s$ 種顏色。

Problem C --- Sum of Digits

題意：有一個數列 $a$ 含 $n$ 個數，且為嚴格遞增，已知第 $i$ 個數所有位數總和為 $b_i$，求最小的可能 $a_i$ 值。

數據範圍：$1 \le n \le 300$，$1 \le b_i \le 300$

tag： [greedy] [進位]

這題雖然是 pC，主要的 idea也不難，但我卻最後寫它，因為我覺得他很容易寫出 bug (事後看 scoreboard確實如此)。

首先會發現我們一直貪心的構造 $a_i$，構造的方法為令 $a_i$ 為大於 $a_{i-1}$ 且總合為 $b_i$ 的最小的數 (可以假設 $a_0 = 0$)，如此一來一定能使 $a_n$是所有可能中最小的。

所以此問題可以藉由解 "求大於 $x$ 且位數和為 $y$ 的最小的數(問題1)" n 次得到。

若第一次接觸到這類問題可能會覺得並不簡單。我們先想想一個比較簡單的問題：

請求出位數和為 $y$ 的最小的正整數。

這應該不太困難，貪心地從位數低到高一直都填 $9$，直到總和快要超過 $y$ 時改成填 $y mod 9$。

會做這個問題後再回來解問題1，我們枚舉 $x$ 有變動的最高位數，有變動的最高位當然位置愈小愈好，接著我們再枚舉該位要變成哪個數字，例如說若該位是 '7' ，那就只能變成 '8' 或 '9'。枚舉完後，由於我們已經確定 $x$ 已經變大了，剩下的比較低的位數就貪心的填最小的數即可。但若就算全填 '9' 也無法使得總合為 $y$，則繼續枚舉下一個。

看到這裡或許你已經知道怎麼做了，但實作過程還是可能有很多大大小小 bug，請自己多家小心吧Orz

最後我想再考考大家一個問題：在這樣的數據範圍下，答案最多可能會有幾位呢～？
(我想有些人的 bug 是因為這樣產生的，翻了幾份 code 也確實有這樣的 bug)