#3005. 「JOISC 2015 Day 4」Limited Memory

---

题目描述

译自 JOISC 2015 Day4 T2「Limited Memory」。

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C
• C++
• C++ (NOI)
• C++ 11
• C++ 11 (Clang)
• C++ 11 (NOI)
• C++ 17
• C++ 17 (Clang)

JOI 酱被选为了日本代表去参加国际信息学奥林匹克竞赛。为了提高信息处理速度，日本国际信息学奥林匹克竞赛委员会的 K 理事长提出了一个课题。

K 理事长在纸上写下了一个字符串 $S$，仅由 <，>，[ 和 ] 组成，但是 JOI 酱不知道字符串具体是什么。JOI 酱会被告知字符串的长度，他的课题是判断字符串 $S$ 是不是一个合法字符串。合法字符串的定义如下：

1. 空字符串（长度为 $0$ 的字符串）是合法字符串。
2. 假设 $x$ 是一个合法字符串，那么 <x> 也是合法字符串。
3. 假设 $x$ 是一个合法字符串，那么 $[x]$ 也是合法字符串。
4. 假设 $x$ 和 $y$ 都是合法字符串，那么 $xy$ 也是合法字符串。

例如 <>[] 和 [<>]<> 都是合法字符串，而 >< 和 [<]> 都不是合法字符串。

每天的中午，JOI 酱可以给 K 理事长打一个电话。电话里，JOI 酱可以指定一个整数 $I$，K 理事长会告诉他字符串 $S$ 的第 $I$ 个字符。

现在 JOI 酱有一个限制：不能用其它东西记录这个课题相关的笔记。JOI 酱每天晚上 $22$ 点睡觉，早上 $6$ 点起床。在睡眠中，她只能在脑中记下 $22$ 比特的信息。更准确的说，她会在睡前把一个 $0$ 到 $2^{22}-1$ 的整数记在脑内，然后第二天醒来根据这个整数来做决策。由于字符串长度是一开始就被告知的，JOI 酱是一直知道这个信息的。

JOI 酱每天睡前可以记住一个整数，或者发邮件告诉 K 理事长字符串 $S$ 是不是一个合法字符串。在后者的情况下，这个课题就结束了，K 理事长会判定你是否完成了这个课题。注意，邮件必须在课题开始后 $15000$ 天内发给 K 理事长，不然你就算没有完成这个课题。

---

任务

请编写一个程序实现 JOI 酱的策略，并正确解出上述课题。

---

实现细节

你需要实现一个过程来确定字符串是否正确。请包含头文件 memory.h。

程序需要实现以下过程。

int Memory(int N, int M)

• 参数 $N$ 表示字符串 $S$ 的长度。
• 参数 $M$ 表示上一天睡前记下的整数，在课题一开始的时候 $M = 0$。
• 在这个函数里必须恰好调用一次 Get 函数。
• 函数的返回值必须是一个 $0$ 到 $2^{22} - 1$ 的整数，或者 $-1$，或者 $-2$。如果返回值不在这些数里面，那么你的程序会被判为 Wrong Answer [1]。
• 返回值是 $0$ 到 $2^{22} - 1$ 的整数的话，表示这是睡前记下的数字。
• 返回值是 $-1$ 的话，表示用邮件回答 $S$ 是一个合法字符串。
• 返回值是 $-2$ 的话，表示用邮件回答 $S$ 不是一个合法字符串。
• 这个函数应该理论上只依赖 $N$，$M$ 和 Get 的返回值进行决策。在实际评测过程中这个函数会被调用 $2^{22} \times 4$ 次，更详细的信息请参考「评分的顺序」。

此外，程序中可以调用如下函数。

char Get(int I)

• 这个函数只能在调用 Memory 函数的时候被调用一次，如果调用了不止一次，你的程序会被判为 Wrong Answer [2]。
• 参数 $I$ 是一个 $1$ 到 $N$ 的整数，不满足此条件时，会被判为 Wrong Answer [3]。
• 返回值是 $S$ 的第 $I$ 个字符。

---

评分的顺序

每个测试文件会包含多组测试数据，每组测试数据对应的字符串 $S$ 的长度 $N$ 是一样的。评测过程如下，如果一旦被判定为了 Wrong Answer，你的程序会立刻被终止。

在给出参数 $N$，$M$ 和 Get 的返回值的情况下，检查函数 Memory 的行为。也就是说对于满足 $0 \le M \le 2^{22} - 1$ 的整数 $M$，做如下操作：

对于每个在 <，>，[ 和 ] 的字符 $c$，会执行如下操作：把 $N$ 和 $M$ 作为参数传给 Memory 函数，当 Get 被调用的时候，把 $c$ 返回出去。用 $m(M, c)$ 表示函数 Memory 的返回值。

上述操作会调用 $4$ 次 Memory 函数，需要检测 Get 的调用是否一致。如果 Get 被调用了，那么这 $4$ 次传给 Get 的参数 $I$ 必须一样。如果 Get 没有被调用，那么这 $4$ 次 Memory 的返回值必须要一样。不满足此条件时，会被判为 Wrong Answer [4]。当 Get 被调用的时候，我们令 $i(M)$ 表示 $I$ 的值（如果没有被调用 $i(M)=1$）。

对于每组数组里的字符串 $S$，如下操作会被用来模拟课题描述

1. 一开始 $M = 0$。
2. 重复执行如下操作：
   • 令 $c$ 是 $S$ 的第 $i(M)$ 个字符。
   • 把 $M$ 换为 $m(M, c)$。
   • $M = -1$ 或者 $M = -2$ 的情况下，跳出这个循环，进入下个流程。
3. 如果循环了超过 $15000$ 次，你的程序会被判为 Wrong Answer [5]。
4. 如果是以下某个情况，你的程序会被判为 Wrong Answer [6]。
   • $S$ 是一个合法字符串，但是 $M = -2$。
   • $S$ 不是一个合法字符串，但是 $M = -1$。

你的程序被认为是正确的。

---

编译与运行方法

「附加文件」中提供了 memory.h、grader-simple.c、grader-simple.cpp、grader-strict.c 和 grader-strict.cpp 五个文件。若你编写的程序名称为 memory.c 或 memory.cpp，请运行以下命令来编译：

C 语言：

gcc -std=c11 -O2 -o grader-simple grader-simple.c memory.c -lm
gcc -std=c11 -O2 -o grader-strict grader-strict.c memory.c -lm

C++ 语言：

g++ -std=c++14 -O2 -o grader-simple grader-simple.cpp memory.cpp
g++ -std=c++14 -O2 -o grader-strict grader-strict.cpp memory.cpp

当命令成功时，会产生一个可执行文件 grader-simple 或者 grader-strict。

注意实际评测时的程序与下发的样例评测程序并不相同。实际的 memory.h 函数实现将通过标准输入/输出与单独运行的交互器进行交互。

---

样例程序评测概要

grader-simple 不会模拟「评分的顺序」的第一步，但是会模拟课题的操作，具体可以参考「样例交互」。grader-strict 会严格按照「评分的顺序」执行。两者在输出上会有如下的不同：

• grader-simple 不会输出 Wrong Answer [4]，因为它并没有模拟这个操作
• grader-simple 和 grader-strict 不会输出 Wrong Answer [6]，但是会输出 $M$ 的值。

---

样例评测程序输入格式

grader-simple 和 grader-strict 将从标准输入读入以下数据。

第一行包含两个整数 $N$ 和 $Q$ $(0 \le Q \le 2^{31} - 1)$，表示字符串 $S$ 的长度和测试数据组数。

接下来 $Q$ 行，每行包含一个长度为 $N$ 的字符串 $S$。

---

样例评测程序输出格式

如果评测程序正常结束，grader-simple 和 grader-strict 将向标准输出输出以下信息。

• 程序正常结束的话，会输出 $M$ 的值。
• 运行过程中被判为错误时，以 Wrong Answer [x] 的格式报告并退出。

---

样例

样例评测输入

4 1
<>[]

样例交互

上述过程结束后 grader-simple 会输出 $-1$。

---

数据范围与提示

对于全部数据，满足 $1 \le |S| \le 100$，字符串 $S$ 仅由 <，>，[ 和 ] 组成。

本题共有 $6$ 个子任务。每个子任务的分数和附加限制如下：

Subtask	附加限制	分数
1	$S$ 的长度不超过 $8$	$10$
2	$S$ 的长度不超过 $14$
3	$S$ 的长度不超过 $24$	$5$
4	$S$ 的长度不超过 $30$
5	字符串 $S$ 仅由 < 和 > 组成	$10$
6	无附加限制	$60$