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