CF2055A.Two Frogs
入门
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Roaming through the alligator-infested Everglades, Florida Man encounters a most peculiar showdown.
There are n lilypads arranged in a row, numbered from 1 to n from left to right. Alice and Bob are frogs initially positioned on distinct lilypads, a and b, respectively. They take turns jumping, starting with Alice.
During a frog's turn, it can jump either one space to the left or one space to the right, as long as the destination lilypad exists. For example, on Alice's first turn, she can jump to either lilypad a−1 or a+1, provided these lilypads are within bounds. It is important to note that each frog must jump during its turn and cannot remain on the same lilypad.
However, there are some restrictions:
- The two frogs cannot occupy the same lilypad. This means that Alice cannot jump to a lilypad that Bob is currently occupying, and vice versa.
- If a frog cannot make a valid jump on its turn, it loses the game. As a result, the other frog wins.
Determine whether Alice can guarantee a win, assuming that both players play optimally. It can be proven that the game will end after a finite number of moves if both players play optimally.
佛罗里达州男子在遍布鳄鱼的佛罗里达大沼泽地(Everglades)中穿行时,遭遇了一场极为奇特的对决。
一排共 n 片睡莲叶,从左到右依次编号为 1 到 n。青蛙爱丽丝(Alice)和鲍勃(Bob)初始时分别位于不同的睡莲叶上,位置分别为 a 和 b。他们轮流跳跃,爱丽丝先手。
在某只青蛙的回合中,它可向左或向右跳一格,前提是目标睡莲叶存在。例如,在爱丽丝的第一回合中,只要 a−1 或 a+1 在有效范围内(即介于 1 与 n 之间),她便可跳至对应睡莲叶上。需特别注意:每只青蛙在自己的回合中必须跳跃,不可停留在原地。
然而,游戏存在如下限制:
- 两只青蛙不得占据同一片睡莲叶。这意味着爱丽丝不可跳至鲍勃当前所在的位置,反之亦然。
- 若某只青蛙在其回合中无法执行任何合法跳跃,则该青蛙判负,另一只青蛙获胜。
假设双方均以最优策略进行游戏,请判断爱丽丝是否能必胜。可以证明:若双方均采用最优策略,游戏将在有限步内结束。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤500). The description of the test cases follows.
The first and only line of each test case contains three integers n, a, and b (2≤n≤100, 1≤a,b≤n, a=b) — the number of lilypads, and the starting positions of Alice and Bob, respectively.
Note that there are no constraints on the sum of n over all test cases.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤500)。随后是各测试用例的描述。
每个测试用例仅有一行,包含三个整数 n、a 和 b(2≤n≤100,1≤a,b≤n,且 a=b)——分别表示莲叶的数量,以及爱丽丝和鲍勃的起始位置。
注意:所有测试用例的 n 值之和没有额外限制。
输出格式
For each test case, print a single line containing either "YES" or "NO", representing whether or not Alice has a winning strategy.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
对于每个测试用例,输出一行,包含“YES”或“NO”,表示 Alice 是否存在必胜策略。
你可以以任意大小写形式输出答案(大写或小写均可)。例如,字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。
输入输出样例
输入#1
5 2 1 2 3 3 1 4 2 3 5 2 4 7 6 2
输出#1
NO YES NO YES YES
说明/提示
In the first test case, Alice has no legal moves. Therefore, Alice loses on the first turn.
In the second test case, Alice can only move to lilypad 2. Then, Bob has no legal moves. Therefore, Alice has a winning strategy in this case.
In the third test case, Alice can only move to lilypad 1. Then, Bob can move to lilypad 2. Alice is no longer able to move and loses, giving Bob the win. It can be shown that Bob can always win regardless of Alice's moves; hence, Alice does not have a winning strategy.
在第一个测试用例中,Alice 没有合法的移动。因此,Alice 在第一回合即告失败。
在第二个测试用例中,Alice 只能移动到荷叶 2。随后,Bob 没有合法的移动。因此,Alice 在此情况下拥有必胜策略。
在第三个测试用例中,Alice 只能移动到荷叶 1。接着,Bob 可以移动到荷叶 2。此时 Alice 无法再进行任何移动,从而失败,Bob 获胜。可以证明,无论 Alice 如何行动,Bob 总能获胜;因此,Alice 并不拥有必胜策略。
输入解题思路,AI测评打分。不知道怎么写?