題目 Problem#
題目連結：https://zerojudge.tw/ShowProblem?problemid=a625
敘述 Description#
你可以把一疊的卡片凸出桌子的邊緣多遠呢？如果你有一張卡，你最大可以凸出卡片長度的一半。有兩張卡時，你可以把上面那張的一半凸出下面的那張，而下面的那張則有三分之一凸出桌子的邊緣，總凸出長度則為$ 1/2 + 1/3 = 5/6 $張卡片長度。總之，你可以把$ n $張卡片凸出$ 1/2 + 1/3 + 1/4 + … + 1/(n+1) $張卡片的長度，其中最上面那張凸出$ 1/2 $於第二張的外面，第二張凸出$ 1/3 $於第三張的外面，第三張凸出$ 1/4$，以此類推，最底下那張則凸出$ 1/(n+1)$。如下圖所示。
輸入 Input#
每筆測資一行，含有一個正浮點數 c (代表所要凸出的總長度)，其值最小為 0.01，最大為 5.20；這個數含有三位數字。
輸出 Output#
輸出要達成所需的凸出長度最少需要幾張卡片。請參照範例輸出的格式。
範例輸入 Sample Input#
1.00
3.71
0.04
5.19
範例輸出 Sample Output#
3 card(s)
61 card(s)
1 card(s)
273 card(s)
提示 Hint#
題解 Solution#
$1$張卡片長度為$1/2$ $2$張卡片長度為$1/2+1/3$ $3$張卡片長度為$1/2+1/3+1/4$ $…$以此類推$…$ $n$張卡片長度為$1/2+1/3+1/4+…+1/(n+1)$ 先建表，最大卡片數頂多$276$張 最後再用二分搜尋找卡片數就好
程式碼 Accepted Code#
#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
_
double query[277]={0},a=0.0;
for(int i=1;a<=5.20;i++){
a+=(1.0/(i+1));
query[i]=a;
}
double enter;
while(cin>>enter){
int l=0,r=277;
while(l+1<r){
int mid=(l+r)/2;
if(enter>query[mid]){
l=mid;
}
else{
r=mid;
}
}
cout<<l+1<<" card(s)"<<'\n';
}
return 0;
}
後記 Afterword#
這一題在 ICPC Live Archive 跟 POJ 找得到 ICPC Live Archive 題目代碼：2294 - Hangover POJ 題目代碼：1003 - Hangover ZeroJudge 拿到 AC 之後 就到 ICPC Live Archive 繳交，但直接被 WA 掉 我還以為是我二分搜寫錯 但仔細看了它們的 Input 後 才知道程式輸入$0.00$才會結束 改完這題就 AC 了