首页 > 代码库 > Heritage（高精度）

Heritage（高精度）

2024-07-15 02:17:51   227人阅读

Description

Your rich uncle died recently, and the heritage needs to be divided among your relatives and the church (your uncle insisted in his will that the church must get something). There are N relatives (N <= 18) that were mentioned in the will. They are sorted in descending order according to their importance (the first one is the most important). Since you are the computer scientist in the family, your relatives asked you to help them. They need help, because there are some blanks in the will left to be filled. Here is how the will looks: 

Relative #1 will get 1 / ... of the whole heritage, 
Relative #2 will get 1 / ... of the whole heritage, 
---------------------- ... 
Relative #n will get 1 / ... of the whole heritage. 

The logical desire of the relatives is to fill the blanks in such way that the uncle‘s will is preserved (i.e the fractions are non-ascending and the church gets something) and the amount of heritage left for the church is minimized.

Input

The only line of input contains the single integer N (1 <= N <= 18).

Output

Output the numbers that the blanks need to be filled (on separate lines), so that the heritage left for the church is minimized.

Sample Input

2

Sample Output

2
3

解题思路：

题目大意是财产分割，每个人分的钱从前往后越来越少，最后必须给教堂留一部分最少的钱。这题第一个人一定只能拿1/2，后面一个人只能拿剩下的1/2，而由于要给教堂留一部分钱所以最多只能拿1/3，接着下一个人只能拿剩下的1/6，由于也要给教堂留一部分钱，所以最多只能拿1/7，因此每个人拿的钱都是从剩下的1/x中拿走1/(x + 1)。通过类比归纳可以发现如果第n-1个人拿了1/a，则第n个人拿了1/((a - 1)*a + 1)。虽然公式很简单，是一个数列，但动笔写写就会发现，越往后，数字越大，成指数倍增长，必须得用高精度来做。数组开多大可以计算一下，我算出第18个数位数最多达到2^15个，所以开5万数组应该是够了。不过我依然开了10万，多开总比开少了好嘛。。。一开始把数组全初始化，控制前导零来做，结果TLE了，还是考虑过于简单，10万数组初始化来做高精度不TLE才怪呢。还是老老实实地去计算每个数的位数吧，总算AC了。。。。为了达到种种目的导致代码写得很挫，不过AC才是王道嘛。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 50000;
int a[20][maxn], b[maxn], len[20];
void Fun(int n)
{
    a[1][0] = 2;
    len[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        int len_1 = len[i - 1];
        int d = 0;
        for(int j = 0; j < len_1; j++)
        {
            if(j == 0)
                b[0] = a[i - 1][0] - 1;
            else
                b[j] = a[i - 1][j] + d;
            if(b[j] < 0)
            {
                b[j] += 10;
                d = -1;
            }
            else
                d = 0;
        }
        for(int j = 0; j < len_1; j++)
            for(int k = 0; k < len_1; k++)
                a[i][j + k] += a[i - 1][j] * b[k];
        a[i][0] += 1;
        a[i][len_1 * 2 - 1] = 0;
        for(int j = 0; j < len_1 * 2 - 1; j++)
        {
            if(a[i][j] >= 10)
            {
                a[i][j + 1] += a[i][j] / 10;
                a[i][j] %= 10;
            }
        }
        if(a[i][len_1 * 2 - 1])
            len[i] = len_1 * 2;
        else
            len[i] = len_1 * 2 - 1;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    Fun(n);
    for(int j = 1; j <= n; j++)
    {
        for(int i = len[j] - 1; i >= 0; i--)
        {
                printf("%d",a[j][i]);
        }
        printf("\n");
    }
    return 0;
}



联系
我们