아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

카르텔 님 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약
A, B, C가 돌을 순서대로 가져가되 A와 B는 1 이상 K/2 이하, C는 1 이상 K 이하를 가져갈 수 있을 때 최선의 플레이에서 이기는 쪽을 판정한다.
난이도

보통10점 중 6점

유형
게임 이론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

A, B, C는 님 게임을 하기로 했다. 님 게임에서는 NN개의 돌이 주어지고 각 사람이 차례대로 턴을 번갈아 가며 게임을 진행한다. 자신의 턴이 되면 1 이상 KK 이하의 정수 중 원하는 정수를 골라 그만큼의 돌을 가져갈 수 있다. 마지막 돌을 가져가는 사람이 승리한다.

세 명은 A, B, C 순서대로 게임을 진행한다.

C는 워낙 게임을 잘하기 때문에, A, B는 둘이 팀을 맺고 C를 상대하기로 했다. 즉 A와 B 중 누가 이기더라도 둘은 동시에 이긴다. 하지만 이렇게 게임을 해 본 결과, C가 매우 불리하다는 사실을 알 수 있었다.

따라서 규칙을 바꿔 A와 B는 각각 1 이상 K2K\over2 이하의 정수만을 골라 돌을 가져갈 수 있도록 규칙을 수정하였다. 각 플레이어들이 모두 최선의 전략으로 플레이하였을 때, 어느 팀이 이길지 출력하자.

입력

입력은 다음과 같이 주어진다.

NN KK

첫째 줄에 돌의 개수 NN, 한 턴에 C가 가져갈 수 있는 돌의 개수 KK가 공백을 사이에 두고 입력으로 주어진다.

출력

A와 B가 이긴다면 A and B win을, 아니라면 C win을 출력한다.

제한

  • 2≤K≤N≤1,000,0002 \leq K \leq N \leq 1\\,000\\,000
  • KK는 짝수이다.

예제2

  1. 예제 1

    입력
    10 8
    
    예상 출력
    C win
    
  2. 예제 2

    입력
    12 8
    
    예상 출력
    A and B win