4283: 「CTSC2017」密钥

一个密钥是一个长度为 $n = 2k + 1$ 的字符串，它包含 $1$ 个字母 $X$、$k$ 个字母 $A$ 和 $k$ 个字母 $B$。例如 $k = 3$ 时，$BAXABAB$ 就是一个密钥。 如下图所示，可以按顺时针顺序把这 $2k+1$ 个字母排成一个圈：  在 $k$ 个字母 $A$ 中，有一部分可以定义为「**强的**」。具体来说，从 $X$ 出发顺时针走到某个 $A$ 时，如果途中 $A$ 的数目**严格多于** $B$ 的数目，则称此字母 $A$ 为强的。 对于上面的例子来说，顺时针方向从字母 $X$ 数起第 $1$ 个和第 $2$ 个字母 $A$ 是强的，而第 $3$ 个字母 $A$ 不是强的。 一个密钥的**特征值**就是其中包含的强的字母 $A$ 的个数。 天才小朋友 KT 给出了一个结论： 假设 $k$ 个字母 $A$ 所在的位置已经固定，但是剩下的 $k$ 个 $B$ 和 $1$ 个 $X$ 的位置是未知的。（注意，满足这样要求的密钥一共有 $k + 1$ 个，因为字母 $X$ 还剩下 $k + 1$ 个可能的位置。） 可以证明：所有这 $k + 1$ 个可能的密钥的特征值是各不相同的，它们恰好为 $0,1,2,...,k$。 下页的图是一个具体的示例，从左到右的四个子图中分别有 $3$ 个，$2$ 个，$1$ 个，$0$ 个字母 $A$ 是强的。  类似地，如果固定 $k$ 个字母 $B$ 的位置，那满足条件的所有 $k + 1$ 个密钥的特征值也各不相同，恰好为 $0,1,...,k$。 现在你需要解决以下三个问题： 1. 给定密钥中所有 $A$ 的位置，当密钥的特征值为 $0$ 时，请问 $X$ 在哪个位置。 1. 给定密钥中所有 $A$ 的位置，当密钥的特征值为 $S$ 时，请问 $X$ 在哪个位置。 1. 给定密钥中所有 $B$ 的位置，当密钥的特征值为 $S$ 时，请问 $X$ 在哪个位置。 注意：字符串的 $2k + 1$ 个字母的位置由 $1$ 到 $2k + 1$ 编号。 #### 例子 1 假定 $k = 3,S = 2$。那么： 当 $A$ 的位置是 $\{2,4,6\}$ 且特征值为 $0$ 时，$X$ 的位置在 $7$； 当 $A$ 的位置是 $\{2,4,6\}$ 且特征值为 $2$ 时，$X$ 的位置在 $3$； 当 $B$ 的位置是 $\{2,4,6\}$ 且特征值为 $2$ 时，$X$ 的位置在 $5$。 #### 例子 2 假定 $k=9,S=7$。那么： 当 $A$ 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $0$ 时，$X$ 的位置在 $14$； 当 $A$ 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $7$ 时，$X$ 的位置在 $18$； 当 $B$ 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $7$ 时，$X$ 的位置在 $17$。

只包含一组测试数据。 第一行包含一个整数 $k$ ，意义如题所述。 第二行包含一个整数 $\text{seed}$ ，这个数将用于生成一个 $k$ 元集合 $P$。 第三行包含一个整数 $S$，意义如题所述。 保证 $0\leq S\leq k \leq 10^7,1\leq \text{seed} \leq 10000$。 提供了三个用于生成输入数据的文件 `cipher.cpp/c/pas`。其中读入部分已经完成，在数组 $p[]$ 中，若 $p[i] = 0$ ，表示 $i$ 不属于集合 $P$，否则，$i$ 属于集合 $P$。

输出三行，每行一个数，依次对应问题描述中的三个子问题的答案。 即： 1. 第一个数表示当 $k$ 元集合 $P$ 代表 $A$ 的位置且特征值为 $0$ 时 $X$ 的位置。 1. 第二个数表示当 $k$ 元集合 $P$ 代表 $A$ 的位置且特征值为 $S$ 时 $X$ 的位置。 1. 第三个数表示当 $k$ 元集合 $P$ 代表 $B$ 的位置且特征值为 $S$ 时 $X$ 的位置。

5
3344
2

10
1
2