自從臨末偷吃蝸牛老師的冰棒和偷喝蝸牛老師的雪碧後,他最近又更得寸進尺了,他開始會偷拿蝸牛老師的金幣巧克力來吃!
蝸牛老師看不下去了,這次,他決定要再來跟臨末玩一個遊戲!
蝸牛老師準備了$K$個金幣巧克力,並且找了$N-1$個學生來跟臨末玩一個「分金幣」的遊戲,他首先讓這$N-1$個學生排成一列,接著讓臨末排在這$N-1$個學生後面。
遊戲規則如下:
● 由當前隊伍最前面的學生開始提議一種金幣的分法。
● 接著由當前隊伍後面的所有人一一表示是否同意最前面的人的分法。
● 如果同意的人數超過當前隊伍人數的$\frac{P}{100}$(不包含),那就採取這種分金幣的方式。
● 如果同意的人數沒有超過當前隊伍人數的$\frac{P}{100}$,則隊伍最前方的人會退出遊戲,並且重新由當前隊伍最前方的人提議分金幣的方法。
而這$N-1$個學生跟臨末都非常聰明,會以最佳策略進行遊戲,意即:
● 每個人都知道自己所做的決定會產生的後果。
● 每個人都會爲自己追求最大化的利益。
● 每個人都會盡可能想辦法留在隊伍中,因為這樣還可以順便翹課。
● 為了分得更多金幣,他們希望能讓越多人退出遊戲越好。
你想事先知道這場遊戲最後的結果會如何,於是寫了一個程式來模擬!
輸入包含三個正整數$N,K,P$,分別代表遊戲人數、金幣數量、同意人數比例。
$1 \leq N \leq 5 \times 10^3$
$1 \leq K \leq 10^9$
$1 \leq P \leq 100$
請輸出$N$個整數,代表這$N$個人最後可以分到的金幣數,但是由於答案可能不具有唯一性,所以請將這$N$個人能分到的金幣數排序好後以大到小輸出!
2 10 50
10 0
3 10 60
10 0 0
4 2 50
1 1 0 0
在第一筆範例中,有兩個人要分金幣,並且同意人數必須超過50%(不包含),不管第一個人怎麼提議,第二個人只要都否決就可以自己獨吞10枚金幣,於是最後金幣的分法將會是10枚、0枚。
在第二筆範例中,有三個人要分金幣,並且同意人數必須超過60%(不包含),不管第一個人怎麼提議,第二個人都必須支持他,因為如果他不支持他,他就必須面臨只與第三個人共兩人分金幣的情況,他不但一樣得不到金幣,還會被移出隊伍,於是最後金幣的分法將會是10枚、0枚、0枚。
在第三筆範例中,有四個人要分金幣,並且同意人數必須超過50%(不包含),第一個人為了確保自己還留在隊伍中,必須提議把金幣各分一個給第三、四個人,而他們會接受,因為他們知道,如果他們讓第一個人離開了隊伍,兩個金幣都會落到第二個人手上,於是最後金幣的分法將會是1枚、1枚、0枚、0枚。
------------------------------------------------------------------------------------------------------------------------------------------
$12\%:N≤3$
$22\%:P=50$
$28\%:K=N$
$38\%:無特殊限制 $
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|