[CTSC2017] 密钥

题目描述

一个密钥是一个长度为 n = 2k + 1 的字符串,它包含 1 个字母 X、k 个字母 A 和k 个字母 B。例如 k = 3 时,BAXABAB 就是一个密钥。 如下图所示,可以按顺时针顺序把这 2k+1 个字母排成一个圈: ![](https://cdn.luogu.com.cn/upload/pic/5481.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 是强的。 ![](https://cdn.luogu.com.cn/upload/pic/5482.png) 类似地,如果固定 k 个字母 B 的位置,那满足条件的所有 k + 1 个密钥的特征值也各不相同,恰好为 0, 1, …, k。 现在你需要解决以下三个问题: 1. 给定密钥中所有 A 的位置,当密钥的特征值为 0 时,请问 X 在哪个位置。 2. 给定密钥中所有 A 的位置,当密钥的特征值为 S 时,请问 X 在哪个位置。 3. 给定密钥中所有 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。 在 cipher/下,包含两个用于生成输入数据的文件 cipher.cpp/pas。其中读入部分已经完成,在数组 p[] 中,若 p[i] = 0,表示 i 不属于集合 P,否则,i 属于集合P。 [百度网盘链接>> 密码:9vr3](http://pan.baidu.com/s/1i55NdWx) 请自行编译 ```cpp #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; } ```

输出格式


输出三行,每行一个数,依次对应问题描述中的三个子问题的答案。 即: 1. 第一个数表示当 k 元集合 P 代表 A 的位置且特征值为 0 时 X 的位置。 2. 第二个数表示当 k 元集合 P 代表 A 的位置且特征值为 S 时 X 的位置。 3. 第三个数表示当 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。 对于每个测试点, 得分为以下三部分得分之和: 1. 如果第一问回答正确,你将获得 3 分。 2. 如果第二问回答正确,你将获得 4 分。 3. 如果第三问回答正确,你将获得 3 分。 **如果你仅仅知道部分答案,请也务必按此格式要求输出三个数。否则你可能会因格式错误无法得分。**