g309: pC. 傳遞杯子蛋糕(Cupcake)
Tags : tree
Accepted rate : 20人/20人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-14 21:11

Content

在動物王國中,為了建立良好的傳遞網路,

每個動物都會有左右需要傳東西的人,我們稱之為「左節點」和「右節點」。

其中根節點為動物王國的國王,即動物0

 

當動物拿到 K 個東西後,會將所拿到的東西以 (自己 + 子節點數量) 做均分,

均分完的等份,分別傳遞給其左節點、右節點和自己做保留;

若無法均分時,則會將剩下的個數優先保留給自己。

其子節點則繼續這個過程,直到沒有任何子節點為止。

 

以上圖為例,假設動物0 拿到 9 個東西,則會其均分為三等份後,

其中 3 個傳給左邊的動物1(如紅字所示),另外 3 個傳給右邊的動物2剩下 3 個則自己保留(螢光黃所示)

依序同理,最後每個動物所能夠得到的物品數量如螢光黃所示。

 

現在已知有 N 個動物,以及動物間的左右節點關係,

假設動物國的國王動物得到了 K 個杯子蛋糕,

請問依照上述傳遞規則,每個動物最後分別可以得到幾個杯子蛋糕?

Input

第一行有兩個正整數 N 和 K

代表總共有 N 個動物 ( 1 ≤ N ≤ 10 ),動物編號依序為 0, 1, ..., N-1

並且有 K 個杯子蛋糕要由動物開始往下傳送

 

接著依序有 N 行,每行有三個整數 a ( 0 ≤ a ≤ N-1 )、L 和 R ( -1 ≤ L, R ≤ N-1 )

代表動物a 的左子節點為 L,右子節點為 R

如果沒有該子節點,則以 -1 表示;並且動物0 必定為根節點

 

Output

由左至右,分別印出 動物0, 動物1, ..., 動物N-1 最後可得的杯子蛋糕數量

Sample Input #1
6 9
0 1 2
1 3 4
2 5 -1
3 -1 -1
4 -1 -1
5 -1 -1
Sample Output #1
3 1 2 1 1 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1K
公開 測資點#2 (14%): 1.0s , <1K
公開 測資點#3 (14%): 1.0s , <1K
公開 測資點#4 (14%): 1.0s , <1K
公開 測資點#5 (15%): 1.0s , <1K
公開 測資點#6 (15%): 1.0s , <1K
Hint :
Tags:
tree
出處:
110學年度hgsh校內賽 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
27162
r1cky (APCS實作兩級分)
g309
Java 解題心得
28 2021-09-15 21:12