Game
Time limit1sMemory limit128 MB
Two players alternately add to S within a range set by the current parity, and whoever first reaches F loses, so decide if the first player can force a win.
- Level
Medium6 of 10
- Topics
- Game theory, Dynamic programming, Sliding window
- Solved
- No attempts yet
Problem
Hangi and Hyoseop are staff members preparing a contest. After working through the night they took a break and played a game. The rules are as follows.
First they fix positive integers , , and , where . One of the two starts, and after that they take turns building a number. On your turn, if the number the previous person made is odd, you choose an integer and add it to that number; if it is even, you choose an integer and add it. The player who starts adds a number to the initial value the same way. The first player to make a number greater than or equal to loses.
Given , , and , with Hangi starting first, write a program that decides whether Hangi has a winning strategy that always beats Hyoseop.
For example, if , , and , Hangi has no winning strategy. On the first turn Hangi may choose 1 or 2. If Hangi chooses 1 and makes , Hyoseop chooses 2 and makes 4, and then every number Hangi can make is at least 5, so Hangi loses the game. If Hangi chooses 2 and makes , Hyoseop chooses 1, and Hangi loses again.
Input
Input comes from standard input. The first line has the number of test cases . Each of the following lines has , , and of one test case in that order. and are integers with , and is an integer with .
Output
Print to standard output. For each test case, print YES on one line if Hangi has a winning strategy, and NO if there is none.