高一信息学奥赛组寒假作业

2004届高一信息学奥赛组寒假作业（＊＊）

一、星际旅行（space）

问题描述：有一艘从地球出发的宇宙飞船要按照固定的顺序访问一系列行星。飞船从一个行星飞到另一个行星可以通过两种空间，一种是普通的空间，一种是超空间。与在普通空间飞行相比，在超空间中飞行通常可以缩短飞行的距离，但是燃料的消耗会比较多。事实上，我们可以这样计算飞船飞行消耗的燃料，进行d光年的普通空间飞行，消耗的燃料为d个单位；进行d光年的超空间飞行，消耗的燃料为d4个单位。值得注意的是，飞船从一个行星飞往另一个行星的时候只能通过一种空间。

现在你就是这艘飞船的船长，你的任务是编写一个程序，找出完成这次旅行最少需要消耗多少燃料。 输入格式：

输入文件第一行只有一个整数N（1≤N≤500），表示这次旅行一共要访问多少颗行星。在接下来的N行中，第i行对应第i个要访问到的行星，每行有两个正整数hd、nd分别表示第i-1个行星到第i个行星的超空间距离和普通空间距离（当然，第0个行星就是飞船的出发地——地球）。距离的单位都是光年，1≤hd≤10，1≤nd≤10,000,000。 输出格式：

只有一个数字，即访问了所有的行星后最少需要多少单位的燃料。 输入输出样例： 输入样例 输出样例 3 2296 3 1000 2 5000 4 8000

二、生成字符串

问题描述:假设字符串只由字符‘0’，‘1’，‘*’组成，其中字符‘*’表示该字符可由字符‘0’或‘1’替代。

现有一些字符串，根据这些字符串生成所有可生成的字符串。如： {10，*1，0* }可生成{10，01，11，00 } {101，001，*01}可生成{ 101，001}

注意后一个例子中‘*01’并没有生成新的字符串。 输入格式:

从当前目录下的文本文件“STRINGS.DAT”读入数据。该文件的第一行是两个整数m,n。（1≤m≤15,1≤n≤2500）m表示字符串的长度，n表示字符串的个数。两个整数之间由一个空格隔开。以下n行每行各有一个字符串。文件中各行的行首、行末没有多余的空格。 输出格式:

答案输出到当前目录下的文本文件“STRINGS.OUT”中，该文件只有一个整数total，表示所能生成的字符串的个数。 输入输出举例:

输入文件：STRINGS.DAT 输出文件：STRINGS.OUT

第 1 页 共 4 页

2 3 10 *1 0* 4

三、骨牌矩阵

问题描述：多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0～6），现在有28组骨牌，每组两个，各组编号为1～28，每组编号对应的两个骨牌数值如下。 骨牌组编号 骨牌 骨牌组编号 骨牌 骨牌组编号 骨牌 骨牌组编号 骨牌 1 0|0 8 1|1 15 2|3 22 3|6 2 0|1 9 1|2 16 2|4 23 4|4 3 0|2 10 1|3 17 2|5 24 4|5 4 0|3 11 1|4 18 2|6 25 4|6 5 0|4 12 1|5 19 3|3 26 5|5 6 0|5 13 1|6 20 3|4 27 5|6 7 0|6 14 2|2 21 3|5 28 6|6 现将这28组骨牌排成一个7?8矩阵，此时只能看到每个骨牌上的数字（0～6），而不能知道每组的组号。如左下图所示。请编程将每组骨牌分辨出来（见右下图。图中数字为对应左图每组骨牌的编号）。骨牌摆放可旋转，例如第9组骨牌经旋转可得以下4种放法：1|2、

212|1、、。

12 7?8骨牌矩阵 骨牌组编号矩阵

6 6 2 6 5 2 4 1 28 28 14 7 17 17 11 11 1 3 2 0 1 0 3 4 10 10 14 7 2 2 21 23 1 3 2 4 6 6 5 4 8 4 16 25 25 13 21 23 1 0 4 3 2 1 1 2 8 4 16 15 15 13 9 9 5 1 3 6 0 4 5 5 12 12 22 22 5 5 26 26 5 5 4 0 2 6 0 3 27 24 24 3 3 18 1 19 6 0 5 3 4 2 0 3 27 6 6 20 20 18 1 19 输入格式：

从键盘输入一个文本文件的文件名。该文件包含了一个7行?8列的骨牌矩阵，每行有8个0-6的整数，每个整数之间用空格分开。每行的行首、行末无多余空格。 输出格式：

答案输出到一个文本文件中，文件名由键盘输入。 1.若问题无解,则输出“-1”；

2.若问题有解,则将所有可能的解输出，每个解之间用一个空行分开，最后输出解的总数。 数字间用空格分开。

第 2 页 共 4 页

输入输出举例： 输入：SAMPLE2.DAT

输出：SAMPLE2.OUT 6 20 20 27 27 19 25 25 6 18 2 2 3 19 8 8 21 18 28 17 3 16 16 7 21 4 28 17 15 15 5 7 24 4 11 11 1 1 5 12 24 14 14 23 23 13 13 12 26 26 22 22 9 9 10 10 1

5 4 3 6 5 3 4 6 0 6 0 1 2 3 1 1 3 2 6 5 0 4 2 0 5 3 6 2 3 2 0 6 4 0 4 1 0 0 4 1 5 2 2 4 4 1 6 5 5 5 3 6 1 2 3 1 四、求三角形最大面积(Triangle)

问题描述：圣诞节快到了。你接受了一件光荣的任务，就是制作圣诞树顶上的那颗大星星。不过当你拿到制作用的三角形银纸的时候，你发现银纸上面有许多洞。原来你的妹妹已经在银纸上剪下了一些小的三角形来制作小星星。你唯有寻找一个算法，能告诉你在每张银纸上还能切 出来的最大的三角形面积。

给定一个三角形，里面有黑色和白色的区域，你必须找到白色的区域中最大三角形的面积，如右图所示： 输入格式：

输入文件包含若干个三角形描述。每个三角形描述的第一行是一个整数n(1<=n<=100)，表示该三角形的高。接下来的n行每行包含由空格、“#”和“-”组成的字符串表示三角形的状况。其中“#”代表黑色的区域，“-”代表白色的区域。空格是用来填充输入的左边，从而使得整个输入构成一个三角形的形状。

对每个三角形，每行字符“#”和“-”的数目之和都是奇数，由2n-1递减至1。

全部输入以n=0结束。 输出格式：

对输入的每个三角形，输出白色的区域中最大三角形的面积，注意最大三角形可以是顶角朝上的，如同第2个样例输入所示。 样例输入： 5

#-##----# -----#- ---#- -#-

- 4

#-#-#-- #---# ##-

第 3 页 共 4 页

- 0

样例输出： 9 4

五、客户调查

公司派你去和几位客户面谈，以了解他们对公司产品的意见。你逐个打电话与客户联系，得知他们一般都很忙，不过他们还是可以为你抽出一点时间。现在的问题是有些客户的时间有冲突，你无法在一天内联系所有客户。所以你需要一个程序来帮助你安排第一天的工作，使得你能尽可能地和更多的客户进行联系。注意，客户不愿意你打乱他们的计划。如果你和某个客户约定见面，必须按时到达并且充分利用这段时间和他交谈，这样才不至于让他产生不满。你可以假设从一个客户处到另一个客户处的时间短得忽略不计。

输入包括了多个测试数据，每个测试数据开头是一个整数n（1<=n<=1000），表示客户总数。接下来n行每行包括两个正整数s、t，分别表示该客户的空闲时间段的起始时间和终止时间。其中s

对于每个测试数据，在单独一行内输出你所能接触到的最多客户数。 输入样例： 3 1 15 2 19 15 17

输出样例： 2

六、青蛙的约会

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝着对方那里跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入包括多个测试数据。每个测试数据包括一行5个整数x，y，m，n，L，其中x≠y，m、n≠0，L>0。m，n的符号表示了相应的青蛙的前进方向。对于每个测试数据，在单独一行里输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“Impossible”。 输入样例： 1 2 3 4 5 输出样例： 4

第 4 页 共 4 页