第十二届信息学奥林匹克竞赛试题

1、N0I95试题第一天第一题査阅爪词 试題一个文木文件仅含有英文字母和分隔符，分隔符包括空格、逗号、句号和换行符。除此之外.该文件不含其它符号。一个敢词的由一个或女个分隔符分隔的连续字僚序列例如:下面是一个包含5个单？词的文件| _Stude ntmusthave II a book其中符号为空格符：“ I为换行符：“ ”为句号。文木文件中的第一个句子是从文件头到第一个句号间的字符序列（含句号），除第一个句子之外的所有句子都是由两个句号间的所有字符组成的序列（含后面的句号）。编一程序由键盘输入一个符合上述约定的文木文件名和一个爪词，计算该单词在该文件中出现的次数并输出包含该讯词的所有句子（按句子

2、在文件中的先后次序，依次输出）。文件中每个单词长度不超过 2 0个字母。判断单？词是否相同时不区分大小写。例如ABC、Abe、ABc、aBC、a b c都是同一个讯词。输入数据：由键盘输入待查文木文件名和待查单词。输出数据：输入文件为output, txt该文件第一行为该讥词在文件中出现的次数C从每二行幵始是依先后次序输出的包含该於词的句子。在输出句子时请注总：每个句子无论多长只占一行：原句中每一个换行符用一个空格符代替。输入输出范例：输入文件内容：I _Every computer will have MsDos, Borland C Microsoft I I Quick Basic ?

3、And Turbo Pasca1? For the translati ons I I the teamleaders will be provided with Microsoft Office | I with MS Word and WordPerfect Information on directories | I and last instructions will be sent to you in the last | newsletter and distributed on the day before the first | con test day. _Each stud

4、e nt will have the opport unity iI for some practice? On the equipment?i输出文件内容12I _Every computer will have MsDos, Borla nd C MicrosoftI Quick Basic | _Each student will have the oppertunity for some practice? |第一天第二题石子合并试題在一个园形操场的四周摆放 N堆石子（NW100 ）,现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合

5、并的得分。編一程序由文件读入堆数N及每堆的石子数（W2 0 ，选择一种合并石子的方案.使得做N? 1次合并.得分的总和最小：选择一种合并石子的方案.使得做N? 1次合并.得分的总和最大c例如.图1所示的4堆石子.每堆石子数（从最上面的一堆数起？顺时针数）依 次为4 5 9 4。则3次合并得 分总和最小的方案为图2.得分总和最大的方案为图 3448* *4 545 - *5- *13 - *229999*图1图2总得分=8+13+22=：43444*4 5- 4* - 18*- 22 *914* *图3总得分=14+18+22=：54输入数据：文件名由键盘输入.该文件内容为：第一行为石子堆数N

6、:第二行为每堆的石子数.每两个数之间用一个空格符分隔。输出数据：输出文件名为output, txt从第1至第N行为得分垠小的合并方案。第 N+1行是空行。从第N+2行到第2N+1行是得分最大合并方 案。每种合并方案用N行表示，其中第1行（IWiWN ）表示第i次合并前各堆的石子数（依顺时针次序输出,哪一堆先输出均可）。耍求将待合并的两堆石子数以相应的负数表示.以便标识。输入输出范例：I输入文件内容：I |输出文件内容:| 4 一 5 9 4| 4 一 1 4 一 4| 4 1 8| 2 2（图 6. 2-4）第一天第三题最短编号序列试題表A和表B备含K（kW2 0 ）个元素.元素编号从1到嘉两

7、个表中的每个元素都是由0、1组成的字符串。（不是空格）字符串的长度 W 2 0。例如下面的两个表，每个都含3个元 素（k= 3 ）?1兀素编号111字符净1|兀索編号|11L字符串1!1 111tI 1I1II 1I111I 2|10111 |1 2 |10I 3|10 |1 3|0对于表A和表B?存在一个元素编号的序列 2 113,分别用表A中的字符串和表B中的字符串去宜换相应的元素编号，可得相同的字符串序列I 0 1111110,见下表：1 1I1111兀素编号序列121 11 1131II11111r1ttt1用表A的字符串替换丨1011111 11 11io1 Irrtt11用表B的字

8、符串替换|1110I 111i| 111i1i1 0i对表A和表B,具有上述性质的元素编号序列称之为S (AB)o对于上例S (AB) = 2 1 1 3?编写程序：从文件中读入表A和表B的各个元素.寻找一个长度最短的具有上述性质的元素編号序列S (AB) o注总：如果对于表 A和表B不存在S (AB),即找不到相同元素编号序列对应有相同的长度W 1 0 0的由0 .1组成的字符串序列.这时应输出“ No Answer无解九 输入数据A输入文件名由键盘输入该文件第1行为K的值：第2行至第K+ 1行为表A的内容(依次是元素編号从1到K的相应0、1字符串)：第K + 2行至第2K+ 1 行为表B的

9、内容(依次是元素编号从1至K的相应0. 1字符串)输岀数据：输出文件名为 OUTPUT. TXT,该文件只有一行。或是 S (AB)的值.或是“N Answer ” (无 解时)。s (AB) 是元素編号序列，输出时每个編号占一行。输入输岀范例：I输入文件内容：I I输出文件内容：I TOC o 1-5 h z 3I I 2I 11110 111 | | 1I 1 oI I 3第一天第四題“互邻”数码序列(已删除N位由0和1组成的字符串A、B可分别表示为A= a N a N-1 a i a 2 a 1B= bNbN-1- bi- ? b2bl其中，ai=O或1, bi=O或1W, NW15如果

10、存在某一位j (jGI-N),在该位上两串不同，即 ajHbj,而其余N-1位上的两串相同， 即ai=bi(i?l -N, iHj),则称A、B两串“互邻二比如，在 N=4 时，A=1100, B = 1000, As B 两串“互邻”，而 C = 1100, D = 1010, C. D 两 串不 “互邻”。編程要求：寻找一个含有2N个上述01串的序列，该序列满足以下要求：组成该序列的每一个01串都与其它串不同；第k个串与第k-1个串有柱互邻”关系.2WkW2N;该序列首项由输入指定例如22,抬定首项为01,则一个满足上述要求的序列为01 11 10 00输入数据文件名由键盘输入1I EXA

11、MPLE4.TXT该文件共有两行厂I M0DEL4.TXT第一行为N|2第二行为指定的序列首项1 011 011111 10| 00输出数据 输出文件为OUTPUT. TXT第一行为N第二行至第2N+1行依次输出序列的每一个串输入输岀举例参考输入文件：EXAMPLE4. TXT参考输出文件：MODEL!. TXT第一天第五題极值问题试題m、“为整数.且满足下列两个条件:(Dmx nG 1,2，K .(1 WKW 10A9 )(n “ 2-mnnT2)“2=1編一程序.由键盘输入K.求一组满足上述两个条件的 m. n,并且使亦2+2的值最大。例如.若K= 1 9 9 5.则9 8 7, n= 1

12、 5 9 7,则m、n满足条件，且可使 mP+r/2的值最大。 输入数据: 健盘输入K o输出数据：输出有两行：第一行为m的值：第二行为n的值。第二天试题下棋一个NXM的棋盘上每格均涂有黑色或白色，黑色代表建筑物，白色代表街道。例如下图是个6 X 8的棋盘。N为行数，M为列数。棋盘上只有建筑物和街道 .不存在广场，即任意一个2 X 2的区域不会全是白格。口3 口口口 ? 口? 口 ?45 口 ? 口口口 ?6 口口口 ? 口口口口（图 6? 5- 1 ）现有R枚棋子（代表R个行人）分别放在棋盘的 R个白格上.它们各自有一个目的格（也是白格 . 目的格有可能相同），希望它们能尽快地全部到达目的格

13、，行动规则如下：所有棋子同时行动一次称为一步，行动包括走入相邻白格或原地不动：同一时刻任何一白格内最多只有一枚棋子：棋子行动时可以“跟随”，但不允许“碰撞”。以下情况称为“跟随S、分别代表第1 . 2号棋子I I I I 久丿 I I I II 丨 I I -1 II1I_I_I_I 一步后 I_I_I_ 1I 1I 1I1I IIII - * II I或者111II1图 6? 5-2 ） 以下情况称为“碰撞”（图 6? 5-3 ）棋子在到达目的格后即可从棋盘上金走，此格在下一步才允许走入别的棋子所有棋子均到达目的格所用步数称为收盘步数 S t e p.嬰求：求 R= 1 时收盘步数最优解：求 R=2 时收盘步数最优解较优解酌情给分：R 2 时求较优解 以上均婆求能判无解（即按前述规则无法使全部棋子到达目的格）：2WMW16：2WNW16： 1WRW6：解的收盘步数均 W 6 0 步。输入数据：第1行是N （列数在前，行数在后九第2行至第 N+ 1 行是 NXM 的0、 1矩阵.矩阵元素间有一空格元素 0表示白格.1 表示黑格：第 N+2 行是 R：第N+3行至第N+2+R行分别是第1? R号棋子的起点横坐标 _起点纵坐标 _终点横坐标终点纵坐标 输入文件不会有错注总棋子有编号，編号不可颠倒。输出数据：若无解. 输岀文件为一 1 :至第S t e p步后所有棋子位0 0,