← 返回题目列表

Codeforces · 690/A3

A3. 集体心态(难)

中文机器翻译题面 查看原题

海蒂有脑子,竖起大拇指!但夜晚还没有结束,还有一个挑战等待着我们无畏的特工:晚餐后,午夜时分,N 名与会者喜欢玩一场非常危险的游戏……

每个僵尸的额头上都写着一个数字 ni (1 ≤ ni ≤ N)。虽然没有一个丧尸能看到自己的数字,但他却能看到所有N-1个家伙额头上写的数字。请注意,并非所有数字都必须是唯一的(它们甚至可以全部相同)。从此以后,僵尸之间就不能再有任何交流了。观察是成功的唯一关键。当布谷鸟钟敲响午夜时,所有与会者必须同时猜测自己额头上的数字。如果其中至少有一个猜对了他的数字,所有僵尸都会幸存并快乐地回家。另一方面,如果没有一个参加者能够猜对他的号码,那么所有人都注定要死!

不过,僵尸并不是非常聪明的生物,如果海蒂不想危及自己的生命,她就必须迅速采取行动。她只有一个选择:通过对她从胸部取出的大脑进行一些快速手术,她有能力远程重新编程所有参加者为即将到来的午夜比赛制定的决策策略!您能否向海蒂提出一个合理的策略,根据游戏规则,确保至少一名参与者能够正确猜出自己额头上任何可能的数字序列?

给定僵尸的等级 R 和其他参与者额头上的 N - 1 个数字 ni,您的程序将必须返回等级 R 的僵尸应猜测的数字。这些答案定义了您的策略,我们将检查它是否完美。

输入

输入的第一行包含一个整数 T (1 ≤ T ≤ 50000):您必须猜测的场景数量。

T 场景如下,每行描述两行:

- 第一行包含两个整数,N (2 ≤ N ≤ 6),即参加者的数量,以及 R (1 ≤ R ≤ N),即必须进行猜测的僵尸的等级。
- 第二行列出了N - 1个整数:所有其他参加者额头上的数字,按照参加者排名从小到大的顺序列出。 (每个僵尸都知道其他僵尸的等级。)

输出

对于每个场景,输出一个整数:R级僵尸根据其N-1个同伴额头上的数字ni猜测的数字。

示例

输入 #1

4
2 1
1
2 2
1
2 1
2
2 2
2

输出 #1

1
2
2
1

输入 #2

2
5 2
2 2 2 2
6 4
3 2 6 1 2

输出 #2

5
2

注意

例如,如果有 N = 2 两名与会者,则成功的策略可能是:

- 1级僵尸总是猜测他在2级僵尸额头上看到的数字。
- 2级僵尸总是猜测与他在1级僵尸额头上看到的数字相反的数字。