You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

点击此处下载题目文件。

监狱里有两个犯人 A 和 B。大发慈悲的典狱长决定给他们俩一个出狱的机会，只要他们能成功完成下面这个游戏，就能重获自由。

游戏规则如下。典狱长的房间里有一排 $16$ 个硬币，在桌面上排成一列，每枚硬币要么正面朝上，要么反面朝上。这 $16$ 枚硬币中，有一枚是特别的硬币，但外观上和其他硬币没有任何区别。典狱长先让 A 走进房间，告诉他哪枚硬币是特别的。接着 A 需要翻转 恰好 一枚硬币，不能多翻，也不能不翻。这枚硬币可以是特殊的硬币，也可以不是。接下来 A 离开房间，B 进入房间并观察这些硬币。如果 B 能正确指出哪枚硬币是特别的，就算成功，否则失败。

和传统的谜题一样，二人可以事先商定策略，但游戏的整个过程中，二人除了那 $16$ 枚硬币的正反面以外，不得有任何信息交流。

现在，假如你是这二人之一，你会怎样安排策略呢？

实现方式

你需要实现两份代码，分别命名为 encoder.cpp 和 decoder.cpp。

encoder.cpp 模拟 A 的角色。该代码的输入格式如下：

• 第一行一个正整数 $n$，表示硬币的数量。对于正式的测试点，总有 $n=16$。
• 第二行一个长度为 $n$ 的字符串，每个字符都为 01 之一，表示典狱长桌面上的硬币排列。第 $i$ 个字符为 0 表示第 $i$ 个硬币正面朝上，为 1 表示反面朝上。
• 第三行一个正整数 $k$，为特殊的硬币编号。保证 $1\leq k\leq n$。

该代码需要输出一个正整数，表示 A 翻转的硬币编号。你需要保证这个整数在 $1$ 到 $n$ 之间。

decoder.cpp 模拟 B 的角色。该代码的输入格式如下：

• 第一行一个正整数 $n$，表示硬币的数量。对于正式的测试点，总有 $n=16$。
• 第二行一个长度为 $n$ 的字符串，每个字符都为 01 之一，表示典狱长桌面上的硬币排列。第 $i$ 个字符为 0 表示第 $i$ 个硬币正面朝上，为 1 表示反面朝上。

该代码需要输出一个正整数，表示 B 猜测的特殊硬币编号。你需要保证这个整数在 $1$ 到 $n$ 之间。

两份代码都必须从标准输入读入，输出到标准输出，不使用任何文件读写操作。

评分方式

下发文件中有一个评分程序 grader.exe。请将你写的两份代码分别编译成 encoder.exe 和 decoder.exe，并将三个 exe 文件都放在同一个文件夹下。然后双击 grader.exe，打开该程序。该程序的输入格式为：

• 一行两个正整数 $n,T$，分别表示硬币的数量和测试的次数。

如果你输入的 $n=16$，$T=100$，那么 grader.exe 将认为这是一次正式的测试；否则将认为是一次调试。grader.exe 将会等概率随机生成 $T$ 组数据，并调用你的 encoder.exe、decoder.exe 来检验你的策略是否有效。接着它会反馈如下信息：

• 如果你某次 encoder.exe 给出的位置是非法的，将会提示并直接退出。
• 否则会返回你回答正确的数据组数。
• 如果是正式的测试，grader.exe 会将你的正确组数视为得分，并会给出你的分数的一个哈希值。保证各种可能得分的哈希值互不相同。请在 OJ 上提交一份输出这个哈希值的代码，OJ 便会记录你的得分。

grader.exe 的输出有少量英文提示，可酌情参考。

grader.exe 的实现细节与本题无关，故不予公开。我们保证对于 $1\leq n\leq 16$，$1\leq T\leq 100$ 的情形，该程序能正常工作。调用时可能要稍稍等一下，正常情况下大约需要 $3$ ~ $5$ 秒。

注意事项

本题下发文件除了上面提到过的 grader.exe 外，还有两份代码文件 sample_encoder.cpp 和 sample_decoder.cpp。这两份文件分别是你需要实现的 encoder.cpp 和 decoder.cpp 的示例，可以用作参考。

在 OJ 上提交的时候请不要直接提交得分的哈希值，而是提交一份输出这个哈希值的代码。