b038: 存量問題
Tags : 模擬
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-30 16:25

Content

 

猴子島上有個傳統,猴王專向其他猴子從採收 的香蕉中抽成 ,但自己不採香蕉。

島上除猴王外有 20 隻猴子,每隻猴子每天固 定採收 80 根香蕉。 第 1 天猴王向 20 隻猴子各收 1 根香蕉,第 2 天也向 20 隻猴子各收 1 根香蕉,第 3 天之後 每天各收先前兩天所抽香蕉數的總和 (即:第 3 天,各收 2 根(1+1);第 4 天,各收 3 根 (1+2);第 5 天,各收 5 根(2+3),… 依此類推)。

然而,猴王抽成來的香蕉不新鮮,隔天有一半 (或近一半), 即 香蕉數×0.5 (註 1)會壞掉。例如: 第 4 天時,前 3 天猴王抽成來的 55 根香蕉,會壞掉 27 根,剩 28 根, 第 4 天,新收 60 根, 第 4 天結束時,猴王有 88 根香蕉。 其他猴子擁有的香蕉比較新鮮,所以不會壞掉。

日子如此這般,當某天猴王收走其他猴子們所有的香蕉後,猴子們立即會發生暴動並選出 新猴王。此時,舊猴王必須發給新猴王以外的每一個猴子(包括自己共 20 隻)各 N 根香蕉, 剩餘的香蕉則由新猴王擁有。而 N 符合這樣條件:

N * 20 <= 舊猴王原擁有總數 * 95%

(N+1) * 20 > 舊猴王原擁有總數 * 95%

N 為正整數

例如:第 14 天原猴王有 10912 根香蕉,其他猴子各有 134 根香蕉,第 15 天每隻猴子又 採了 80 根香蕉變成 214 根,但猴王依照算法當天要收 610 根,全部香蕉給猴王之後,都 還不夠,所以引發暴動並產生新猴王。如前述之方式重分配後,新猴王拿到 496 根香蕉, 其他猴子(包括舊猴王) 則留下 462 根香蕉,然後下一天新猴王又向大家收 1 根香蕉,再一 天 1 根香蕉,再來 2 根香蕉,依此類推。 島上資源有限,所以總猴子數為固定 21 隻。

註 1: 向下取整

Input

一個正整數t,表示第t天,因為猴子一百萬年前就有,1 <= t <= 100000000

Output

輸出猴子(非猴王)第t天擁有的香蕉數量。

Sample Input
//#1
2
//#2
28
//#3
65
//#4
15
Sample Output
//#1
158
//#2
893
//#3
893
//#4
462
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :
Tags:
模擬
出處:
2019YTP [管理者:
810848 (路過)
]


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