题目名称	程序文件名	时限	内存限制	备注
ZZ机	zz.*	2S	64MB	样例数据较大，另附文件
化简括号	shorten.*	1S	32MB	此题使用Special Judge
社团招新	campus.*	3S	4MB	此题使用Special Judge
雕塑安置	arrange.*	1S	32MB	--
修剪花卉	makeup.*	1S	32MB	--
定向越野	adven.*	1S	32MB	--

感谢大家对本次模拟赛的支持和参与，祝大家取得好成绩！

ZZ机

（请选手一定要仔细读题目以免产生误解）

程序名：zz.*                                                                                        时间限制：2秒

输入：zz.in                                                                                           内存限制：64M

输出：zz.out

问题背景：

ZZ作为上海交通大学计算机系的学生，免不了要修《计算机科学导论》这门课，以便对本学科产生一种概貌性的认识。在某堂有关机器语言的课上，老师提到了ZZ机（ZZ：怎么和我同名？？）这个概念。她称：众所周知，计算机的功能是极其强大的，也许我们会认为这些功能的实现是由于它内部复杂的电路设计。但是事实上，一台裸机（没有任何软件支持的机器）提供给我们的功能是十分简单的，它的电路设计也只是一些简单模块的组合，但数量极大。像我们的这台ZZ机只提供了12条基本指令，但就是利用如此简单的指令集也同样可以实现非常复杂的功能。

下面介绍一下ZZ机的结构：

我们的ZZ机包括一个CPU（Central Processing Unit）和一个主存储器（Main Memory）。CPU与主存储器之间用一条总线（Bus）相连。

ZZ机的主存很小，只有256个单元（Cell），每个单元用00到FF的十六进制整数标识地址（机器内表示为0000 0000到1111 1111）。每个单元能够存储一个字节的信息（即十六进制数00到FF）。

ZZ机的CPU中包含一个运算/逻辑单元ALU（Arithmetic/Logic Unit）和一个控制单元（Control Unit）。其中的ALU提供给我们5种基本运算（指令集中5到9）。而控制单元中包含一个寄存器组（Register Group），一个程序指针（Program Counter）以及一个指令寄存器（Instruction Register）。其中寄存器组包括16个多用途的寄存器从0到F编号（每个寄存器用一位十六进制数标识，机器内表示为0000到1111）。每个寄存器的可以存储一个字节的信息。程序指针包含一个字节，用于记录主存单元的地址从00到FF。指令寄存器包含2个字节，记录一条正在被执行的指令。（ZZ机的一条完整指令用2个字节表示）

再来介绍一下我们ZZ机的程序执行过程（Program Execution）：

控制器完成一项工作要重复进行一个三歩过程即所谓一个指令周期（Machine Cycle）。

1.提取  在主存中获取一条指令（地址由程序指针给出）并存储在指令寄存器中，然后使程序指针的值增加2，指向下一条指令，如果程序指针的值超过FF则对256取模。

2.解码  对存储在指令寄存器中的指令进行解码。如果指令错误（如出现指令不在所给的指令集内等情况），则程序非法结束。

3.执行  执行指令寄存器中的指令。如果程序没有结束，则返回第一步。

ZZ机的输出设备

ZZ机的输出设备是一台穿孔纸带机（设备编号为1）。纸带机可在纸带上打孔（有孔处代表1，无孔处代表0），代表输出的数值的二进制编码。

最后介绍ZZ机的指令集：

每条指令由两个主存单元的内容即一个四位16进制数构成，分成两个部分，第一部分表示表示要执行的操作（一位16进制数），其余3位为被操作的对象。

下表列出了ZZ机的指令集

1	RXY	把主存地址XY的内容放到寄存器R
2	RXY	把数据XY存入寄存器R中
3	RXY	把寄存器R的内容写入主存XY
4	0RS	把寄存器R的内容复制到寄存器S
5	RST	把寄存器S的内容和寄存器T的内容作为整型数相加，并把值放在寄存器R
6	RST	把寄存器S的内容和寄存器T的内容取或，并把值放在寄存器R
7	RST	把寄存器S的内容和寄存器T的内容取与，并把值放在寄存器R
8	RST	把寄存器S的内容和寄存器T的内容取异或，并把值放在寄存器R
9	R0X	将寄存器R的内容向右循环移位X位
A	RXY	如果寄存器R的内容等于寄存器0，则程序指针指向地址XY（不再增加2）并执行接下去的语句
B	RXY	把主存中地址为XY的单元的内容输出到设备R（无论输出到什么设备都不会出错）
C	000	程序终止

注意：1.加法溢出情况的处理，如FF+01=00。

2.若指令中0的位置（如指令C000中有3个0位置）出现其他的数，不影响指令的执行。

末了，老师道：到此为止，相信大家应该对我们的这台ZZ机已经有所了解。然而到底这台ZZ机能够发挥多大的作用，还要靠程序员的天才。

你们的任务就是，给出程序员顺序存入ZZ机主存的K段程序（每段程序运行之前所有寄存器清0，一段程序执行结束后再输入下一段程序），输出当所有程序段都执行完毕后，哪几段程序输出到纸带上的结果是相同的。由于纸带长度很有限，所以程序员规定给每段程序输出的长度为2个字节（固定），若输出不足2个字节则后面用0补足（纸带未被打孔使用），若输出超过2个字节或没有输出则视为输出错误。

输入说明：

每个测试数据的第一行包含1个正整数K（K≤500），表示有K个程序，每个程序包含257行，前256行每行两位16进制数(中间无空格，用大写字母A到F表示超过9的部分)，表示每个主存单元的内容（00到FF），第257行表示程序指针的内容。

输出说明：

第一行输出一个正整数M，表示把K个程序分成M个类（ERROR类也计算在内），每个类中的程序输出到纸带的结果相同。

下面M行,每行输出一个类的全部元素（空格分隔）。输出完毕后空6个空格后输出“OUTPUT:”然后输出纸带上的结果。

注意：

1.         类的输出顺序按每个类中元素的个数从大到小排列，若元素个数相同的类有多个，则按照每个类的首元素的编号从小到大输出。

2.         类中元素（程序编号）的输出顺序按编号从小到大输出。

3.         若程序输出超过2个字节或无输出则视为输出错误，归为同一个类OUTPUT ERROR，先输出一行“OUTPUT ERROR:”再输出一行所有程序名，若没有这样的程序则不输出OUTPUT ERROR，且位于PROGRAM ERROR类之前。

4.         每个能够正常结束的程序都在100000个指令周期内结束。若程序无法正常结束，则要强制退出，且把这类程序与指令错误的程序归为同一个类PROGRAM ERROR，先输出一行“PROGRAM ERROR”再输出一行所有程序名，若没有这样的程序则不输出PROGRAM ERROR。

5.         如果一个程序同时出现OUTPUT ERROR和PROGRAM ERROR两种错误则只记录在PROGRAM ERROR中。

样例数据：

输入文件zz.in

4

11

00

B1

00

C0

00

00

…

00

00 （258行）

00

12

11

B1

02

C2

AB

00

…

00

01 （515行)

32

11

01

00

B1

01

C0

00

00

…

00

00  (772行)

B1

00

B1

00

B1

00

C0

00

00

00

…

00

00  (1029行)

输出文件 zz.out

3

1 2      OUTPUT:0001000100000000

OUTPUT ERROR:

4

PROGRAM ERROR:

3

注：程序1和2的结果是00010001（后面的0补足空下的字节）

程序3由于指令错误而退出

程序4由于输出到纸带机超过2个字节而出错

    附样例 zz.in

4
11
00
B1
00
C0
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
12
11
B1
02
C2
AB
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
01
32
11
01
00
B1
01
C0
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
B1
00
B1
00
B1
00
C0
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00

化简括号

程序名：shorten.*                                                                              时间限制：1秒

输入：shorten.in                                                                                 内存限制：32M

输出：shorten.out

问题背景：

最近ZZ苦于《数学分析》课的老师上课速度飞快，以致抄板书的速度跟不上老师的进度，特别是在遇到复杂的多项式因子之积时，总会有连续多个括号产生，比如(x(x(x(x(x+2)))))…于是ZZ有时不得以将单个或多个连续右括号“)”改写成“]”（但在时间充裕时他仍然会按常规写法而不用改写）。

然而课后ZZ在复习时发现，将“]”还原成对应数量的“)”实在是太麻烦了，恳求你编写一个程序告诉他每个“]”与多少个“)”匹配。

注：“(”“)”“]”均为半角的括号。

输入说明：

第一行两个整数0≤N≤10⁷, 0≤M≤5*10⁶, M≤N。N代表括号串的长度，M代表“]”的个数。

第二行开始为括号串，由“(”“)”“]”组成，每行最多72个字符。

输出说明：

第一行为一个数字，0或1。如果输入文件中括号能全部匹配，则输出1，否则输出0。

第二行开始，每行为一个整数，依次输出“]”所代表的“)”的个数。

如果有多种匹配方案，输出任意的一个。

样例输入：

8 2
(((((])]

样例输出：

1
3
1

数据范围：

对于40%的数据，保证N≤100

对于80%的数据，保证N≤200,000

对于100%的数据，保证N≤10,000,000

社团招新

程序名：campus.*                                                                             时间限制：3秒

输入：campus.in                                                                               内存限制：4M

输出：campus.out

问题背景：

开学以后，紧接而来的就是社团招新，是各大社团争抢人才的时段，每天中午都会收到数不清的传单……一阵轰轰烈烈之后，各社团的“高层”就开始清点“战利品”——即吸引到的人才。Z社连续数年被评为“十佳社团”，因此得以招募到许许多多大一的freshman，社长想要知道来自哪个学院的新社员人数超过了新社员总人数的一半（令该学院编号为x），以及新社员中来自哪个学院(除编号为x的那个学院之外)的人数为单数（令该学院编号为y）。换句话说，可以默认x,y都是唯一的并且y与x不相等。

输入说明：

数据的第一行包括一个正整数N，表示新社员的数量、

接下来的N行，每行包括一个正整数 a_i，表示第i位新社员所属学院的编号 (a_i≤2⁶³-1)

输出说明：

文件包括一行，两个整数，x与y。两个整数之间用一个空格分开，此题使用Special Judge，答对x或y均有部分分。

样例输入：

12

1

2

2

4

4

1

1

1

1

5

1

1

样例输出：

1 5

数据范围：

对于30％的数据，保证N≤1,000

对于60％的数据，保证N≤100,000

对于100％的数据，保证N≤1,000,000

雕塑安置

程序名：arrange.*                                                                             时间限制：1秒

输入：arrange.in                                                                                内存限制：32M

输出：arrange.out

问题背景：

话说交大为了美化校园，请设计师设计了N座精美的雕塑，准备安置在校园里。整个校园可以抽象为一个N*N的大网格，并且为了平均分布这些雕塑，学校决定网格的同一行、同一列必须有且只有一座雕塑，还规定不能出现1座以上的雕塑出现在同一个1*1网格里的情况。然而某些1*1的网格恰巧是一片湖或者是食堂，这些网格就不能安置雕塑了。每个雕塑的造型是相同的，这样同一种安置方案中交换排列都算一种。

学校想知道有多少种安置方案，你能解决这个问题吗？

输入说明：

第一行，两个整数 n,m用空格分开 n表示n*n的大网格，m表示不能安置雕塑的位置个数。

第二行至第m+1行，每行两个整数x,y，用空格分开，表示坐标（x,y）的1*1网格上不能安置雕塑。

输出说明：

       仅一行，方案的个数。

样例输入：

6 7

1 1

2 1

2 2

3 3

3 4

4 3

4 4

样例输出：

184

数据范围：

对于50%的数据， 保证n≤10,m≤10

对于100%的数据，保证n≤20,m≤10，方案总数≤2⁶³-1

修剪花卉

程序名：makeup.*                                                                             时间限制：1秒

输入：makeup.in                                                                               内存限制：32M

输出：makeup.out

问题背景：

ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。

于是当日课后，ZZ就向老师提出了这个问题：

一株奇怪的花卉，上面共连有N朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。

每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。

所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。

经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。

老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，相当不爽，于是又拿来问你。

输入说明：

第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N朵花。

第二行有N个整数，第I个整数表示第I朵花的美丽指数。

接下来N-1行每行两个整数a,b，表示存在一条连接第a朵花和第b朵花的枝条。

输出说明：

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。

样例输入：

7

-1 -1 -1 1 1 1 0

1 4

2 5

3 6

4 7

5 7

6 7

样例输出：

3

数据范围：

对于60%的数据， 保证N≤1,000

对于100%的数据，保证N≤16,000

定向越野

程序名：adven.*                                                                               时间限制：1秒

输入：adven.in                                                                                   内存限制：32M

输出：adven.out

问题背景：

交大闵行校区位于上海西南处，离市中心距离略远，因此占地面积巨大，足有5000亩之多，校园周长达8公里，因而校团委学生会充分利用了资源，每年都要在校园里举办定向越野比赛，但规则与普通定向越野不同，每个队被要求从某个起点出发最后到达终点，只要是地图上每个被标注的点都可以走，经过一个点时必须在打卡器上打卡作记录，记录该点的打卡器所在位置的海拔高度，高度用一个非负整数来量度，该数将会被所保存在卡中。最后到达终点时，该队的成绩就为卡中记录的最大数与最小数之差，差最小的队伍将摘取桂冠。

ZZ和他的同学也参与了这项运动，拿到地图后，他们想要迅速找到一条最佳路线以确保获得冠军。

PS：其实光脑子好能算出最佳路线还不够，还得能跑，但我们假设ZZ他们队个个都是SUPERMAN，只要你帮助他们找到了最佳路线，他们就能获得冠军。

输入说明：

数据的第一行包含一个正整数n，表示校园地图上共有n*n个被标注的点（n≤100）

接下来n行每行有n个非负整数a_i,j，表示该点的打卡器所在位置的高度。（a_i,j≤200）

ZZ和他的同学从(1,1)出发，目的地为(n,n)

输出说明：

文件包含一个整数，即最小的高度差的值

样例输入：

5

1 1 3 6 8

1 2 2 5 5

4 4 0 3 3

8 0 2 2 4

4 3 0 3 1

样例输出：

3

注：最佳路线为(1,1)-- (1,2)-- (2,2)-- (2,3)-- (3,3)-- (4,3)-- (4,4)-- (5,4)-- (5,5)。路线上最高高度为3，最低高度为0，所以答案为3。当然，最佳路线可能不止一条。

数据范围：

对于40%的数据， 保证N≤20

对于100%的数据，保证N≤100