# 一道简单的博弈论问题 (II play with GG)

3月 12, 2019 - 算法

## 题目描述

IG won the S championship and many people are excited, ii and gg are no exception. After watching the game, the two of them also want to play a game.
There is now an infinite chessboard with only one piece. Initially the pieces are placed at the (x, y) position (the board coordinates are counted from 0). They took turns to move the pieces. ii moves first.
There are three ways to move
1. Move the piece to the left by one space (from (x, y) to (x-1, y)).
2. Move the piece down one space (from (x, y) to (x, y-1)).
3. Move the piece to the lower left by one space (from (x, y) to (x-1, y-1)).

It should be noted that the pieces cannot be removed from the board.
The first person who can not operate is judged negative (in other words, the first person who moves the piece to (0,0) wins).
Now give the initial coordinates x, y of the piece. Under the premise that both take the optimal strategy, please output the name of the winner (ii or gg).

## Input

The input contains only one line. Enter two integers x y to represent the initial coordinates of the piece. $(0 \leq x, y \leq 1000)$。

## Output

the winner’s name (ii or gg)。

1 1
124 654

ii
gg

## 题目分析

1. 考虑最简单的情况，如果初始状态下棋子放在(0,0)，那么对于ii而言，游戏开局时就没有可以移动的方式，于是gg自动获胜。也就是说，在(0,0)时，先手必败。
2. 有了上一种情况的例子，我们很轻松的可以得到，如果先手方可以把棋子移到(0,0)，那么后手方无法继续移动棋子，先手就能获得胜利。也就是说(0,1),(1,1),(1,0)这三种情况下，先手必胜。
3. 接下来我们考虑一条线，也就是说当初始状态下棋子在(x,0)或者在(0,x)的位置时的情况，由于规则的限制，移动只限制在向(0,x-1)和(x-1,0)位置进行，我们可以轻松的推出，当x为奇数时，先手必胜，x为偶数时，后手必胜。
4. 继续深入讨论，如果处于(1,x)的状态下，此时先手可以通过移动到(0,x)或(0,x-1)的位置来确保状态转移成(0,偶数)的情况，由于先手在下一次操作中相当于后手，也就是说先手可以确保自己这一次操作后达到后手必胜的结局，从而获得游戏的胜利。
5. 由上述分析我们可以得到，不管是对于谁在操作，都会极力避免通过自己的操作使得局面变成(1,x)或者(x,1)的局面，因此问题抽象成两条线上的问题，要么一直向左，要么一直向下，也就是说，再由之前的结论，我们可以总结得到最后的结果，当(x,y)均为偶数时，后手必胜，在其他情况下，先手必胜。