poj 1032 Parliament
Parliament
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 20708 | Accepted: 8739 |
Description
New convocation of The Fool Land's Parliament consists of N delegates. According to the present regulation delegates should be divided into disjoint groups of different sizes and every day each group has to send one delegate to the conciliatory committee. The composition of the conciliatory committee should be different each day. The Parliament works only while this can be accomplished.
You are to write a program that will determine how many delegates should contain each group in order for Parliament to work as long as possible.
Input
The input file contains a single integer N (5<=N<=1000 ).
Output
Write to the output file the sizes of groups that allow the Parliament to work for the maximal possible time. These sizes should be printed on a single line in ascending order and should be separated by spaces.
Sample Input
7
Sample Output
3 4
议会
时限: 1000MS | 内存限制: 10000K | |
提交总数: 20708 | 接受: 8739 |
描述
愚人国议会的新召集由 N 名代表组成。根据现行规定,代表应分成不同规模的独立小组,每个小组每天必须派一名代表到调解委员会。调解委员会的组成应该每天都不同。议会只有在可以完成的情况下才能运作。
您将编写一个程序,该程序将确定每个组应包含多少代表,以使议会尽可能长时间地工作。
输入
输入文件包含一个整数 N (5<=N<=1000 )。
输出
将允许议会在尽可能长的时间内工作的组的大小写入输出文件。这些尺寸应按升序打印在一行上,并应以空格分隔。
样本输入
7
样本输出
3 4
解题思路:
先从0到n位列出从2开始的间隔为1的等差数列,直到第N位【值应当为N+1】使得余数left(等于输入值A减去前N个数之和)小于N+2;然后为了构造不同的值,将余数从N位到第一位开始每位加1,若有剩余循环执行。
以输入值A=8为例;可以构造数列2,3直到第N=2位,余数为3那肯定是小于N+2(4)的。依次从高位开始加1,一次循环【3,4】还有剩余1,再次执行【3,5】,然后结束。
代码:
#include
using namespace std;
int main()
{
int i;
int * array = new int[50];
int index=0;
int num=2;
while(cin>>i && i>=5 && i<=1000)
{
int sum=0;
for(int j=0;j<50;j++)
{
if(i-sum>num-1)
{
array[j]=num;
sum += num;
}
else
{
index = j;
i -= sum;
break;
}
num++;
}
num=i%index;
i=i/index;
for(int m=0;m array[m] += i;
for(i=index-1;i>index-num-1;i--)
array[i]++;
for(i=0;i cout< num=2;
cout< }
return 0;
}