두 토큰이 1번 칸에서 시작해 Lora와 Bobi가 번갈아 앞으로 이동하며, 같은 칸에 오면 상대를 K칸 뒤로 밀어낸다. 최선의 플레이에서 승자 또는 무승부를 판정한다.
어려움8게임 이론시뮬레이션동적 계획법수학아직 제출이 없습니다시간 제한2초메모리 제한512 MBWhenever the weather outside is bad, Lora and Bobi enjoy playing board games together. One of their favorite games is the board game Activity – in this task we will describe a generalization of the game.
The game consists of a strip divided in N spaces numbered from 1 to N. Each of the two players (Lora and Bobi) has a token that is initially placed on the space numbered 1. The players take turns to move their own token forwards. In a single turn the rules are as follows:
Note that each player must make a move on their turn and cannot “pass”. The winner is the player whose token ends up on space number N first. As a lady, Lora gets to make the first move.
A single game can be fully described by the quadruple (N, L, B, K). Now Lora and Bobi are wondering who would win if they both play optimally given different parameters for the game. It is possible that with optimal strategy from both players a game continues forever. In such case we consider the game to be a draw.
On the first line of the standard input is a single integer T – the number of games that your program should process.
Each of the next T lines contains 4 space-separated integers – N, L, B and K – respectively the amount of spaces in the game, Lora’s maximum move, Bobi’s maximum move and the number of spaces that one gets pushed back when the two tokens end up on the same space.
For every game output on a separate line the result of the game with the given parameters assuming that both players play optimally. The possibilities are: