i185: 蝸牛老師的金幣
Tags : games
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-04 00:18

Content

自從臨末偷吃蝸牛老師的冰棒和偷喝蝸牛老師的雪碧後,他最近又更得寸進尺了,他開始會偷拿蝸牛老師的金幣巧克力來吃!

蝸牛老師看不下去了,這次,他決定要再來跟臨末玩一個遊戲!

蝸牛老師準備了$K$個金幣巧克力,並且找了$N-1$個學生來跟臨末玩一個「分金幣」的遊戲,他首先讓這$N-1$個學生排成一列,接著讓臨末排在這$N-1$個學生後面。

遊戲規則如下:


● 由當前隊伍最前面的學生開始提議一種金幣的分法。
● 接著由當前隊伍後面的所有人一一表示是否同意最前面的人的分法。
● 如果同意的人數超過當前隊伍人數的$\frac{P}{100}$(不包含),那就採取這種分金幣的方式。
● 如果同意的人數沒有超過當前隊伍人數的$\frac{P}{100}$,則隊伍最前方的人會退出遊戲,並且重新由當前隊伍最前方的人提議分金幣的方法。

而這$N-1$個學生跟臨末都非常聰明,會以最佳策略進行遊戲,意即:


● 每個人都知道自己所做的決定會產生的後果。
● 每個人都會爲自己追求最大化的利益。
● 每個人都會盡可能想辦法留在隊伍中,因為這樣還可以順便翹課。
● 為了分得更多金幣,他們希望能讓越多人退出遊戲越好。

你想事先知道這場遊戲最後的結果會如何,於是寫了一個程式來模擬!

Input

輸入包含三個正整數$N,K,P$,分別代表遊戲人數、金幣數量、同意人數比例。

$1 \leq N \leq 5 \times 10^3$

$1 \leq K \leq 10^9$

$1 \leq P \leq 100$

Output

請輸出$N$個整數,代表這$N$個人最後可以分到的金幣數,但是由於答案可能不具有唯一性,所以請將這$N$個人能分到的金幣數排序好後以大到小輸出!

Sample Input #1
2 10 50
Sample Output #1
10 0 
Sample Input #2
3 10 60
Sample Output #2
10 0 0 
Sample Input #3
4 2 50
Sample Output #3
1 1 0 0 
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (3%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (6%): 1.0s , <1K
公開 測資點#7 (6%): 1.0s , <1K
公開 測資點#8 (7%): 1.0s , <1K
公開 測資點#9 (7%): 1.0s , <1K
公開 測資點#10 (7%): 1.0s , <1K
公開 測資點#11 (7%): 1.0s , <1K
公開 測資點#12 (4%): 1.0s , <1K
公開 測資點#13 (4%): 1.0s , <1K
公開 測資點#14 (4%): 1.0s , <1K
公開 測資點#15 (4%): 1.0s , <1K
公開 測資點#16 (4%): 1.0s , <1K
公開 測資點#17 (6%): 1.0s , <1K
公開 測資點#18 (6%): 1.0s , <1K
公開 測資點#19 (6%): 1.0s , <1K
Hint :

在第一筆範例中,有兩個人要分金幣,並且同意人數必須超過50%(不包含),不管第一個人怎麼提議,第二個人只要都否決就可以自己獨吞10枚金幣,於是最後金幣的分法將會是10枚、0枚。

在第二筆範例中,有三個人要分金幣,並且同意人數必須超過60%(不包含),不管第一個人怎麼提議,第二個人都必須支持他,因為如果他不支持他,他就必須面臨只與第三個人共兩人分金幣的情況,他不但一樣得不到金幣,還會被移出隊伍,於是最後金幣的分法將會是10枚、0枚、0枚。

在第三筆範例中,有四個人要分金幣,並且同意人數必須超過50%(不包含),第一個人為了確保自己還留在隊伍中,必須提議把金幣各分一個給第三、四個人,而他們會接受,因為他們知道,如果他們讓第一個人離開了隊伍,兩個金幣都會落到第二個人手上,於是最後金幣的分法將會是1枚、1枚、0枚、0枚。

------------------------------------------------------------------------------------------------------------------------------------------

$12\%:N≤3$ 
$22\%:P=50$ 
$28\%:K=N$ 
$38\%:無特殊限制 $

Tags:
games
出處:
蝸牛與臨末之頌 [管理者: Ststone1687(使用C++的都邪教) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」