2002년 가을학기 문제해결기법 - 문제 8

게임

한기와 효섭은 프로그래밍 대회를 준비하는 스탭들이다. 이들은 대회 준비를 위하여 밤을 새워가며 일을 하다가 휴식 시간에 게임을 하게 되었다. 게임의 규칙은 다음과 같다. 먼저 세 양의 정수 S, F와 K를 정한다. 여기서 S<F이다. 그리고 나서 한기와 효섭 둘 중 한 명이 게임을 시작하여 서로 번갈아 가며 수를 다음과 같이 만들어 간다. 각각은 앞 사람이 만든 수가 홀수라면 이 수에 어떤 정수 P (1≤P≤K)를 선택하여 더하고, 짝수라면 이 수에 어떤 정수 P (2≤P≤K+1)를 선택하여 더한다. 게임을 시작하는 사람은 초기값인 S에 위와 같은 방법으로 수를 만든다. 두 사람 중 처음으로 F 이상의 수를 만드는 사람이 게임에서 지게 된다. S와 F, 그리고 K가 주어지고 한기가 게임을 먼저 시작할 때, 한기가 효섭에게 반드시 이길 수 있는 필승 전략이 존재하는지를 결정하는 프로그램을 작성하시오.

예를 들어 S=1, F=5이고, K=2라면 한기의 필승 전략이 존재하지 않는다. 그 이유는 다음과 같다. 처음에 한기가 선택할 수 있는 수는 1 혹은 2 이다. 만약 한기가 1 을 선택하면 한기가 만든 수는 S+1=2가 된다. 이때 효섭이 2를 선택하여 4를 만들면 한기는 5 이상을 만들게 되어 게임에 지게 된다. 만약 한기가 2를 선택하여 S+2=3를 만들면 효섭은 1을 선택하여 결국 한기가 게임에 지게 된다. 그러므로 한기의 필승 전략이 존재하지 않는다.

프로그램 이름과 설명 파일 이름은 각각 game.xxx, game.yyy라고 하고 실행 파일 이름은 game.exe로 한다. 프로그램의 실행 시간은 2초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 입력은 T(1≤T≤10)개의 테스트 케이스로 이루어진다. 테스트 케이스의 수 T가 첫 번째 줄에 주어진다. 각 테스트 케이스는 한 줄에 S, F, K의 값이 순서대로 주어진다. S와 F는 1≤S<F≤10,000인 정수이고, K는 1≤K≤1,000인 정수이다. 입력되는 정수들 사이에는 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 각 테스트 케이스에 대해서 한기가 승리하는 필승 전략이 존재한다면 YES를, 존재하지 않는다면 NO를 한 줄에 출력한다.

입력과 출력의 예

INPUT.TXT

5

1 5 2

2 7 3

1 7 3

2 8 2

5 13 3

OUTPUT.TXT

NO

YES

NO

NO

YES