奶牛们发明了一种名为 Herdle 的新型解谜游戏,在牛界引起了轰动。
每天都会有一个新谜题发布供奶牛解决。游戏采用 3x3 方阵的形式表示农场的一块田地,田地的每个方格都由特定品种的奶牛占据。总共只有 26 种可能的品种,每一种由 A 到 Z 中的不同大写字母标识。玩家不会被告知田地中的奶牛品种排列方式——游戏目标是通过一系列猜测确定它们。
每次猜测,奶牛们输入一个 3x3 的大写字母方阵,表示该田地可以用奶牛填充的可能方式。猜测的某些方格可能是正确的。这些方格以绿色高亮显示,让奶牛们知道这些是正确的。猜测的另一些方格可能填入了品种正确但位置错误的奶牛。这些以黄色高亮显示。
黄色高亮显示的方格的数量可以帮助指示某个品种的奶牛数量。 例如,假设猜测方阵包含 4 头品种 A 的奶牛,而答案方阵包含 2 只品种 A 的奶牛,其中没有正确位置上的 A (即,它们都不应该是绿色的)。 在这种情况下,猜测方阵中只有两个 A 应以黄色高亮显示。 更准确地说,如果猜测方阵中有 x 个特定品种的奶牛,并且 答案方阵中有 y<x 头该品种奶牛(不包括位置正确而得到绿色高亮显示的奶牛),那么猜测方阵的 x 头奶牛中只有 y 头奶牛应该以黄色高亮显示。
给定正确答案的方阵和一个表示对该答案的猜测的方阵,请计算绿色和黄色高亮显示的方格的数量。
输入格式(从终端 / 标准输入读入):
输入的前 3 行给定了正确答案的方阵。以下 3 行表示对该答案的猜测。
输出格式(输出至终端 / 标准输出):
输出两行。输出的第一行包含应当以绿色高亮显示的方格的数量。输出的第二行包含应当以黄色高亮显示的方格的数量。
输入样例:
COW SAY MOO WIN THE IOI
输出样例:
1 1
在这个例子中,最后一行中间的 O 是正确的,所以这个方格以绿色高亮显示。字母 W 位于错误的位置,所以它以黄色高亮显示。
输入样例:
AAA BBB CCC AYY AAA ZZZ
输出样例:
1 2
在这里,其中一个 A 位于正确的位置,所以它以绿色高亮显示。余下的 A 均不在正确位置上,由于答案方阵中有两个 A,所以有两个 A 应当以黄色高亮显示。
供题:Brian Dean,灵感来自应用 "Wordle"
为了消磨牛棚里的时光,奶牛们喜欢玩简单的骰子游戏。其中一种游戏使用两个骰子 X 和 Y 进行。两个骰子均被投掷,获胜的骰子是显示的数字较大的骰子。如果两者显示相同的数字,则重新投掷(只要持续打平,骰子可能会被重新投掷多次)。我们称骰子 X 击败骰子 Y,如果骰子 X 比骰子 Y 更有可能赢得这局游戏。
考虑以下的 4 面骰子:
骰子 A 在各面上有数字 4,5,6 和 7。
骰子 B 在各面上有数字 2,4,5 和 10。
骰子 C 在各面上有数字 1,4,8 和 9。
这些骰子满足一个相当奇妙的性质:A 击败 B,B 击败 C,并且 C 也击败 A。特别地,三个骰子都不是「最佳的」,可以击败其他两个。在这种情况下,当没有两个骰子打平,也没有一个骰子是最佳的,我们称这三个骰子的集合为「非传递的」。在非传递的三个骰子的集合中,每个骰子击败一个其他骰子,并输给另一个其他骰子。
给定两个 4 面骰子 A 和 B 各面上的数字,请帮助奶牛们求出是否有方法为第三个骰子 C 的各面分配数字,使得这个骰子的集合是非传递的。所有骰子面上的数字必须是 1 到 10 的整数。
输入格式(从终端 / 标准输入读入):
每个测试用例包含多个独立的子测试用例,必须全部回答正确才能通过整个测试用例。输入的第一行包含 T(1≤T≤10),为你需要求解的子测试用例的数量。
以下 T 行,每行描述了一个子测试用例,包含 8 个整数:骰子 A 的 4 面上的整数,以及骰子 B 的 4 面上的整数。所有的数均在 1 到 10 之间,不一定排序。可能同一个数会出现多次,即使在同一个骰子上也可能出现多个相同的数。
输出格式(输出至终端 / 标准输出):
输出 T 行。如果有可能为骰子 C 分配数字使得第 k 个测试用例成为一个非传递的骰子集合,则第 k 行输出 "yes",否则输出 "no"。
输入样例:
3 4 5 6 7 2 4 5 10 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2
输出样例:
yes no no
第一个子测试用例对应题目中的例子。在第二个子测试用例中,不存在骰子 C 可以使得这个骰子集合是非传递的。同理第三个子测试用例的答案也是 "no"。
供题:Brian Dean
Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思,Farmer John 想到了一个绝妙的主意,购买玉米来喂养他宝贵的奶牛。
FJ 的 N 头奶牛(1≤N≤10^5)排成一行,队伍中的第 ii 头奶牛的饥饿度为hi(0≤hi≤10^9)。由于奶牛是社会性动物,她们坚持一起进食,FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 i 和 i+1 并分别喂她们一袋玉米,令她们的饥饿度各减少 1。
FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。 请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数,或者如果不可能达到,输出 −1。
输入格式(从终端 / 标准输入读入):
每个测试用例包含多个独立的子测试用例,必须全部回答正确才能通过整个测试用例。输入的第一行包含 T(1≤T≤100),为你需要求解的子测试用例的数量。以下是 T 个子测试用例,每个子测试用例包含两行。第一行包含 N,第二行包含 h1,h2,…,hN。输入保证所有子测试用例的 N 之和不超过 10^5。每个子测试用例的 N 的值可能不同。
输出格式(输出至终端 / 标准输出):
输出 T 行,每个测试用例输出一行。
注意这个问题涉及到的整数可能需要使用 64 位整数型(例如,C 或 C++ 中的 "long long")。
输入样例:
5 3 8 10 5 6 4 6 4 4 6 4 3 0 1 0 2 1 2 3 10 9 9
输出样例:
14 16 -1 -1 -1
对于第一个子测试用例,给奶牛 2 和 3 各两袋玉米,然后给奶牛 1 和 2 各五袋玉米,可以使得所有奶牛的饥饿度均为 3。
对于第而个子测试用例,给奶牛 1 和 2 各两袋玉米,奶牛 2 和 3 各两袋玉米,奶牛 4 和 5 各两袋玉米,奶牛 5 和 6 各两袋玉米,可以使得所有奶牛的饥饿度均为 2。
对于余下的子测试用例,均不可能使得奶牛们的饥饿度相等。
测试点性质:
此外,测试点 3-5 和 9-11 中的 N 均为偶数,测试点 6-8 和 12-14 中的 N 均为奇数。
供题:Arpan Banerjee