#31012: 想法


dfd8282@gmail.com (fishhh)

School : 嘉義市私立嘉華高級中學
ID : 99760
IP address : [163.27.13.253]
Last Login :
2024-05-23 11:00:10
a249. 00679 - Dropping Balls -- UVa679 | From: [36.236.19.36] | Post Date : 2022-07-03 00:56

比較直觀一點的解法:?

先設總共會有d層、x顆球、最後一顆球目前所在的id=1(題目有說

那麼先假設一下,一層會經過的有x顆。

那麼,最後一顆球的在下一層的 id 就會是 id*2+(x%2),會跟著最後一顆球跑到下一層的只有 x/2+(x%2)顆

(如果無法理解 可以再腦中模擬x=1,x=2,x=3自id=1的點掉下去會變怎樣

同樣的道理跑d-1次(因為只會掉落d-1次) 最後直接印出id就是答案囉~

剛剛測了一下,zj的compiler好像會優化掉*2的部分~

110學年彰雲嘉資訊學科初賽有出這題(一模一樣) 賽中我直接寫for迴圈一顆一顆模擬 然後還是糊到AC XD

 
ZeroJudge Forum