[CTSC2017]密钥

内存限制：512 MB 时间限制：1000 ms

一个密钥是一个长度为 $n = 2k + 1$ 的字符串，它包含 $1$ 个字母 $X$、$k$ 个字母 $A$ 和 $k$ 个字母 $B$。例如 $k = 3$ 时，BAXABAB 就是一个密钥。

如下图所示，可以按顺时针顺序把这 $2k+1$ 个字母排成一个圈：

屏幕快照 2019-07-08 下午4.20.32.png

在 $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$ 是强的。

屏幕快照 2019-07-08 下午4.20.48.png

类似地，如果固定 $k$ 个字母 $B$ 的位置，那满足条件的所有 $k + 1$ 个密钥的特征值也各不相同，恰好为 $0, 1, …, k$。

现在你需要解决以下三个问题：

给定密钥中所有 $A$ 的位置，当密钥的特征值为 $0$ 时，请问 $X$ 在哪个位置。
给定密钥中所有 $A$ 的位置，当密钥的特征值为 $S$ 时，请问 $X$ 在哪个位置。
给定密钥中所有 $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$，意义如题所述。

第二行包含一个整数 $seed$，这个数将用于生成一个 $k$ 元集合 $P$。

第三行包含一个整数 $S$，意义如题所述。

保证 $0 ≤ S ≤ k ≤ 10^7。1 ≤ seed ≤ 10000$。

一个用于生成输入数据的代码如下。其中读入部分已经完成，在数组p[]中，若p[i] = 0，表示 $i$ 不属于集合 $P$，否则，$i$ 属于集合$P$。

#include <stdio.h>
#include <string.h>
int p[20000005];
int seed, n, k, S;
int getrand() {
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}
void generateData() {
    scanf( "%d%d%d", &k, &seed, &S );
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for( int i = 1; i <= n; ++i ) {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while( t > k ) {
        while ( p[i] == 0 ) ++i;
        p[i] = 0;
        --t;
    }
    while( t < k ) {
        while( p[i] == 1 ) ++i;
        p[i] = 1;
        ++t;
    }
}
int main() {
    generateData();
    return 0;
}

输出三行，每行一个数，依次对应问题描述中的三个子问题的答案。

即：

第一个数表示当 $k$ 元集合 $P$ 代表 $A$ 的位置且特征值为 $0$ 时 $X$ 的位置。
第二个数表示当 $k$ 元集合 $P$ 代表 $A$ 的位置且特征值为 $S$ 时 $X$ 的位置。
第三个数表示当 $k$ 元集合 $P$ 代表 $B$ 的位置且特征值为 $S$ 时 $X$ 的位置。

样例输入 1

5
3344
2

样例输出 1

10
1
2

样例输入 2

500000
4545
234567

样例输出 2

999992
246922
753067

【样例解释】

第一个样例中，$P$ 数组为 $1$ 的元素的下标分别为 $5, 6, 7, 8, 9$。

【数据范围与约定】

对于 30% 的数据，$k ≤ 10^3$。

对于 50% 的数据，$k ≤ 10^5$。

对于 100% 的数据，$k ≤ 10^7$。

对于每个测试点, 得分为以下三部分得分之和：

如果第一问回答正确，你将获得 3 分。
如果第二问回答正确，你将获得 4 分。
如果第三问回答正确，你将获得 3 分。

如果你仅仅知道部分答案，请也务必按此格式要求输出三个数。否则你可能会因格式错误无法得分。

（comet 暂不支持部分分）

C0105 [CTSC2017]密钥

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示