2023 Xiangtan Unversity Freshman Conteset
A. 签到啦 
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

今天是小A进入大学的第一天，第一天的事情当然就是签到啦 

根据入学手册他要先带着行李进行签到然后最后到达寝室。

他携带了 w 个的行李，要前往 n 个地点进行签到，第 i 个地点热情的学长学姐（其中一个）会帮小A运送 ai 个的行李去寝室，小A不想麻烦太多的人帮他，同时他准备请所有帮他运行李的学长学姐喝杯奶茶。

那么在他可以安排签到点顺序的情况下，你可以帮帮他计算一下他最少要准备多少杯奶茶来答谢帮助过他的人吗。

Input

第一行 整数 T 表示所有样例的个数

接下来的 2 * T 行，每两行的第一行两个整数n, w,第二行是n 个整数 a1, a2, ...an

数据保证

Output

输出 T 行，每行一个整数，表示小A最少要准备的奶茶数量

Example
Input
3
5 100
20 30 31 15 50
3 10
5 6 4
7 32
12 14 9 8 3 5 17
Output
3
2
3

B. 熙巨打票
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

众所周知，熙巨最近参加的 icpc-ec-final，回到长沙的时候，需要报销车费凭证，火车站只有两台机器。

长沙火车站报销机

但是由于机器非常卡顿，每次只能导出1张凭证，并且在每导出一张后需要冷却 a, a ≤ 100 分钟，熙巨每次操作需要 b ≤ 100 分钟，并且同一时刻只能在一个机器上进行操作。由于熙巨有 n, n ≤ 109 张车票需要打，熙巨不想浪费时间，他想知道，最少打完票需要多长时间。

Input

第一行一个整数 T，表示测试样例数量

接下来 T 行，每行三个整数 a, b, n。

数据保证 0 ≤ a ≤ 100, 1 ≤ b ≤ 100, 1 ≤ n ≤ 109, T ≤ 105

Output

输出 T 行，每行一个正整数，表示最小需要的时间。

Example
Input
4
10 4 10
5 5 15
7 8 1
1 3 12
Output
64
75
8
36

C. 三元分配
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Ricardoly正在面对一个大难题，他手下有三个部门，每个部门都有一定数量的员工。出于某种原因，他需要将他手下的所有员工都两两配对，已知处于同一部门的两个员工之间可以配对；对于不同部门的两个员工，如果这两个员工所在的部门的员工数量之和为质数，那么他们两个也可以配对。注意配对并不会减少部门员工。

Paranoid觉得Ricardoly想不出到底能不能将他的所有员工都进行配对，并对他进行了无耻的嘲笑。Ricardoly受不了这个气，于是他向你求助。

Input

第一行为样例数T(1 ≤ T ≤ 200000)

接下来T行，每行有三个整数A, B, C(0 ≤ A, B, C ≤ 100000)，分别代表三个部门的人数。

Output

每行输出一个结果，对于每个样例，如果能够将所有员工都进行配对，则输出一个字符 R

否则输出一个字符 P

Example
Input
2
2 4 6
2 4 5
Output
R
P

D. "逆"天求和
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

董事长最近学了"逆元"，他现在来问你，对于每一个质数 p 来讲，我们假设 f(x) 是 x 的逆元，那么 等于多少。

如果你不理解上述式子的意思，那么可以表述为，从 1 到 p - 1 的所有整数的逆元的和

逆元定义如下：

对于一个数 p ，我们在此题中，仅仅考虑 p 是质数。

若对于一个整数 a ，存在一个 0 到 p - 1 的整数 b，使得 ,也就是 a、b 的乘积对 p 取模等于 1。那么我们说 a, b 在模 p 情况下互为逆元。

你看了一眼，不太会。但是你感觉这是一个数学题，于是你去问了胡老板，胡老板撇了一眼，一脸不屑的说："这也算数学题，我给你一句提示，你自己领悟吧"

胡老板说的是：在模 p 情况下，对于每一个不为 0 的整数 a，存在唯一一个整数 ,他们互为逆元。

一共有T组询问 数据范围：q ≤ 100000，T ≤ 9592

Input

第一行一个正整数T，表示一共有T次询问 对于每次询问，每行一个正质数p

Output

每次询问输出一个正整数，表示从1到p - 1中的每个数在模p意义下的逆元的和

Example
Input
2
5
99991
Output
10
4999050045

E. 读中国数字
time limit per test
1 second
memory limit per test
16 megabytes
input
standard input
output
standard output

众所周知，中国的数字计数法有自己的一套读法：

中文读数法

例如：12003，读作壹万贰仟零叁；1200003，读作 壹佰贰拾万零叁。

注意：对于十，我们统一读作壹拾，在各级中均这样读，如果某一级都是 0，我们默认不读。

给定一个数字 n ，n ≤ 9 × 1011，你需要输出它的中文读法。

为了方便比对答案，我们约定中文全角字符由以下英文半角字符代替：

中文替代字符中文替代字符
零0玖9
壹1拾T
贰2佰B
叁3仟K
肆4万W
伍5亿Y
陆6捌8
柒7
Input

第一行个整数 T ，代表输入数据的组数。T ≤ 105

接下来 T 行，每行一个整数 n，n ≤ 9 × 1011

Output

输出 T 行，每行一个字符串，表示大写读法。

Example
Input
6
0
10
102
70308432
12003
900000000000
Output
0
1T
1B02
7K03TW8K4B3T2
1W2K03
9KY

F. 您有一封新邮件待接收
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

WahAHa 是个阳光开朗大女孩，她每天都会和一群和她一样活泼的朋友写信。买信纸、写信、盖邮戳......成了她每天的必做的事。

为了让朋友间的联系更加紧密，她们有时会通过朋友的朋友来传达信件，但她们从来都不会在信件上署名，也不会在信件上写上收件人的名字。因此，为了能确保信件顺利抵达，每个收到信件的朋友都不得不将信件抄送以后发给自己所有的朋友。

但这样做可能会带来麻烦，例如，WahAHa 给她的朋友 Bob 发了一条消息，收到信的Bob 将这封信发给自己的朋友Alice，而Alice 在收到这封信后又会将这封信发给自己的朋友WahAHa。以此无限循环下去......

有一天，WahAHa 所在的湘潭大学升到了 "双一流"，她十分高兴，于是将这个消息以邮件的方式发给了她所有的朋友，但是由于这个存在缺陷的规则，有的人会收到无限封邮件，你需要告诉 WahAHa，哪些人（或许包括她自己）可能会收到无限封邮件。

Input

第一行为一个整数T（1<=T<=1000），表示样例个数。

对于每个样例而言，第一行为两个整数 n, m(1 ≤ m ≤ n ≤ 100)，表示总人数和最初的发件人。 由于网络邮件可以取昵称，因此 WahAHa 的网名可以是别的名称，在这里我们认为是第 m 个名称是 WahAHa 本人。

随后一行包括n个字符串，其中第i个字符串 Si(|S| <  = 50) 表示第i个人的名字。

随后第i行的第一个数为 k(0 <  = k <  = n) ，随后 k 个数 Dij(1 <  = Dij <  = n) 表示第i个人知道第 Dij 个人的地址。

Output

对于每个每个样例而言，第一行为受影响人数，随后一行按输入顺序给出人名，人名之间用一个空格隔开。如果没有人会烦恼，则输出"No one is disturbed!"。

Example
Input
3
3 1
WahAHa Alice Bob
1 2
1 3
1 1
3 1
Alice WahAHa Bob
2 2 3
0
0
6 3
Ross Julie WahAHa Linda Arup Niki
2 3 5
0
1 4
1 1
1 2
2 5 4
Output
3
WahAHa Alice Bob 
No one is disturbed!
5
Ross Julie WahAHa Linda Arup

G. 空气扑克
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

在众多赌郎的见证下，噬谎者莫和idea首领拉罗，开始了命中注定的赌局:《空气扑克》。

赌局为2V2赛制，分别为莫对决拉罗，以及蜂名直器对决枭，其中莫与蜂名直器之间互为搭档，拉罗和枭互为搭档。

初始时，莫和拉罗每人手上会手持若干张标有数字的手牌。而蜂名直器和枭则是共享一副去掉了大小王的扑克。

每回合开始，莫和拉罗都需要从手牌中选出一张打出,我们令莫的出牌为M,拉罗的出牌为L。

接着蜂名直器会被赌郎告知M的大小，同样的枭会被告知L的大小。

接下来蜂名直器和枭要从剩余的扑克牌中选取5张牌作为自己所选的牌组，且要满足牌组的点数大小之和要刚好等于他们被告知的搭档所出的手牌大小，即蜂名直器凑出的牌组点数之和要为M，而枭则是要为L。扑克牌对应的点数范围为[1, 13]，分别对应各个花色的 {A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K}。

例如如枭被告知L是45，且场上的四种花色的T和某一种花色的5都还可用的情况下，枭便可用这5张牌来组成此回合的牌组。

同一回合内蜂名直器和枭每张扑克只能选一次，但是两人可以选择同一张扑克来凑成自己当回合的牌组，且在回合结束后，他们此回合所选的扑克将会被丢弃，不能作为下回合的选牌。所以每回合开始时的可选扑克牌不一定完整。

牌型大小的规则与德州扑克一致:一副牌组包含 5 张扑克牌，他们可能会形成若干种牌型，按照从大到小的顺序依次为：

皇家同花顺：相同花色的{T, J, Q, K, A}

同花顺：花色相同的顺子（顺子的定义见下方），例如同花色的 {9, J, Q, K, A}。

四条：存在四张大小相同的牌，例如任意花色的 {T, T, T, T, 2}。

葫芦：有三张牌大小相同，另外两张牌大小相同，例如任意花色的 {T, T, T, J, J}。

同花：五张牌花色相同，例如同花色的 {7, J, Q, K, A}。

顺子：五张牌大小连续，例如任意花色的 {2, 3, 4, 5, 6},或者{T, J, Q, K, A}。特殊地，{A, 2, 3, 4, 5} 也是一个顺子（但是 {K, A, 2, 3, 4} 不是）。因此一共有 10 种不同数值的顺子，它们的第一张牌分别是 {A, 2, 3, 4, 5, 6, 7, 8, 9, T}

三条：存在三张大小相同的牌，例如任意花色的 {T, T, T, J, Q}。

两对：存在两个大小不同的对子（一个对子是两张大小一样的牌），例如任意花色的 {T, T, Q, Q, K}。

对子：存在两张大小相同的牌，例如任意花色的 {T, T, J, Q, K}。

高牌：不满足以上任何一个牌型的手牌都是高牌。

一副牌组可能同时满足很多个不同的牌型，这个时候我们会把最大的那个牌型作为这幅牌组的牌型。 请注意在此题中同牌型之间认定为一样大，而不是继续做牌面字典序或者花色的比较。

特殊的，如果蜂名直器或者枭在得知此回合的M或者L后，在此回合剩余的扑克牌中，无法凑出任何牌组，则视为高牌

在进行了若干个回合之后，莫通过摩斯密码将自己和拉罗当前的所有手牌(而不是本回合决定出的牌)告知了蜂名直器，并询问他自己在这一回合之内是否能ALLIN。莫能够ALLIN，当且仅当莫这一回合存在一种出牌方案使得无论拉罗出哪张手牌，自己打出某张手牌后都能够获胜，而不是平局或者失败。

但是现在蜂名直器又陷入了间歇性失忆，所以只好由你来代替他来回答莫询问的结果

Input

第一行一个整数 T(1 ≤ T ≤ 200)，表示数据组数，接下来T组样例

每组测试数据的第一行是：一个数字n(1 ≤ n ≤ 5)，代表莫和拉罗剩余的手牌数

接下来两行每行都有n个整数Ai(6 ≤ Ai ≤ 64)，第一行为莫的手牌情况，第二行为拉罗的手牌情况

接着输入一个4 × 13的01矩阵d，代表当前剩余的扑克牌情况，dij代表花色为i,牌面为j的牌是否可用，如果为1则可用，否则不可用

四行矩阵从上到下对于的颜色分别为 黑桃 红心 方块 梅花。

Output

每组样例分别输出一行结果，如果能够满足题意中ALLIN的情况，则输出YES，否则输出NO

Example
Input
2
5
25 45 26 36 39
47 15 8 64 44
1111111111111
0111111110000
0111111110000
0111111110000
1
6
25
1100101010101
1010110100100
1001001011010
1010101010100
Output
NO
YES
Note

在第一组样例中，因为黑桃的A, K, Q, J, 10都在，所以拉罗只要该回合出手牌47，枭这局可以顺利的凑出皇家同花顺，而无论莫这回合出什么手牌，蜂名直器都无法凑出一副牌组来比赢皇家同花顺，故不能ALLLIN，输出NO

在第二组样例中，因为只有一张手牌，故莫只能打出6，而四种花色的A都还在场上，故蜂名直器可以用其来凑出A, A, A, A, 2的四条；同样的，拉罗只能出25，而枭在此限制下用场上剩余的扑克能凑出的最大的一种牌组是A, A, A, J, J的葫芦，故只要莫打出6，拉罗无论出什么都能取胜，输出YES

H. 我爱XTU
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定长度为 n 的，由 XTU 三个字符构成的字符串 S，现请你输出 S 中满足三种字符数量相同的子串的数量

Input

第一行一个整数 T(1 ≤ T ≤ 100)，表示数据组数

接下来 T 行，每行为一个仅由字符 X、T、U 组成的字符串 S

数据保证字符串长度 len(S) ≤ 104

Output

输出 T 行，每行一个整数，表示合法子串的数量

Example
Input
2
XXTUUTXTU
UTUXXTTUXUXX
Output
6
8

I. 小黑的鸡脚plus
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

题目背景同小黑的鸡脚。

给定长度为 n 的 01串 S，你可以将不超过 k 个 0 变为 1，请问最多可以取出多少个不相交的 完美d串。

完美d串 指长度为 d ，并且全为1的连续串。例如，完美3串就是指 111，完美5串指 11111。

Input

第一行一个整数 T。表示测试数据组数。

接下来 T 行，每行包含2个整数k, d，以及一个01字符串 S。

数据保证 0 ≤ k ≤ 100, 1 ≤ d ≤ 50, len(S) ≤ 2000, T ≤ 150

Output

输出 T 行，每行一个整数，代表可以取出最多的完美 d 串的数量。

Example
Input
3
0 3 11101111
1 4 10111111
2 4 10111101
Output
2
2
2

J. 组队
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

ACM-ICPC是一个大型网络组队游戏，最近出了一个ICPC-puls游戏，每个队伍可以大于一个人，没有上限。完成一个组队需要满足一些要求：

1. 比赛共有 p 个知识点，一个队伍应该了解每个知识点。

2. 由于一些知识点每个人的理解可能不同，因此对于某个知识点，队伍中不应该有两个人及以上的人了解。

教练知道每个队员的知识点学习情况，他想知道，如果组成一个队伍，有多少种组队方法。

两种组队方法A，B 不同，当且仅当，有一个人出现在 A 中但不出现在 B。（同集合的比对方法）

在校队中共有 n 个人。 n ≤ 42

第 i 队员掌握共有 ai 种知识点，0 ≤ ai ≤ p

知识点数量 p ≤ 60

Input

第一行输入整数 T, T ≤ 200 ，表示输入测试组数。

对于每一组测试数据，由以下格式输入：

第一行输入两个整数 n, p

接下来 n 行，每行第一个整数 ai ，表示他掌握的知识点数量，接下来 ai 个数，表示第 i 个人掌握的知识点，知识点标号从 1 到 p。

Output

输出 T 行，每行一个整数，表示组队可能的方案数量。

Example
Input
1
6 6
2 1 2
2 3 4
2 5 6
2 1 3
2 2 4
2 5 6
Output
4
Note

样例1：{1, 2, 3},{1, 2, 6},{4, 5, 6},{3, 4, 5}共计4种组队方式