水槽 (AP325 Q-2-14)

我們用一排 \(n\) 個擋板建造水槽。擋板的寬度為 \(1\)，高度為正整數且均不相同，水槽前後是兩片長寬均為無限大的玻璃板（見下圖例）。相鄰擋板的距離都是 \(1\)，故相鄰二擋板之間會形成底面積為 \(1\) 的水槽。

擋板由左而右依序由 \(0\) 到 \(n - 1\) 編號，第 \(i\) 及 \(i + 1\) 擋板中間的水槽稱為水槽 \(i\)。現在將總量為 \(w\) 立方公分的水緩緩注入水槽 \(i\)。注意水量可能溢出到別的水槽，但是由於所有擋板高度都不同，所以每當溢出時，只會先從一個方向溢出。請計算將總量為 \(w\) 立方公分的水緩緩注入水槽 \(i\) 後，所有水槽的水深。本題最左的擋板與最右的擋板是所有擋板中最高的兩個，並且保證欲注入的水不會溢出到左右邊界之外；另外，所有水槽的最後水深一定都是整數。以下圖為例，於水槽 \(2\) 注入 \(17\) 立方公分的水後，各水槽的水深依序為 \(5, 5, 5, 1, 1, 0\)。

輸入格式

第一行有三個正整數 \(n\)、\(i\) 和 \(w\)，分別代表擋板數、注水水槽編號，及水量。第二行有 \(n\) 個以空白間隔的正整數，代表由左到右擋板的高度。請注意注水量可能超過一個 32-bit 整數的範圍。

限制

• \(3 \le n \le 10^5\)。
• \(0 \le i \le n - 2\)。
• \(1 \le w \le 10^{12}\)。
• 每個擋板高度為正整數且不超過 \(10^9\)，所有擋板高度互不相同。
• 最左與最右的擋板是所有擋板中最高的兩個；保證水不會溢出到左右邊界之外，且所有水槽的最後水深都是整數。

輸出格式

輸出為一行，共 \(n - 1\) 個整數，依序代表各個水槽水深，數字之間以一個空白間隔。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

8 3 27
9 7 5 3 4 6 8 10

範例輸出

0 6 6 6 6 3 0

範例說明

水先在水槽 \(1\) 到 \(4\) 之間蓄積（這一段裡最高的擋板 \(1\) 高 \(7\)、擋板 \(5\) 高 \(6\)）；水面升到 \(6\) 時（用掉 \(4 \times 6 = 24\)），剩下的 \(3\) 越過擋板 \(5\) 流進水槽 \(5\)，水槽 \(5\) 的水深為 \(3\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 2 章 Q-2-14，第 66 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。原題出自 108 學年度全國高級中等學校資訊學科能力競賽。