*Not an official ACM page*

[Problem F
| 1995 Western Europe problem set
| Ed's programming contest problem archive
| my home page]

### 1995-1996 ACM International Collegiate Programming Contest

Western European Regional

# Problem E

## Donkey

Long ago, a number of farmers wanted to sell their donkeys. These farmers lived in a small
village and the marketplace was in the capital. There was only one small road from the village
the farmers lived in to the capital, and one day the farmers left for the long journey towards the
capital. Every farmer wanted to travel as fast as possible to be the first to sell his donkey, but
there was one major problem: the donkeys were very stubborn; everytime a donkey reached a
river there was a chance that he would stay there for some time, not willing to cross the river.
However, two donkeys never rested at the same river.
The game 'Donkey' is derived from this legend: *N* players (numbered from 1..*N*) start with
their donkey in the village. Between the village and the capital are *M* rivers. The players take
turns in throwing a fair, 6-sided die and move their donkey the thrown number of rivers towards
the capital. Since only one donkey can rest at a river, the donkey is placed at the next free river
if necessary. After player 1 has thrown the die, it is player 2's turn, etc. After *N* comes 1. The
player that passes all rivers first wins the game.

This is an example of a 'Donkey' gameboard, where *N* = 2 and *M* = 6. Player 1's donkey is
located at river 4 and player 2's donkey is located at river 1.

Your task is to give the probability that player 1 wins the game, given a certain board position.

### Input Specification

The first line contains a single integer which equals the number of test cases that follow. Each of
the following lines contains one test case. The first integer on a line gives the number of rivers
*M*, the second integer gives the number of players *N* (1 <= *N* <= 4 and *N* × *M* <= 50). Then follow
*N* integers *P*_{i} (0 <= *P*_{i} <= *M*, 1 <= *i* <= *N*), representing the position of the *i*th player. The river
closest to the village has number 1, the river closest to the capital has number *M*. The village
has number 0. Two donkeys may not be positioned at the same river. However, more than one
donkey may be standing in the village. The last integer on the line gives the player, whose turn
it is.

### Output Specification

For every situation you have to print the following line, giving the game number (1 for the first,
2 for the second, ...) and the probability player 1 wins with an accuracy of 3 decimals:
Game *N*:the probability that player 1 wins = *D.DDD*

### Example Input

3
3 2 1 2 1
6 3 1 2 3 2
6 3 4 1 3 2

### Example Output

Game 1:the probability that player 1 wins = 0.667
Game 2:the probability that player 1 wins = 0.093
Game 3:the probability that player 1 wins = 0.366

This page maintained by
Ed Karrels.

Last updated January 3, 1998