历年题目wc2008试题

1、WerC20082008 年信息学冬令营NOI Wer C2008竞赛时间：2008 年 1 月 30 日上午 8:00-13:00提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关第 1 页 共 13 页对于 Pascal 语言trip.pasN/Ac.pas对于 C语言trip.cN/Ac.c对于 C+语言trip.cppN/Ac.cpp题目名称游览计划窥孔超能纸带机目录trippasswordc可执行文件名tripN/Ac输入文件名trip.inpassword1.in password10inc.in输出文件名trip.outpassword1.out passwor

2、d10.outc.out每个测试点时限2 秒N/A1 秒测试点数目101010每个测试点分值101010是否有部分分有有有题目类型传统提交传统附加文件无checkerc_rWerC2008游览计划【问题描述】从未来过绍兴的小 D 有幸参加了 Wer C2008，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。主办者将绍兴划分为 N 行 M 列（NM）个方块，如下图（88）：景点含于方块内，且一个方块至多有一个景点。无景点的方块视为路。为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的；在景点内聘请导游（导游不是）。在选择旅游方案时，保证任意两

3、个景点之间，存在一条路径，在这条路径所经过的每一个方块都有或者该方块为景点。既能满足选手们游览的需要，又能够让总数最少。的例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的数目：图中用深色标出的方块区域就是一种可行的安排方案，一共需要 20名。由图可见，两个相邻的景点是直接（有景点内的路）连通的（如沈园和八字桥）。现在，希望你能够帮助主办方找到一种最好的安排方案。第 2 页 共 13 页2沈园12332八字桥故居东湖512大禹陵45兰亭6鉴湖1沈园八字桥故居东湖大禹陵兰亭鉴湖WerC2008【输入文件】输入文件中 trip.in 中第一行有两个整数，N 和 M，

4、描述方块的数目。接下来 N 行，每行有 M 个非负整数，如果该整数为 0，则该方块为一个景点；否则表示控制该方块至少需要的行首行末也可能有多余的空格。数目。相邻的整数用（若干个）空格隔开，【输出文件】输出文件 trip.out 由 N + 1 行组成。第一行为一个整数，表示你所给出的方案中安排的总数目。接下来 N 行，每行 M 个字符，描述方案中相应方块的情况：_（下划线）表示该方块没有安排 o（小写英文字母 o）表示该方块安排了；x（小写英文字母 x）表示该方块是一个景点；注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不一致（任何一行中，多余的空格都不允许出现），都可能导致

5、该测试点不得分。【样例输入】4 40 1 1 02 5 5 11 5 5 10 1 1 0【样例输出】6xooxoo xoox【样例说明】下图中深色方块安排了：第 3 页 共 13 页0110255115510110WerC2008【评分标准】本题共有 10 个测试点，每个测试点占本题总分数的 10%。对于每个测试点：如果仅输出了正确的如果输出了正确的 否则得 0 分；的总数目，则得到该测试点 50%的分数；总数目与方案，则得到该测试点的全部分数；【数据规模】所有的 10 组数据中 N, M，以及景点数 K 的范围规定如下：输入文件中的所有整数均不小于 0 且不超过 216。第 4 页 共 1

6、3 页测试点NMK122224543210346755897610910791010810103910101010101010WerC2008窥孔【问题描述】相传古越州人曾发明过一种信息的加密方式，他们将信息表达为 10 进制数字序列并按顺序刻写在一个易碎陶瓷圆盘的边沿上。很偶然的机会，得到了一个陶瓷圆盘，但陶瓷圆盘被封装在一个可以旋转的偏振盒中（偏振是一种光学现象，只有沿特定方向振动的光波可以通过偏振只能看到连续的 4 个数字（在圆周上连续）。为了研究陶的团队决定打开偏振盒取出陶瓷片，但是不幸的是，在盒）。透过偏振盒，瓷盘上的数字信息，此过程中陶瓷片破碎了。在团队感到万分沮丧的时候，突然想起

7、他曾经在笔记本上记下了一些已经看到的四位数，但是由于偏振盒是可旋转的，这些四位数的位置与顺序已经不可分辨。决定通过分析下来的这些四位数尽可能的恢复原始数据。于是找到了你。你的任务是恢复圆盘的原始数据。你将得到 N 个是寻找一个尽量短的数字环，该数字环应包含每个所所的四位数，任务的四位数。【输入文件】这是一道提交型试题，所有的输入文件 password*.in 都已在目录下。输入文件第一行为四位数的个数 N，接下来 N 行每行一个四位数（可能包含前导 0）。【输出文件】输出文件 password*.out 应包含两行，第一行为一个整数 M，表示你找到的数字环长度。第二行包含 M 个数字(相邻数字

8、之间没有空格, 见样例)，表示数字环。第 5 页 共 13 页WerC2008【样例输入】1234【样例输出】534512/ 注: 输出 12345 , 23451, 45123 , 51234 皆可。【评分标准】每个测试点单独评分。对于每一个测试点，如果你给出的输出文件不合法，如文件格式错误、输出解不符合要求等，该测试点得 0 分。否则设你的输出长度为 ans，对于不同的测试点， c7 c8还设有 9 个评分相关的常数 c1 c2 c3 c9，你在该测试点中的得分由下列陈述得出：c4c5c6如果 ans 4N，得 0 分。如果 ans如果 ans如果 ans如果 ans如果 ans如果 an

9、s如果 ans如果 ans如果 ans4N，得 1 分。c9，得 2 分。c8，得 3 分。c7，得 4 分。c6，得 5 分。c5，得 6 分。c4，得 7 分。c3，得 8 分。c2，得 9 分。如果 ans = c1，得 10 分。如果 ans c1，得 12 分。如果满足多个条件，取得分最大者为最终得分。【如何测试你的输出】你可以使用 checker 程序检查你的输出，格式为：./checker TestNo其中 TestNo 为测试点。例如你已经得到了数据 5 的输出 password5.out，可以使用命令./checker 5 来测试你的输出是否合法。【特别提示】请妥善保存输入文

10、件*.in 和你的输出*.out，及时备份，以免误删。第 6 页 共页WerC2008超能纸带机【问题描述】超能纸带机（Capability Advanced Machine, CAM）是由一个简单的程序、一条无限长的纸带和一个读写头的。纸带由一长列单元格，每个单元格上可以写 08 的这几种符号之一，也可以为空。为了方便，使用符号 9 表示对应的单元格为空。程序开始运行前，纸带上已经有一些符号，这个符号序列称为输入。如下面就是一个输入：100811811081输入必定是一串连续的非空符号，除了输入符号，纸带的其他地方都是空的。上面的输入在纸带上表示如下：读写头始终指向纸带的一个单元格。它可以由

11、程序控制左右移动，可以由程序控制向纸带上写入一个符号，还可以读出单元格上的符号作为程序运行的参数。程序开始运行时，读写头指向纸带的第一个非空符号。如下面是程序开始运行时的读写头和纸带。超能纸带机的程序非常简单，只有三种指令：L该指令的作用是向读写头指向的纸带单元格上写入符号 C，并将读写头向左移动一个单元格。符号 C 可以是 09 或?之一，其中，C=9 表示向纸带写入一个空符号，而 C=?表示不改变纸带上的当前符号。R该指令的作用是向读写头指向的纸带单元格上写入符号 C，并将读写头向右移动一个单元格。符号 C 可以是 09 或?之一，其中，C=9 表示向纸带写入一个空符号，而 C=?表示不改

12、变纸带上的当前符号。第 7 页 共 13 页R L 991008118110818999910081181108199WerC2008LOOP-END该指令是一个循环指令，有两个符号表 H 和 E，符号表由 09 和?中的零 个或多个符号 （其中?为通配符，用以匹配任何符号）。指令中，循环体内可以是任何合法的零个或多个指令（循环可以无限层嵌套）。指令的执行过程如下：首先判断当前读写头上的符号是否在符号表 H 中（注意?可以匹配任何符号，所以如果 H 中包含?，则条件一定成立），如果不在，则跳出循环，否则继续执行。注意：当 H 为空时，循环体将不会执行。执行循环体内的内容。当执行完循环体的内容后

13、，判断当前读写头的符号是否在符号表 E 中（同样，E 中的?也可以匹配任何符号），如果不在，则跳出循环，如果在，则跳转到第 1 步。注意：当 E 为空时，则条件必然不满足，将跳出循环。下面是一个 CAM 的程序（#和其后面的内容表示注释），其功能是：当读写头指向一个用二进制表示的整数的第一个符号时，该程序将此整数加 1。设有一个整数 39：第 8 页 共 13 页91001119# 将读写头移至该整数的最后一个单元格LOOP 0 1R ? END ?# 上面的程序中，只要读写头处的符号是 0 或 1 就右移，所以现在指针指向的是# 整数最后一个单元格的后一个单元格，还需要向左移动将读写头移回到

14、整数最后一位。L ?# 将整数加 1，首先将末尾连续的 1 变成 0，然后将最后一个 0 变成 1LOOP 1L 0 END ?L 1# 将读写头移回整数的起始位置LOOP 0 1L ? END ?# 已经移出整数，需要向右移动一个单元格使读写头指向整数的第一个单元格R ?LOOP END WerC2008对于下面的输入，该程序的运行过程如下：对一组只包含整数的算术表达式求值，表达式运算包含加法、减法和乘法。乘法优先级最高，但可以通过使用小括号来改变优先级。对于每个表达式，其参与运算的都是变量或者常数 1。变量最终会用整数代替，在代入变量的值后表达式的任何一步不会出现负数或 0 的情况。表达式

15、中最多包含三个运算符（注意是三个而不是三种，所以 a+b+c 是包含两个运算符的表达式），且不会出现两个乘号。写一个程序，对于每一个表达式产生一个 CAM 程序，该程序的输入是变 量的值，在运行完该程序后，纸带上只剩下表达式的运算结果。为了简化问题，运算结果中可以保留多余的前导 0。使用下面的格式表示变量的值：首先将第一个字母(a)的值表示成二进制，然后将第二个字母(b)的值表示成二进制，在两个字母前用一个符号 8 连接，接着是第三个字母，第母。母不会输入，同样，如果只有 k 个字如果表达式中只有三个字母，则第母，则第 k+1 个字母不会输入。例如，一个表达式中有 a,b,c 三个字母。如果a

16、=10, b=4, c=7，则输入为101081008111如果 a=1, b=100, c=3，则输入为181100100811如果表达式中没有任何字母，则输入为空，这时候，纸带上的每个单元格里都是空字符（9）。字母的值不会是 0 或负数，变量的值都不会超过 1023，但运算的过程和结果有可能超过 1023。第 9 页 共 13 页步骤纸带和读写头状态步骤纸带和读写头状态开始89100111991001109199100111991001009210910011199100000931191001119910100094129100111991010009513910011199101000

17、9614910011199101000971591001119WerC2008【输入文件】输入文件 c.in 仅一行，为一个四则运算表达式。该表达式满足：至多有三个运算符至多有一个乘号可能包含一个或多个括号，但括号不会直接被括号包含，如(a+b)*c不会出现，正确的出现方式是(a+b)*c。注意，这不代表括号不会嵌套，如 a+(b+(c+d)是合法的。表达式中运算对象仅包含字母和 1如果第i 个字母在表达式中出现，则第 i-1 个字母一定在表达式中出现。如：如果表达式中有 c，那么表达式中一定有 b 和 a。如果按照先括号内再括号外，先乘除，后加减，同级运算从左到右的顺序运算，则在运算的任何一

18、步，你都可以假设值为正数。所以类似(1-1)的表达式是不可能出现的。但是(a-b)这样的表达式可能会出现，因为 a,b 的值由输入给定，而可以设定输入使 a-b 的值为正。【输出文件】输出文件 c.out 包含一个 CAM 的程序，该程序仅包含上面所述的几种指令。你的输出格式必须满足：每行至多一条指令所有的指令标识符(LOOP, END, L, R)都大写LOOP 和 END 后面的符号表每两个符号之间用至少一个空格分隔，符号表的第一个符号与指令标识符之间用至少一个空格分隔。符号表可以不按大小顺序。同一个符号可以重复，但重复的符号只算一次。如下面是一个正确的 LOOP END 指令它和下面的指

19、令是等效的可以在程序的任意位置放任何个数的空格或制表符，但这些分隔符不能将指令标识符分开。如：第 10 页 共 13 页LOOP?ENDLOOP 1 3 6END ?LOOP 6 1 3END 7 1 ? 1WerC2008是可以的，但是的，因为 LOOP 被分开了。可以用#号标识一条行注释，但如果用一个空格分隔有指令，#和指令之间至少过 100000 行。输出的程序【样例输入/输出】【样例说明】上面的样例和问题描述中的例子一样，这里去掉了注释（你可以加上，不影响正确性）和最后将指针移动到整数开始的部分。这对结果没有影响。【怎样测试你的程序】在你的用户目录下，有一个程序 c_r，你可以使用这个

20、程序来运行你的输出。该程序是一个 CAM 的模拟程序，它能从 c.out 中读入程序，从 t.in 中读入输入串，然后将运行的结果输出到 run.log 中。维了正确执行 c_r，你需要建立一个 t.in 文件，为初始的输入。t.in 的第一个数为输入的长度 e，后面有用空格分隔的 e 个数，为输入。如下面是一个合法的 t.in：使用下面./c_r令运行你的程序：在 run.log 中会出现运行的结果第 11 页 共 13 页51 0 0 1 1输入(c.in)输出(c.out)a+1LOOP 0 1R ? END ? L ?LOOP 1L 0 END ? L 1LOOP?ENDWerC2008其中，第一行表示运行了多少步，第三行表示运行到最后时纸带和读写头的状态。该状态的表述方法是：按顺序输出纸带上从第一个非空符号到最后一个非空符号之间的所有符号，如果一个符号前有 H，则表示当前读写头在此位置，如：表示的