《高一信息学奥赛组寒假作业.doc》由会员分享，可在线阅读，更多相关《高一信息学奥赛组寒假作业.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2004届高一信息学奥赛组寒假作业（）一、星际旅行（space）问题描述：有一艘从地球出发的宇宙飞船要按照固定的顺序访问一系列行星。飞船从一个行星飞到另一个行星可以通过两种空间，一种是普通的空间，一种是超空间。与在普通空间飞行相比，在超空间中飞行通常可以缩短飞行的距离，但是燃料的消耗会比较多。事实上，我们可以这样计算飞船飞行消耗的燃料，进行d光年的普通空间飞行，消耗的燃料为d个单位；进行d光年的超空间飞行，消耗的燃料为d4个单位。值得注意的是，飞船从一个行星飞往另一个行星的时候只能通过一种空间。现在你就是这艘飞船的船长，你的任务是编写一个程序，找出完成这次旅行最少需要消耗多少燃料。输入格式：输
2、入文件第一行只有一个整数N（1N500），表示这次旅行一共要访问多少颗行星。在接下来的N行中，第i行对应第i个要访问到的行星，每行有两个正整数hd、nd分别表示第i-1个行星到第i个行星的超空间距离和普通空间距离（当然，第0个行星就是飞船的出发地地球）。距离的单位都是光年，1hd10，1nd10,000,000。输出格式：只有一个数字，即访问了所有的行星后最少需要多少单位的燃料。输入输出样例：输入样例输出样例33 10002 50004 80002296二、生成字符串问题描述:假设字符串只由字符0，1，*组成，其中字符*表示该字符可由字符0或1替代。现有一些字符串，根据这些字符串生成所有可生成
3、的字符串。如：10，*1，0*可生成10，01，11，00 101，001，*01可生成101，001注意后一个例子中*01并没有生成新的字符串。输入格式:从当前目录下的文本文件“STRINGS.DAT”读入数据。该文件的第一行是两个整数m,n。（1m15,1n2500）m表示字符串的长度，n表示字符串的个数。两个整数之间由一个空格隔开。以下n行每行各有一个字符串。文件中各行的行首、行末没有多余的空格。输出格式:答案输出到当前目录下的文本文件“STRINGS.OUT”中，该文件只有一个整数total，表示所能生成的字符串的个数。输入输出举例:输入文件：STRINGS.DAT输出文件：STRIN
4、GS.OUT2 310*10*4三、骨牌矩阵问题描述：多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（06），现在有28组骨牌，每组两个，各组编号为128，每组编号对应的两个骨牌数值如下。骨牌组编号骨牌骨牌组编号骨牌骨牌组编号骨牌骨牌组编号骨牌10|081|1152|3223|620|191|2162|4234|430|2101|3172|5244|540|3111|4182|6254|650|4121|5193|3265|560|5131|6203|4275|670|6142|2213|5286|6现将这28组骨牌排成一个78矩阵，此时只能看到每个骨牌上的数字（06），而不能知道每组的
5、组号。如左下图所示。请编程将每组骨牌分辨出来（见右下图。图中数字为对应左图每组骨牌的编号）。骨牌摆放可旋转，例如第9组骨牌经旋转可得以下4种放法：1|2、2|1、。 78骨牌矩阵 骨牌组编号矩阵6 6 2 6 5 2 4 128 28 14 7 17 17 11 111 3 2 0 1 0 3 410 10 14 7 2 2 21 231 3 2 4 6 6 5 4 8 4 16 25 25 13 21 231 0 4 3 2 1 1 2 8 4 16 15 15 13 9 95 1 3 6 0 4 5 512 12 22 22 5 5 26 265 5 4 0 2 6 0 327 24 24
6、 3 3 18 1 196 0 5 3 4 2 0 327 6 6 20 20 18 1 19输入格式：从键盘输入一个文本文件的文件名。该文件包含了一个7行8列的骨牌矩阵，每行有8个0-6的整数，每个整数之间用空格分开。每行的行首、行末无多余空格。输出格式：答案输出到一个文本文件中，文件名由键盘输入。1.若问题无解,则输出“-1”；2.若问题有解,则将所有可能的解输出，每个解之间用一个空行分开，最后输出解的总数。数字间用空格分开。输入输出举例：输入：SAMPLE2.DAT输出：SAMPLE2.OUT5 4 3 6 5 3 4 60 6 0 1 2 3 1 13 2 6 5 0 4 2 05 3
7、 6 2 3 2 0 64 0 4 1 0 0 4 15 2 2 4 4 1 6 55 5 3 6 1 2 3 16 20 20 27 27 19 25 256 18 2 2 3 19 8 821 18 28 17 3 16 16 721 4 28 17 15 15 5 724 4 11 11 1 1 5 1224 14 14 23 23 13 13 1226 26 22 22 9 9 10 101四、求三角形最大面积(Triangle)问题描述：圣诞节快到了。你接受了一件光荣的任务，就是制作圣诞树顶上的那颗大星星。不过当你拿到制作用的三角形银纸的时候，你发现银纸上面有许多洞。原来你的妹妹已经
8、在银纸上剪下了一些小的三角形来制作小星星。你唯有寻找一个算法，能告诉你在每张银纸上还能切 出来的最大的三角形面积。给定一个三角形，里面有黑色和白色的区域，你必须找到白色的区域中最大三角形的面积，如右图所示：输入格式：输入文件包含若干个三角形描述。每个三角形描述的第一行是一个整数n(1=n=100)，表示该三角形的高。接下来的n行每行包含由空格、“#”和“-”组成的字符串表示三角形的状况。其中“#”代表黑色的区域，“-”代表白色的区域。空格是用来填充输入的左边，从而使得整个输入构成一个三角形的形状。对每个三角形，每行字符“#”和“-”的数目之和都是奇数，由2n-1递减至1。全部输入以n=0结束。
9、输出格式：对输入的每个三角形，输出白色的区域中最大三角形的面积，注意最大三角形可以是顶角朝上的，如同第2个样例输入所示。样例输入：5#-#-# -#- -#- -#-4#-#-#- #-# #- -0样例输出：94五、客户调查公司派你去和几位客户面谈，以了解他们对公司产品的意见。你逐个打电话与客户联系，得知他们一般都很忙，不过他们还是可以为你抽出一点时间。现在的问题是有些客户的时间有冲突，你无法在一天内联系所有客户。所以你需要一个程序来帮助你安排第一天的工作，使得你能尽可能地和更多的客户进行联系。注意，客户不愿意你打乱他们的计划。如果你和某个客户约定见面，必须按时到达并且充分利用这段时间和他交谈，这样才不至于让他产生不满。你可以假设从一个客户处到另一个客户处的时间短得忽略不计。输入包括了多个测试数据，每个测试数据开头是一个整数n（1=n=1000），表示客户总数。接下来n行每行包括两个正整数s、t，分别表示该客户的空闲时间段的起始时间和终止时间。其中s0。m，n的符号表示了相应的青蛙的前进方向。对于每个测试数据，在单独一行里输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“Impossible”。输入样例：1 2 3 4 5输出样例：4第 4 页 共 4 页
