TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

59.4% (41/69)

Submission's AC Ratio

22.7% (116/512)

Tags

Description

你聽過樓下的房客嗎?

據說,在一個遙遠的國度,有個名叫希爾伯特的人,收了無限多個房客。雖然希爾伯特的房間已經住滿了,然而這些房客住的房間編號是從0開始的全體非負整數,所以不管來了多少(可數個)房客,希爾伯特總是能收容他們,不過這又是另一個故事了。

話說有一次,希爾伯特煮了幾個鬆餅給前 $n$ 個房客吃,其中住在編號是 $i$ 的房客拿到了 $P_i$ 個鬆餅。然而這些鬆餅很容易就冷掉了,所以這些房客決定和其它房客共享鬆餅。在每一分鐘,每個房客可以吃掉一個鬆餅,或者分一些些鬆餅給另一個房客(不一定要是前 $n$ 個房客)。然而希爾伯特並不喜歡自己的好意一直不斷地被這樣分發掉(看起來他很傲嬌),所以他規定房客們分鬆餅的總次數不能超過一個數 $B$ 。儘管如此,這些房客還是想要在最快的時間內將鬆餅吃完。然而,無窮多個人聚在一起討論是一件非常麻煩的事,所以這些人拜託你,希爾伯特的學生,解決他們的煩惱。

如果你失敗的話,你會被無限多個人圍毆至死。
如果你成功的話,你會解出希爾伯特的第三個問題。

Input Format

第一行有兩個整數 $1\leq n\leq 10^ 5, 0\leq B\leq 10^ 6$,代表前 $n$ 個房客拿到了鬆餅而且他們總共只能分鬆餅 $B$ 次。
緊接著的一行有 $n$ 個正整數 $P_0, P_1,\dots, P_{n-1}$ ,其中 $P_i\leq 10^ 6$ 代表第$i$個人拿到的鬆餅數。

子任務(測資) 額外限制 分數
1 (0~4) $B\leq 25$ 13
2 (5~9) $B\leq 75$ 12
3 (10~14) 無限制 75

Output Format

請輸出一行代表所有鬆餅最快能在幾分鐘內吃完。

Sample Input 1

3 2
3 4 9

Sample Output 1

5

Hints

一種在五分鐘內吃完的方法:
第一分鐘時編號0, 1的房客吃一個鬆餅,編號2的房客分給編號3的房客三個鬆餅。
第二分鐘時編號0,1,3的房客吃一個鬆餅,編號2的房客分給編號4的房客三個鬆餅。
接下來的時間大家都自己吃自己的鬆餅。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pE
題目取自2015 TOI第二階段選訓第三次模擬考pC

Subtasks

No. Testdata Range Score
1 0~4 13
2 5~9 12
3 10~14 75

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3