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}

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈