高精度练习题.doc

高精度练习题（1）Hanoi双塔问题（2007年全国信息联赛普及组试题）【问题描述】 给定A，B，C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求：（1）每次只能移动一个圆盘； （2） A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。（2）密 码（2008宁波市比赛中小学程序设计比赛）【问题描述】在浩浩茫茫的苍穹深处，住着上帝和他的神仆们，他们闲谈着下界的凡人俗事，对人世间表现的聪明智慧，大加赞赏。今天他们正在观赏大地风光人情之际，忽然从遥远的东海之滨传来一阵欢笑声，上帝纵目望去，只见学校内聚集了全市的中小学精英学生，他们要干什么呢？原来他们都在做一种破译密码的游戏，人们发现：红色密码棒上的数字减去蓝色密码棒上的数字，就是开启天庭司粮库密码锁的密码。如：135477 - 67122=68355，则68355就是一组有效的密码。“太简单了！”人们高呼起来，继续探索着。“这不过是早期的密码系统而已。”上帝轻蔑地环顾神仆们说道。可是，当人们演算了 146201-3344=142857 后，上帝的神色愈来愈不对了，要知道，142857是一个特别的数字，这可是天庭的机密，是谁将这些机密泄露给世人的呢？于是，上帝搬出一张牌，对司粮库主管得墨忒耳说：“将这张牌打出去，看看他们还逞能不？”这是天庭的其中一张王牌，但平凡得很，只不过将密码的位数增大到不超过20000位而已。可是难就难在你看到文件：password.in中的两个数后，必须在1秒钟内将密码输出到文件：password.out中，否则这组密码就失效了。上帝还是仁慈的，没有将更难的牌打出来，他想把天庭的粮食恩赐人间，但他绝不会将好处给那些不动脑子的人。现在请你解开天庭司粮库密码锁的密码，帮助人们获得天庭恩赐的粮食。【输 入】输入文件password.in有二行，每行有一个正整数。【输 出】【样例输入2】 67122135477 【样例输出2】68355输出文件password.out只有一行，该行只有一个正整数，为输入的两个正整数中较大者减去较小者的差值。【样例输入1】样例输出1】68355【数据限制】30%的数据，二个数均小于2109。50%的数据，二个数均小于11016。100%的数据，二个数均小于11020000。70%的数据，第一个数大于第二个数。（3）贸 易小张是一位中俄边境商人，主要从事把中国的商品带到俄罗斯，然后在俄罗斯卖掉，在资金允许的条件下采购俄罗斯商品带回到国内。在采购过程中，俄罗斯商品定价有一个奇怪的现象，首先设定一个基准价 x，第一种商品的单价即为x，第二种商品的价格则为 x2，第三种商品的价格为x3，第i种商品的价格为xi依次类推。最后在完成交易后需要支付一笔手续费a0，小张为了尽可能多的带回商品，现在要求你帮助他这笔教义需要支付多少钱？【输 入】x na0a1a2.an第一行两个数分别表示基准价x (x=10)，物品种数n （n=100000）。第二行一个数，手续费a0（a0=100）。接下来的n行每行一个数，第i行表示第i种物品购买的数量（ai=100）。【输 出】直接输出结果。【样例输入】 【样例输出】2 3 1066459【数据限制】对20%的数据，n=10。对50%的数据，n=200。对100%的数据，n=100000。(4)合并排列数(num.in/ num.out)题目描述Oliver自上了初中以后，就很喜欢钻研各种理科知识，他在假期学习了高中数学中的排列组合，主要是为了在OI比赛中起到一些作用，另外也算是又学习了一些大有裨益的知识吧。之后，他一直想用所学的知识表达出一些奇异的想法（再次注：Oliver是一个“标新立异”的大牛），经过几个星期的思考，他终于想出了一个关于排列的特殊数，即合并排列数。关于这个数，Oliver是这样定义的：我们已知A(m,n)=(n-m+1)*(n-m+1)+1*(n-m+1)+1+1*n也就是从n个元素中选取m个元素排列生成不同序列的个数(mn,且均为正整数），例如A(2,5)=4*5=20。但仅仅是这样一个公式太单调了，于是我们可以把生成的序列先按照顺序列出来，即A(2,5)所生成的序列为1,21,31,41,52,15,4，然后再按照一个排列的元素顺序进行合并，则合并之后得到的新数即为121314152154，现在我们将其中的合数全部去掉，则还有如下合并排列数132331414353，然后再算出所有剩下数的乘积，得到的数就叫做合并排列数。现在请你根据Oliver设计的这个方法，算出A(m,n)的合并排列数。输入格式只有一行，即A(m,n)中的m和n。输出格式只有一行，即得到的合并排列数。样例输入2 5样例输出866086091数据规模对于80%的数据，0mn4；对于100%的数据，0mn5。(5)阿猫的实验(cat.pas/c/cpp)【问题描述】阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。一天，阿猫在实验室听说了这样一种繁殖能力很强的老鼠。这种老鼠在出生后的第一个月，可以生出a 对老鼠；第二个月，可以生出b 对老鼠；第三个月及以后的每个月，都可以生出c 对老鼠。阿猫对此十分好奇。他很想知道，如果他有一对刚出生的老鼠，按最理想的模式繁殖，且老鼠不死，那么最少需要多少个月它们就可以覆盖整个地球。为了完成这一猜想，阿猫需要知道这种老鼠在第N 个月时的数量。【输入文件】输入文件cat.in 只有一行，四个数，分别为a，b，c，N（0=a=b=c=100，N=3000)，其含义为题目所述。【输出文件】输出文件cat.out 只有一个数，为第N 个月老鼠的数量。【输入样例】0 1 1 11【输出样例】144(6)Oliver的成绩(score.pas/c/cpp)1.【问题描述】 Oliver进入初中后，觉得自己不能总是玩儿了，应该要好好学习了。正好一次考试结束了，Oliver想知道自己的语文，数学，英语分别与语文年级第一，数学年级第一，英语年级第一相差多少。由于Oliver所在年级有N个人，所以Oliver想你编个程序帮帮他。【输入格式】score.in共3N+4行，第一三行分别为Oliver的语文数学英语成绩(位数M)，第四行为N，以下3N行，每行一个数(它们的位数是M),分别为第N个同学的语文，数学，英语成绩。即:Oliver的语文 数学 英语 N 第一个人的语文 数学 英语 第二个人的语文 【输出格式】 score.out共