Non-Transitive Dice

题目描述

为了在牛棚里打发时间，奶牛们喜欢玩一些简单的掷骰子游戏。其中一个游戏使用两个骰子 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。特别地，三者中没有任何一个是“最优”的（能战胜另外两个）。在这种情况下，当任意两枚骰子都不会打平，且不存在单个骰子是最优时，我们称这组三个骰子为“非传递（non-transitive）”。在一个由三个骰子组成的非传递集合中，每个骰子都会战胜其中一个骰子，并输给另一个骰子。 给定两个 4 面骰子 A 和 B 的各面点数，请帮助奶牛们判断：是否存在一种方式为第三个骰子 C 的四个面赋值，使得这组三个骰子构成非传递集合。所有骰子面上的数字必须是 1 到 10（含）之间的整数。

输入格式

每个输入由若干相互独立的测试用例组成，必须全部正确解决才能通过整个输入。输入第一行包含 $T$（$1\le T\le 10$），表示测试用例数量。 接下来的 $T$ 行每行描述一个测试用例，共 8 个数字：骰子 A 的四个面的数字，以及骰子 B 的四个面的数字。 所有数字都在 1 到 10 之间，不一定按顺序给出。同一个数字可能出现多次，甚至可能在同一个骰子上重复出现。

输出格式

请输出 $T$ 行。第 $k$ 行如果可以设计出一个骰子 C 使得第 $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

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze