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
题意:将一份财产分成n份,1/x1, 1/x2, 1/x3, ...,1/xn.使得x1>x2>x3>...>xn,让教堂分得的财产最少.xn = x1 * x2 * ...*xn-1 + 1.
如果前k个分剩下1/c,因为1/c>1/(c+1)>1/(c+2)>...所以下一个拿1/(c+1),剩下1/(c * (c+1)).
#include<stdio.h>
#include<stdlib.h>
#define inf 1000000000
#define maxn 100000
int len1, len2, len3, len[18];
long long a[maxn], b[maxn], ans[maxn], res[18][maxn];
void setAns()
{
for (int i = 0; i < len3; i++)
{
ans[i] = 0;
}
}
void copy()
{
for (int i = 0; i < len3; i++)
{
a[i] = ans[i];
}
len1 = len3;
}
void multiply()
{
int i, j;
setAns();
for (i = 0; i < len2; i++)
{
for (j = 0; j < len1; j++)
{
ans[i+j] += a[j] * b[i];
ans[i+j+1] += ans[i+j] / inf;
if (ans[i+j+1] && len3 <= i + j + 1)
{
len3 = i + j + 2;
}
else if (len3 <= i + j)
{
len3 = i + j + 1;
}
ans[i+j] %= inf;
}
}
}
void plus()
{
int r;
for (len2 = 0, r = 1; len2 < len1; len2++)
{
r += a[len2];
if (r >= inf)
{
b[len2] = r - inf;
r = 1;
}
else
{
b[len2] = r;
r = 0;
}
}
if (r)
{
b[len2++] = r;
}
}
int main()
{
int i, j, n;
scanf("%d", &n);
a[0] = 2;
len1 = 1;
printf("2\n");
for (i = 2; i <= n; i++)
{
plus();
printf("%lld", b[len2-1]);
for (j = len2 - 2; j >= 0; j--)
{
printf("%.9lld", b[j]);
}printf("\n");
if (i < n)
{
multiply();
copy();
}
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告