信息学奥赛2003吉林省选试卷.docVIP

PAGE  PAGE 6 2003吉林省选试题 试题说明 试题名称分值可执行文件输入文件输出文件限时字符串变换90String.exeString.inString.out≤15s穿 墙 人60wall.exeWall.inWall.out≤3s 选陪审团90Jury.exeJury.inJury.out≤3s方格中置160Grid.exeGrid.inGrid.out≤3s第一试共四道题，满分为300分。 竞赛时间：2003年7月6 日8:30—12:00 题一 字符串变换 【问题描述】 为了简化问题，我们只考虑仅由字符a和b组成的字符串。且只有两个变换规则： 规则1：a → Pa , 表示字符a可以变换为字符串Pa； 规则2：b → Pb , 表示字符b可以变换为字符串Pb； 对字符串中的某个字符应用一次规则将其替换成Pa或Pb的过程，称为一次变换。现在的问题是，给定一个初始串S和目标串T，给定两个变换规则中的Pa和Pb，问是否存在一个从初始串到目标串的变换序列，并且该序列的变换次数不超过m。 例如： m = 4 Pa = ‘aa’ Pb = ‘bb’ S = ‘ab’ T = ‘aaabb’ 则存在一个变换次数不超过4次的变换序列，如下所示： ‘ab’ → ‘aab’ → ‘aaab’ → ‘aaabb’ 注意：上述序列只经过了3次变换。每次变换可以根据规则替换掉当前串中的任意一个字符，但一次变换只能替换一个字符。 【输入格式】String.in 输入文件的第一行为一个整数m，其中1? m ? 30，表示最多允许的变换次数。接下来有4行，分别是Pa, Pb, S, T，其中S不等于T。每个字符串仅由字符a和b组成，不包含空格，且所有字符串的长度都不超过30。 【输出格式】String.out 如果不存在从S到T且变换次数小于等于m的变换序列，则输出一个字符串”NO”（注意要大写，不包含引号）；否则输出最短的变换序列的变换次数。 【输入样例1】 4 aa bb ab aaabb 【输出样例1】 3 【输入样例2】 4 a b ab aaabb 【输出样例2】 NO 题二 穿墙人 【问题描述】 穿墙术是现代魔术表演中常见的一个节目。魔术中的穿墙人可以穿过预先设计好的若干道墙。所有的墙被安置在一个网格区域中，如图所示，‘？’表示墙所占据的网格，所有的墙都水平放置，宽度为1个单位，但长度可能不同。任何两道墙不会相互重叠，即任何一个‘？’不能同时属于两道或两道以上的墙。穿墙人的能量有限，每次表演至多只能穿过k道墙。 表演开始时，主持人让观众任选网格的某一列，然后穿墙人开始沿着此列从网格的上端穿过中间的每一道墙到达网格的底部。但如果观众所选择的那一列中有大于k道墙，则穿墙人的表演会失败。 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 例图所示，如果k=3，则穿墙人可以自上而下地穿过除第6列外的任何列，因为只有第6列需要穿越4道墙，但穿墙人在同一列上最多只能穿过3道墙。 当所有的墙给出之后，如果知道穿墙人当前的能量K，我们希望移去最少数目的墙，才能使得穿墙人能够穿越任何一列。 对于图中的例子，如果k=3，穿墙人无法穿越第6列，但是只要把第3行的墙移去（不唯一），则穿墙人就可以穿过任意一列。因此对于这个例子最少需要移去1道墙。 【输入格式】wall.in 输入文件的第一行是用空格隔开的两个整数n和k，其中1 ? n ? 100，0 ? k ? 100；n表示墙的数目，k表示穿墙人在同一列上最多能穿过多少道墙。接下来有n行，每行是用空格隔开的四个整数x1, y1, x2, y2，其中(x1, y1)和(x2, y2)分别表示一道墙的两个端点（注意，根据题意，一定有y1=y2）。x, y坐标的范围为[0, 100]，左上角的坐标定为(0, 0)。 【输出格式】wall.out 输出文件只包含一个整数，即为了让穿墙人能够穿越任意一列所需要移去的最少的墙的数目。 【输入样例】 7 3 0 0 3 0 6 1 8 1 2 3 6 3 4 4 6 4 0 5 1 5 5 6 7 6 1 7 3 7 【输出样例】 1 题三 选陪审团 【问题描述】 在古埃及时代也有法庭。法庭的裁决取决于陪审团的决定，陪审团的人员来自当地的居民。每次开庭前，法庭会聘请n人作为侯选陪审员，其编号分别为1，2，…，n；然后由法官从n位侯选陪审员中选出m人作为正式陪审员。具体的选择过程如下：由原告和被告分别给每一位