Parliament
Time Limit: 1000MS
|
|
Memory Limit: 10000K
|
Total Submissions: 10936
|
|
Accepted: 4570
|
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
Source
Northeastern Europe 1998
先读懂题意:
题目要求的是对输入的正整数N,要求将N分解成互不相同的正整数的和,使分解出来的这些正整数的乘积最大。
解题思路:
先根据数学知识推导出一般式(别想着遍历所有可能的情况):
(以下证明是从网上得来的)
由题意知,这种分解的数目是有限的,因此,最大积存在;
假设最大积的分解为:
N=a1+a2+a3+...+a[t-2]+a[t-1]+a[t] (t是分解的数目,a1<a2<a3<...<a[t-2]<a[t-1]<a[t])
下面是该数列的性质及其证明:
1)a1>1;
如果a1=1,则a1和a[t]可以由a[t]+a1=a[t]+1来替代,从而得到更大的积;
2)对于所有的i,有a[i+1]-a[i]<= 2;
如果存在i使得a[i+1]-a[i]>=3,则a[i]和a[i+1]可以替换为a[i]+1,a[i+1]-1,从而使乘积更大;
3)最多只存在一个i使得a[i+1]-a[i]=2;
如果i<j且a[i+1]-a[i]=2、a[j+1]-a[j]=2,则a[i],a[j+1]可以替换为a[i]+1,a[j+1]-1,从而使得乘积更大;
4)a1<=3;
如果a1>=4,则a1和a2可以替换为2,a1-1,a2-1,从而使得乘积更大;
5)如果a1=3且存在i满足a[i+1]-a[i]=2,则i一定等于t-1;
如果i<t-1,则a[i+2]可以替换为2,a[i+2]-2,从而使得乘积更大;
将上面5条性质综合一下,得到该数列满足:
1)1<a1<4
2)a[i+1]-a[i] <=2(该序列按升序排序)
3)a[i+1]-a[i]=2的情况最多只有一个
因此,我们得到最大的乘积的做法就是求出从2开始的最大连续(由上面总结的性质2和3可知)自然数列之和A,使得A的值不超过N,具体分析如下:
对输入的N,找到k满足:
A=2+3+4+...+(k-1)+k <= N <A+(k+1) = B
假设N=A+p(0<=p<k+1),即A+p是最大积的数列
1)p=0,则最大积是A;
2)1<=p<=k-1,则最大积是B-{k+1-p},即从数列的最大项i开始,从大到小依次每项加1,知道p=0为止;
3)p=k,则最大积是A+p=A+k=A-{2}+{k+2};( =3+4+...+k+( k+2) );
代码如下:
#include <iostream>
int ans[200];
int main()
{
int N; //输入的整数
int sum = 0; //存储和
int i; //全局用到的
memset(ans,0,sizeof(ans)); //初始化数组
std::cin>>N;
for(i=2; sum<=N; i++) //累计和
{
ans[i] = i;
sum += i;
}//此处sum>N,因此下面需要减掉
i--; //抵消最后的i++
sum -= i;
int diff = N - sum; //计算差值
--i;//抵消倒数第二的i++
if(diff == i) //差值等于最后的ans[i]值
{
//最大积数列是( =3+4+...+i+( i+2) )
for(int j=3; j<=i; j++)
{
std::cout<<ans[j]<<" ";
}
std::cout<<i+2;
}
if(diff>=1 && diff<=(i-1)) //差值1<=diff<=i-1
{
int tmp = i;//为了不修改i
//最大积数列是从原始数列(2,3,4,...,i)的最大项开始
//从大到小依次每项加1,直到diff=0为止
for(int k=diff; k>0; k--)
{
ans[tmp--]++;
}
int t;
for(t=2; t<i; t++)
{
std::cout<<ans[t]<<" ";
}
std::cout<<ans[t];
}
if(diff == 0)//差值为0,则最大积数列就是原始数列2,3,4,...,i
{
int p;
for(p=2; p<i;p++)
{
std::cout<<ans[p]<<" ";
}
std::cout<<ans[p];
}
system("pause");
return 0;
}
分享到:
相关推荐
议会问题是欧洲议会议员向其他欧盟机构和机构提出的问题。它们是议会对其他欧盟机构和机构的直接审查形式...file/opensearch/documents/93180/european-parliament-lists-of-questions-and-declarations_metadata.json
安装npm install --save parliament-svg用法const parliamentSVG = require ( 'parliament-svg' )const svg = parliamentSVG ( parties , seatCount ) parties是包含每个宴会的座位数和颜色的对象{" linke " : {" ...
parliament-twitter
这是欧盟开放数据门户网站托管的欧洲议会数据集。开放数据门户根据所输入的数据量来更新其信息。 2010_02_08_EB_Quali_Femmes_EN.pdf 2010-seminar-women-and-the-eu-march-2-2010_metadata.json ...
吉布斯采样matlab代码议会网络 论文项目旨在发现意大利政客之间的潜在网络。 可以进行全部工作。 项目介绍 收集意大利议会政客中的赞助数据[Briatte,2016年]。 获取每个立法的邻接矩阵。 使用无限关系模型为议会...
The Part-Time Parliament This article appeared in ACM Transactions on Computer Sys- tems 16, 2 (May 1998), 133-169. Minor corrections were made on 29 August 2000. lamport
英国国会人口统计 使用Python代码获取有关下议院议员和上议院议员的数据。 D3.js代码可基于该数据创建图表。 使用Python 3从“获取有关MP和Lords会员的数据。 该过程的灵感来自 (仅获取Commons的数据)。...
De Kamer-La Chambre铲运机 该库为网站和比利时联邦议会的会议记录提供了一个基于Python库Beautiful Soup的刮板。... 功能性 获得给定会议的所有全体会议的概述 在指定的会议期间获取联邦议会议员的政党隶属关系,省份...
联邦议会形象化该存储库托管网站后面的代码。 它使用运行时导入在其中实现了可视化的笔记本。... 运行时为我们提供了许多使用和可视化数据的便利。 在下面,您可以找到每个页面的相关笔记本的链接: ( ) ( ) ( ) ...
PM-Tony-Blair's-speech-to-EU-Parliament.docx
1. The Part-Time Parliament 2. Paxos Made Simple 3. paxos made live-paper2-1 Paxos 三篇经典论文,高清
lamport论文翻译,详细讲解了paxos。 作者在第 4 节中确实简短讨论了 Paxos 议会和分布式计算的关系。计算机科学家可能会想要首先阅读 这一节。甚至在这之前,他们或许想要阅读 Lampson[1996]对这个算法向计算机...
议会听证会 (แอบฟังเสียงรัฐสภา) 设置 要求NodeJS v11.4.0 或更高版本。 $ npm install 发展 $ npm run develop 如何释放 凹凸版本npm version [major|minor|...] git push git push && git ...
DIRECTIVE 2014-40-EU OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL.zip
Parliament.uk-utilities 是一种应用程序,旨在保留由的新网站的实用程序部分。 内容 要求 需要以下内容: 邦德勒 入门 克隆存储库: git clone https://github.com/ukparliament/Parliament.uk-utilities.git cd...
该论文主要是Leslie Lamport在1998年发表的一篇论文The Part-Time Parliament,在这篇论文Lamport介绍了一种全新的数据一致性算法——Paxos算法,是研究计算机科学非常值得读的一篇论文,尤其是大数据中的分布式数据...
European Parliament Proceedings Parallel Corpus 1996-2011 数据集是一个用于统计 机器翻译 的语料库,其中 Europarl 平行语料库来源于欧洲议会的程序,它包括 21 种欧洲语言版本: 罗马语(法语,意大利语,...
议会是一个AWS IAM linting库。 它审查了寻找问题的策略,例如: 格式错误的json 缺少必需的元素 不正确的前缀和动作名称 提供的操作的资源或条件不正确 类型不匹配 不良的政策模式 ...parliament --file test.
Paxos算法是分布式技术大师Lamport提出的,主要目的是通过这个算法,让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说,就是在一个选举过程中,让不同的选民最终做出一致的决定。...
Lamport Paxos 的这两篇论文真的很难懂,小编也是竭尽全力的推敲每一句话的意思,尽量的将Lamport的意思完整的呈现出来。希望大家支持一下。两篇论文大概码了3万多字,每一个公式都是手敲的… ...