HDU 5879.Cure(2016 ACM/ICPC Asia Regional Qingdao Online)

567

题目


Description    


Given an integer n, we only want to know the sum of 1/k2 where k from 1 to n.




Input  


There are multiple cases.
For each test case, there is a single line, containing a single positive integer n.
The input file is at most 1M.



Output  


The required sum, rounded to the fifth digits after the decimal point.



Sample Input  


1
2
4
8
15



Sample Output  


1.00000
1.25000
1.42361
1.52742
1.58044



题解


Σ1/n2
由于该式在 n→∞ 时,结果为 π<sup>2</sup>/6 ( ≈1.64493 )
由于只需要输出 5 位小数,因此当 n 足够大时,只需要输出一个确定值( 1.64493 )即可

本地调试测试可知,当数据大于 200000 时,就可以放心输出 1.64493
因此可以先打表计算 200005 内的值,当读入的数大于 200005 时,直接输出即可

由于 n 的大小不确定,因此应该高精度读入(注意前导 0 )
然后类似高精度的比较大小即可

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリ0隶�
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 200005;

LL n;
double ans[maxn];
char s[1000000];

char cmp[] = "200000";

int read_string(char s[]) {
    char c;
    int i = 0;
    while(!((c = getchar()) >= '1' && c <= '9'))
        if(c == EOF)
            return -1;
    while(c >= '0'&&c <= '9') {
        s[i++] = c;
        c = getchar();
    }
    s[i] = '\0';
    return i;
}

bool cmp_biger(char *a,char *b) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    if(len1 > len2)
        return true;
    else if(len1 == len2) {
        len1 = 0;
        while(a[len1] == b[len1] && len1 <= len2)
            len1++;
        if(len1 <= len2 && a[len1] > b[len1])
            return true;
        else
            return false;
    } else
        return false;
}

bool Do() {
    if(read_string(s) == -1)
        return false;

    //cout << cmp << " " << s << endl << "    ";

    if(cmp_biger(cmp,s)) {
        int len = strlen(s);
        n = 0;
        for(int i = 0;i < len;i++)
            n = n * 10 + s[i] - '0';
        cout << fixed << setprecision(5) << ans[n] << endl;
    } else {
        cout << "1.64493" << endl;
    }
    return true;
}


int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);


    ans[1] = 1.0;
    for(int i = 2;i < maxn;i++)
        ans[i] = ans[i - 1] + 1 / (double)i / (double)i;


    while(Do());

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论