a625. 5. Overhanging Cards

題目 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 了