曙光信息学奥林匹克第1次友谊赛试题.doc

福建师大附中 信息学奥林匹克小组 注意事项：1. 前三题为初中同学必作题目。2. 高中同学要完成所有题目。3. 输出文件中，输出最后一行后必须换行。=试题目录 一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数输入：输入文件只一行，两个正整数N，M( 1N50，2M5)输出：输出文件只有一个正整数S，表示方案总数。Sample Input4 3Sample Output13Problem B N的倍数(Multiple.pas)写一个程序，对于给定的一个自然数N（1N4999），和M个互不相同的十进制数字X1， X2，,XM (至少一个)， 找出N的一个最小正的倍数，使得该倍数中没有X1，X2，XM 之外的其它数字。输入格式：输入文件第一行为整数N，第二行为整数 M，接下来M行 分别列出 数字 X1,X2.XM 。输出格式：输出文件输出为这个倍数，如果无解输出0。约束条件：在所有的测试数据中答案都不会超过500位。Sample Input1223701Sample Output1110Sample Input2211Sample Output20Problem C麻将游戏(Mahjong.pas)在一种麻将游戏中，游戏是在一个有WH格子的矩形平板上进行的。每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性：1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。 2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。这是一个例子： 在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。输入格式：输入文件的第一行有两个整数w，h （1=w，h=75），表示平板的宽和高。接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个X，否则是一个空格。平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。接下来的若干行，每行有四个数x1， y1， x2， y2 ，且满足1=x1,x2=w，1=y1,y2=h，表示两张牌的坐标（这两张牌的坐标总是不同的）。如果出现连续四个0，则表示输入结束。输出格式：输出文件中，对于每一对牌输出占一行，为连接这一对牌的路径最少包含的线段数。如果不存在路径则输出0。Problem D 战略游戏(Strategi.pas)Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。输入格式：输入文件中数据表示一棵树，描述如下：第一行 N，表示树中结点的数目。第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，.，rk。对于一个n(0 n = 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。输出格式：输出文件仅包含一个数，为所求的最少的士兵数目。例如，对于如右图所示的树：答案为1（只要一个士兵在结点1上）。Sample Input140 1 11 2 2 32 03 0Sample Output11Sample Input253 3 1 4 21 1 02 00 04 0Sample Output22Problem E邀请卡分发(Deliver.pas)AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？ 输入格式：输入文件的第一行包含两个整数P和Q （1=P,Q=50000）。P为车站总数（包含AMS公司），Q为公共汽车线路数目。接下来有Q行，每行表示一条线路，包含三个数：起点，终点和车费。所有线路上的车费是正整数，且总和不超过1000000000。并假设任何两个车站之间都可到达。输出格式：输出文件仅有一行为公司花在分发邀请卡员工交通上的最少费用。S