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

最近更新 : 2023-02-26 19:37

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 \times 20 \leq 舊猴王原擁有總數 \times 95\%$

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

$N$ 為正整數

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

 

註 1: 向下取整

Input

一個正整數 $t$, 表示第 $t$ 天

因為猴子一百萬年前就有,$1 \leq t \leq 100000000$

Output

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

Sample Input #1
2
Sample Output #1
158
Sample Input #2
28
Sample Output #2
893
Sample Input #3
65
Sample Output #3
893
Sample Input #4
15
Sample Output #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
沒有發現任何「解題報告」