集训队作业原创比赛

1、2007 模拟试题Wer C2008 年 1 月 9 日比赛时间：6 小时el(R) Pentium(R) pro 512 MB Memory测试环境：sor 1.70GHz,1题目名称CountFunnyPirateBuildings可执行文件名count.exefunny.exrate.exeN/A输入文件名count.infunny.inpirate.inbuilding15.in输出文件名count.outfunny.outpirate.outbuilding15.out单个测试点时限1s1s1sN/A内存限制64Mb64Mb64MbN/A测试点个数1010105单个测试点分数1010

2、10不定附加文件无无无building15.in题目类型传统传统传统提交是否有部分分无无无有1数的拆分(COUNT)2数的拆分(Count)1问题描述：Zz 是一个聪明又好奇的孩子，她常常沉迷于有趣的数学题中。一天，她看到了这样的一道题目：将数 n 拆分成若干个数的和，要求这些数都是 2 的整数次幂，并且相同的数不能使用超过两次。比如对于数 10 ，有如下 5 种不同的拆分方案：10 = 8+ 2 = 8+ 1+1 =4+4+2 = 4+4 +1+1 = 4+2+ 2+1+ 1这样的题目当然难不倒她（当然也难不倒你咯 :) ）。当她完成后，好奇心的驱使使得她产生了一个新：在 0n 的这 n 个

3、数中，哪一个数或哪些数的拆分方案数最大，最大值是多少？这可把她给难住了，聪明的你能帮助她么？输入文件：本题有多组数据。每组数据仅一个自然数 n ，对于每个测试点，数据组数不超过 10000 。每个测试点以 0 作为结束。输出文件：对于每组数据，你只需要输出拆分方案的最大值。对于最后的 0 ，你不需要输出。样例输入：5100样例输出：35数据规模：2一个有趣(FUNNY)3对于 10% 的测试点 n 100对于 30% 的测试点 n 105对于 100% 的测试点 n 10182一个有趣(Funny)问题描述：对于正整数n ，定义函数f(x) 和g(x) 。对于 S=1,2,2n ，如果可以选出

4、若干个数，使得其中的任何两个数之间都不存在倍数关系，称选出的数的集合是合法的。定义合法的集合的元素个数最大值是 f(n) 。例：对于 n=2 ， f(n)=2 ，因为对于集合1,2,3,4 ，选出的数的集合是 2,3 或者 3,4 都满足要求，但只要选出的数多于 2 个，就不可能满足要求了。现在再说说 g(n) 。对于集合 S 的一个合法的 f(n) 元子集，总有一些数是不可能被选入任何一个 f(n) 元子集的。比如说， n=2 的时候， 1 是无论如何也不可能被选入满足条件的 2 元子集的。这样，也必然存在一个正整数 k ，使得 1 到 k 的连续正整数都不在合法子集中。定义 g(n)=k

5、。比如说，如果 n=2 ,那么从 4 元集合中不可能取出 1 ，所以 g(2)=1 。现在的任务就是求g(n) 。输入文件：输入数据包含一个正整数n 。输出文件：输出数据只有一行，即g(n)。样例输入：2样例输出：3海盗(PIRATE)41数据规模：对于 20% 的数据 n 50 对于 40% 的数据 n 1000对于 100% 的数据 n 1063海盗(Pirate)问题描述：N 个海盗要分M 个宝石。首先，由第一个人提出一种分配方案，然后由所有活着的海盗进行投票（包括提出方案者），若这个方案得到超过 p% 的海盗的认可，那么就按照这个方案分配，否则他将被扔到海里去喂鱼(哈哈，喂我或者 yu

6、hch 都行)，并接着由第二个海盗提出方案，按顺序以此类推（即若杀掉第二个人，那么接下来由第三个海盗接着提出方案）。所有的海盗都是理性的，他们希望能够得到越多的宝石。而海盗又是无比凶残的，倘若杀与不杀提出方案的海盗，他的利润是相同的话，他会毫不犹豫的投出票。对于提出方案的海盗，如果有多种方案使得他得到的宝石数目一样多，那么他会尽量让重要的，海盗希望自己能活着。大的海盗得越多的宝石。当然，最那么，倘若你是第一个海盗，你将获取多少宝石呢？输入文件：本题有多组数据。每组输入数据包含三个正整数 n,m,p 。输入以 0,0,0作为结束的标志。输出文件：输出你能获得的宝石的最大值，倘若你注定要被投入大海

7、喂鱼，请输出-1 。4建筑(BUILDINGS)5样例输入：5 100 500 0 0样例输出：97数据规模：对于 30% 的测试点 n 1000 对于 100% 的测试点n 105m 230p 1004建筑(buildings)问题描述：在生活的城市中，人民生活安康，一派和谐的景象。当然，每个人的腰包都鼓囊囊的。高楼常常作为一座城市繁华的标志，因此他希望这座城市能够搭建的高楼。这座城市可以被看作一个 n m 的矩阵，每个矩阵上可以搭建一座楼房或拆除掉原有的楼房。楼房共有 4 个等级。建造不同等级的楼房有着不同的条件：等级 1 的房子只需建筑地点在一片空地上即可。等级 2 的房子需要建筑地点在

8、一片空地上、并且四周有至少一座等级1 的房子。等级 3 的房子需要建筑地点在一片空地上、并且四周有至少一座等级1 的房子、至少一座等级 2 的房子。等级 4 的房子需要建筑地点在一片空地上、并且四周有至少一座等级1 的房子、至少一座等级 2 的房子、至少一座等级 3 的房子。4建筑(BUILDINGS)6希望所有 N M 个地点的建筑的等级之和最高（空地的等级按 0计算）。输入文件：两个整数 n, m。输出文件：输出文件第一行两个整数，表示你找到的路线的建筑等级和 sum ，以及你需要的操作总数 d 。接下来 d 行，每行为一个字符 ch 与三个数 x,y,z ，若 ch = d ，表示拆除掉坐标(x,y) 上的现有建筑，而 z 必须为0，若 ch = b ，表示在坐标 (x,y)上兴建一座z 级建筑。评分标准：方案不合法或前后方案造成 checker，得 0 分。，得 0 分。操作数超过 5000000 ，得 0 分。否则根据 sum ，设所有选手连同参考的最优解为 sum0 ，该测试点的得分为FullScore ,你的得分按下式计算：FullScore:sum = sum0FullScore*60%:sum0 90% sum sum0FullScore*30%:sum0 70% sum sum0 90% F