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

《高一信息学奥赛组寒假作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2004届高一信息学奥赛组寒假作业（＊＊）一、星际旅行（space）问题描述：有一艘从地球出发的宇宙飞船要按照固定的顺序访问一系列行星。飞船从一个行星飞到另一个行星可以通过两种空间，一种是普通的空间，一种是超空间。与在普通空间飞行相比，在超空间中飞行通常可以缩短飞行的距离，但是燃料的消耗会比较多。事实上，我们可以这样计算飞船飞行消耗的燃料，进行d光年的普通空间飞行，消耗的燃料为d个单位；进行d光年的超空间飞行，消耗的燃料为d4个单位。值得注意的是，飞船从一个行星飞往另一个行星的时候只能通过一种空间。现在你就是这艘飞船的船长，你的任务是编写一个

2、程序，找出完成这次旅行最少需要消耗多少燃料。输入格式：输入文件第一行只有一个整数N（1≤N≤500），表示这次旅行一共要访问多少颗行星。在接下来的N行中，第i行对应第i个要访问到的行星，每行有两个正整数hd、nd分别表示第i-1个行星到第i个行星的超空间距离和普通空间距离（当然，第0个行星就是飞船的出发地——地球）。距离的单位都是光年，1≤hd≤10，1≤nd≤10,000,000。输出格式：只有一个数字，即访问了所有的行星后最少需要多少单位的燃料。输入输出样例：输入样例输出样例33100025000480002296二、生成字符串问题描述:

3、假设字符串只由字符‘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行每行各有一个字符串。文件中各行的

4、行首、行末没有多余的空格。输出格式:答案输出到当前目录下的文本文件“STRINGS.OUT”中，该文件只有一个整数total，表示所能生成的字符串的个数。输入输出举例:输入文件：STRINGS.DAT输出文件：STRINGS.OUT第4页共4页2310*10*4三、骨牌矩阵问题描述：多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0～6），现在有28组骨牌，每组两个，各组编号为1～28，每组编号对应的两个骨牌数值如下。骨牌组编号骨牌骨牌组编号骨牌骨牌组编号骨牌骨牌组编号骨牌10

5、081

6、1152

7、3223

8、620

9、191

10、2162

11、42

12、34

13、430

14、2101

15、3172

16、5244

17、540

18、3111

19、4182

20、6254

21、650

22、4121

23、5193

24、3265

25、560

26、5131

27、6203

28、4275

29、670

30、6142

31、2213

32、5286

33、6现将这28组骨牌排成一个7´8矩阵，此时只能看到每个骨牌上的数字（0～6），而不能知道每组的组号。如左下图所示。请编程将每组骨牌分辨出来（见右下图。图中数字为对应左图每组骨牌的编号）。骨牌摆放可旋转，例如第9组骨牌经旋转可得以下4种放法：1

34、2、2

35、1、、。7´8骨牌矩阵骨牌组编号矩阵66265241282814717171111132010341

36、0101472221231324665484162525132123104321128416151513995136045512122222552626554026032724243318119605342032766202018119输入格式：从键盘输入一个文本文件的文件名。该文件包含了一个7行´8列的骨牌矩阵，每行有8个0-6的整数，每个整数之间用空格分开。每行的行首、行末无多余空格。输出格式：答案输出到一个文本文件中，文件名由键盘输入。1.若问题无解,则输出“-1”；2.若问题有解,则将所有可能的解输出，每个解之间用一个空行分开，最后输

37、出解的总数。数字间用空格分开。第4页共4页输入输出举例：输入：SAMPLE2.DAT输出：SAMPLE2.OUT5436534606012311326504205362320640410041522441655536123162020272719252561822319882118281731616721428171515572441111115122414142323131312262622229910101四、求三角形最大面积(Triangle)问题描述：圣诞节快到了。你接受了一件光荣的任务，就是制作圣诞树顶上的那颗大星星。不过当你拿到制

38、作用的三角形银纸的时候，你发现银纸上面有许多洞。原来你的妹妹已经在银纸上剪下了一些小的三角形来制作小星星。你唯有寻找一个算法，能告诉你在每张银纸上还能切出来的最大的