POJ 1003解題レポート

1.問題の説明:
http://poj.org/problem?id=1003
2.問題の解き方:
最も直観的な考え方は、通項式を直接求めて直接計算すればいいのではないかということですが、このような良い水の様子は、この通項式が求められるかどうか、精度がどうなのか分かりません.
 
タイトルには0.01と5.20の入力があり、最後に求めたカード数が必ず1-300の間にあることが判明しているので、1-300枚のカードがそれぞれ積み上げられるoverhangの長さを予め求めることができる.
そして二分検索で作ります.具体的なコードは以下の通りです.

/*

    author: obalama

    date: 2013.07.24

    email: [email protected]

*/

#include <iostream>

#include <vector>

#include <iterator>

using namespace std;

int main()

{

    /*preprocessing*/

    double table[288];

    for(int i = 0;i<288; ++i)

    {

        if(i==0)table[i] = 1/2.0;

        else table[i] = table[i-1] + 1.0/(i+2);

    }

    vector<int> result;

    double cur;

    cin>> cur;

    while(cur-0>0.00001)

    {

        int head=0;

        int end = 277;

        int mid = (head + end)/2;

        while(table[mid] != cur)

        {

            if(table[mid] < cur)

            {

                head = mid +1;

            }

            else

            {

                end = mid -1;

            }

            if(head > end) break;

            else mid = (head + end)/2;

        }

        int maxNum;

        if(table[mid] >= cur)maxNum = mid +1;

        else

            maxNum = mid +2;

        result.push_back(maxNum);

        cin>> cur;

    }

    vector<int>::iterator iter;

    for(iter = result.begin(); iter != result.end(); ++iter)

    {

        cout<<*iter<<" card(s)"<<endl;

    }

    return 0;

}