UVA - 12163 Addition-Subtraction Game (博弈)

Description

You and your friend are playing a 2 player game. The game is played in a graph ofV vertices. The vertices are numbered from0 toV-1. The graph has some directed edges. But the graph does not contain any cycles or loops. The rule of the game is as follows.

1.      Initially vertex i has a positive value value_i

2.      Both players make their moves by turns. In his turn the player chooses a vertex with the following properties.

・         The value of the vertex is strictly positive.

・         The vertex has one or more outgoing edges.

If there is no such vertex the player loses and the game terminates.

3.      If the player can select a vertex the player will decrease the value of the selected vertexi by1. Then from the set of vertices which have an incoming edge from vertexi, the player will selectK_i (this value will be given as input) vertices and increase the value of those vertices by1.  Among these selectedK_i vertices there can be duplicated vertices. And if a vertex is selectedn times its value will be increased by1 every time. Or in another word its value will be increased byn. For example if theK_i=6 and the selected vertex set is{2,2,2,3,3,5} thenvalue₂ will be increased by3, value₃ will be increased by 2 and value₅ will be increased by1.

Now consider the graph on the right.

Let the values of K be {2,1,3,2}.

Now the value set {0,0,0,5} is a losing terminating position because the player cannot select any vertex which have outgoing edges and positive values.

For the value set {3,4,5,6} the current player can go to the following value states by1 move.

・         {2,5,6,6}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠