#2261. 「CTSC2017」密钥

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

一个密钥是一个长度为 n = 2k + 1 的字符串,它包含 1 个字母 X k 个字母 A k 个字母 B 。例如 k = 3 时, BAXABAB 就是一个密钥。
如下图所示,可以按顺时针顺序把这 2k+1 个字母排成一个圈:

BAXABAB

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 在哪个位置。
  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 ,意义如题所述。
第二行包含一个整数 \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 的位置。
  2. 第二个数表示当 k 元集合 P 代表 A 的位置且特征值为 S X 的位置。
  3. 第三个数表示当 k 元集合 P 代表 B 的位置且特征值为 S X 的位置。

样例

样例输入 1

5
3344
2

样例输出 1

10
1
2

样例解释 1

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

样例输入 2

500000
4545
234567

样例输出 2

999992
246922
753067

数据范围与提示

对于 30\% 的数据, k\leq 10^3
对于 50\% 的数据, k\leq 10^5
对于 100\% 的数据, k\leq 10^7

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

  1. 如果第一问回答正确,你将获得 3 分。
  2. 如果第二问回答正确,你将获得 4 分。
  3. 如果第三问回答正确,你将获得 3 分。

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