ETH官方钱包

前往
大廳
主題

ZeroJudge - a625: 5. Overhanging Cards 解題心得

Not In My Back Yard | 2021-09-14 00:00:09 | 巴幣 2 | 人氣 225

題目連結:


題目大意:
輸入有多列,每列給定一浮點數 c(0.01 ≦ c ≦ 5.20,且 c 為兩位小數),代表著目標值。試問滿足
1 / 2 + 1 / 3 + 1 / 4 + …… + 1 / (n + 1) ≧ c
最小正整數 n 值為何?輸出格式參見範例輸出。



範例輸入:
1.00
3.71
0.04
5.19


範例輸出:
3 card(s)
61 card(s)
1 card(s)
273 card(s)


解題思維:
從範例輸入的 c = 5.19 時 n 值為 273,可以看到其 n 值並不會太大(即使極限的測資 c = 5.20,n 值實際上也只到 276)。因此我們可以直接對 n 值建表——對每個 n 值求出
1 / 2 + 1 / 3 + 1 / 4 + …… + 1 / (n + 1)
之值為何並儲存起來。

最後對於每個 c 值線性(或是二分搜尋法(Binary Search)也行)去找最小的、符合題意的 n 值即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作