大学生计算机程序设计竞赛.DOC

1、大学生计算机程序设计竞赛2010 年 10 月 31 日本次比赛 11 道题目，共 13 页。如有缺 页，请立即通知 赛场工作人员。所有题目均采用标准输入输出，请不要读写任何文件。所有题目的正确输出均是惟一的。你的输出只有和正确输出完全一致时才能通过。题目 A汽水瓶有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是 5 瓶，方法如下：先用 9 个空瓶子换 3 瓶汽水，喝掉 3 瓶满的，喝完以后 4 个空瓶子，用 3 个再换一瓶，喝掉这瓶满的，这时候剩 2 个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用 3 个

2、空瓶子换一瓶满的还给老板。如果小张手上有 n 个空汽水瓶，最多可以换多少瓶汽水喝？输入输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（1 0）。根据定义，IRR 可以是负数，但不能大于-1。输入输入文件最多包含 25 组测试数据，每个数据占两行，第一行包含一个正整数 T（1=T=10），表示项目的期数。第二行包含 T+1 个整数： CF0, CF1, CF2, ., CFT，其中 CF0 0, 0 CFi 10000 (i=1,2,.,T)。T =0 表示输入结束，你的程序不应当处理这一行。输出对于每组数据，输出仅一行，即项目的 IRR，四舍五入保留小数点后两位。如果

3、 IRR 不存在，输出“No“，如果有多个不同 IRR 满足条件，输出“Too many“（均不含引号）样例输入 样例输出1-1 22-8 6 901.000.50Problem FBiggest NumberYou have a maze with obstacles and non-zero digits in it:You can start from any square, walk in the maze, and finally stop at some square. Each step, you may only walk into one of the four neighb

4、ouring squares (up, down, left, right) and you cannot walk into obstacles or walk into a square more than once. When you finish, you can get a number by writing down the digits you encounter in the same order as you meet them. For example, you can get numbers 9784, 4832145 etc. The biggest number yo

5、u can get is 791452384, shown in the picture above.Your task is to find the biggest number you can get.InputThere will be at most 25 test cases. Each test begins with two integers R and C (2=R,C=15, R*C=30), the number of rows and columns of the maze. The next R rows represent the maze. Each line co

6、ntains exactly C characters (without leading or trailing spaces), each of them will be either # or one of the nine non-zero digits. There will be at least one non-obstacle squares (i.e. squares with a non-zero digit in it) in the maze. The input is terminated by a test case with R=C=0, you should no

7、t process it.OutputFor each test case, print the biggest number you can find, on a single line.Sample Input Output for the Sample Input3 7#9784#123#45#0 0791452384Problem GRepairing a RoadYou live in a small town with R bidirectional roads connecting C crossings and you want to go from crossing 1 to

8、 crossing C as soon as possible. You can visit other crossings before arriving at crossing C, but its not mandatory. You have exactly one chance to ask your friend to repair exactly one existing road, from the time you leave crossing 1. If he repairs the i-th road for t units of time, the crossing t

9、ime after that would be viai-t. Its not difficult to see that it takes vi units of time to cross that road if your friend doesnt repair it.You cannot start to cross the road when your friend is repairing it.InputThere will be at most 25 test cases. Each test case begins with two integers C and R (2=

10、C=100, 1=R=500). Each of the next R lines contains two integers xi, yi (1=xi, yi=C) and two positive floating-point numbers vi and ai (1=vi=20,1=ai=5), indicating that there is a bidirectional road connecting crossing xi and yi, with parameters vi and ai (see above). Each pair of crossings can be co

11、nnected by at most one road. The input is terminated by a test case with C=R=0, you should not process it.OutputFor each test case, print the smallest time it takes to reach crossing C from crossing 1, rounded to 3 digits after decimal point. Its always possible to reach crossing C from crossing 1.S

12、ample Input Output for the Sample Input3 21 2 1.5 1.82 3 2.0 1.52 11 2 2.0 1.80 02.5891.976题目 H射击游戏A 和 B 在玩一个射击游戏，战场由若干单位正方形积木组成。积木占据了连续的若干列，且图形周长等于它最小包围矩形的周长。下图(a)是一个合法的战场，但(b)和(c)都不是：(b)中有空列；(c)的图形周长为 14，而最小包围矩形（用虚线画出）的周长为 12。受重力影响，每个积木的正下方要么是地面，要么是另一个积木。为了让战场看上去错落有致、玩着更刺激，它不能恰好是一个矩形（即：不能每列积木都一样高）

13、。游戏规则如下：1、 A 和 B 轮流射击，A 先射击。2、 每次射击时，首先选择一行（该行必须至少有一个积木），以及“左” 和“右” 中的一个方向，然后往这个方向开火。子弹的威力为 13 的均匀随机整数（即：威力为 1、2、3 的概率各为 1/3），表示子弹能打掉的积木个数，被打掉的积木将直接从战场中消失。如果该行的积木个数小于威力值，则子弹将在打掉该行所有积木后消失。例如，若选择往右射击从下往上数第 3 行，且威力为 2，且这一行一共有 4 个积木，则最左边的两个积木将被打掉。注意：这两个积木可以不连续。 3、 每次射击完成后，悬空的积木垂直往下落。所有积木不再下落后，下一位选手才能开始射

14、击。4、 谁打掉了最后一个积木，谁就获胜。假定开局是 ，根据规则 1， A 先开火。射击后，B 可能面临的后续局面中的其中三个如下表：行编号（从下往上数） 子弹前进方向 威力（随机值） 刚射击后 积木稳定后2 从右往左 1 （同左图）1 从右往左 21 从左往右 3假定 A 和 B 都足够聪明，采取让自己获胜概率尽量高的策略，你的任务是计算出 A 获胜的概率。输入输入文件最多包含 25 组测试数据，每个数据仅包含两行，第一行是整数 n（1=n=6 ），即积木的列数。第二行包含 n 个正整数 h1, h2,., hn(1=hi=6)，表示从左往右数第 i 列的高度。积木的排列方式保证符合题目描述

15、（即：图形周长等于它最小包围矩形的周长，且各列的高度不全相同）。n=0 表示输入结束，你的程序不应当处理这一行。输出对于每组数据，输出仅一行，即 A 获胜的概率，四舍五入保留六位小数。样例输入 样例输出32 1 100.555556题目 I战场的数目在上题中，假设战场的图形周长为 p，一共有多少种可能的战场？例如，p8 时没有符合要求的战场，p=8 时有 2 种战场：p=10 有 9 种战场：要求输出方案总数模 987654321 的值。输入输入文件最多包含 25 组测试数据，每个数据仅包含一行，有一个整数 p（1=p=10 9），表示战场的图形周长。p=0 表示输入结束，你的程序不应当处理这一行。输出对于每组数据，输出仅一行，即满足条件的战场总数除以 987654321 的余数。样例输入 样例输出7891000209