넘치게 채우기

[Codeforces Round 996(Div.2)] - A. Two Frogs 본문

PS/Codeforces

[Codeforces Round 996(Div.2)] - A. Two Frogs

riveroverflow 2025. 1. 14. 11:29
728x90
반응형

https://codeforces.com/contest/2055/problem/A

Codeforces Round 996(Div.2) - A. Two Frogs

문제 유형: 구현, 수학, 그리디

시간 제한: 1초

메모리 제한: 256MB

 

문제

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 a1 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.

 

n개의 연잎이 한 줄로 있습니다. 1 ~ n까지 순차적으로 번호가 있습니다. 두 마리의 개구리 Alice와 Bob은 서로 다른 연잎 a, b위에 있습니다.

Alice부터 점프를 하고, Bob이 점프를 번갈아가면서 합니다.

턴에서, a에 있을 시, a-1이나 a+1로 점프할 수 있고, 범위를 벗어날 수 없습니다. 다른 개구리가 이미 있는곳에는 점프할 수 없습니다.

각자의 플레이어가 최적의 움직임을 한다는 가정하게, Alice가 이기는 경우인지 판단하시오.

유효한 이동할 수 있는 곳이 없다면, 게임에서 지는 것입니다.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1t500). The description of the test cases follows.

The first and only line of each test case contains three integers n, a, and b (2n100, 1a,bn, ab) — 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가 주어집니다. n은 연잎의 개수, a와 b는 각각 Alice와 Bob의 위치입니다.( 2 <= n <= 100, 1 <= a, b <= n, a!= b)

 

 

출력

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.

 

Alice가 이길 수 있는지를 "YES" 또는 "NO"로 출력하시오.

출력에는 대소문자를 구분하지 않고 채점됩니다.

 

풀이

만약 a, b가 붙어있는 경우라면, Alice는 뒤로 갈수밖에 없다. 즉, 다음 턴에 Bob은 Alice방향으로 움직여서 계속 압박하고, 결국 Alice가 진다.

만약 a와 b 사이에 한 칸의 여유가 있다면, Alice가 먼저 Bob쪽으로 가서 위의 상황에 대해 반대로 압박할 수 있다.

 

즉, 거리의 차이가 홀수라면, 아무리 Alice가 게임을 잘 해도, Bob을 이길 수 없다.

Bob은 a, b가 붙어있는 상태로 시작하는 그림을 만들 수 있고, 상대방도 최적의 플레이를 하는게 보장되기 때문이다.

거리의 차이가 짝수라면, 반대로 Alice는 계속 Bob에게 압박을 줄 수 있다. Bob은 결국 후퇴만 하게되는 턴이 찾아오게 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n, a, b;
  cin >> n >> a >> b;

  if (abs(a - b) % 2 == 1)
    cout << "NO\n";
  else
    cout << "YES\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}
728x90
반응형