Rar the Cat and Mr. Panda have just bought a new board game! They eagerly tear up the plastic wrapping and search for the instructions and it was much longer than they expected.
Contents of package
- 1 small ball
- 4 6-sided dice
- 4 sets of D cards numbered 1 to D
- 1 tube divided into D sections for basic level
- 1 rectangular grid divided into D by D sections for intermediate level
- 1 cube divided into D by D by D sections for advanced level
This game is a strategy game that can be played with 2-4 players and can technically be played in any N-dimensional space but due to physical limitations, this board game only provides equipment sufficient for up to 3-dimensional gameplay. We categorise the games with basic level for 1 dimension, intermediate level for 2 dimension and advanced level for 3 dimensions. The game is broken down into various stages.
First, deal each player 1 set of D cards. For an N-dimensional game, each player then rolls a die N times and takes that number of cards from the set each time without replacement to get N hands. The hands are shown to all other players before the game starts.
Get another person to place the ball in any section of the tube/grid/cube and choose any of the corner sections as a goal point. The sections are separated by walls which can be completely opened or closed with a button at the side of the equipment. The game is turn-based. Each hand represents one axis and the numbers on each hand represent the movement in units on that axis. One each turn, the players in order must play 1 card from any hand. The board is then tilted so that the ball falls along the respective axis towards the goal and the walls are released to allow the ball to fall the respective number of units. The first person to make the ball fall out of the board is considered the loser. Refer to sample game below for clarification.
After analysing the lengthy instructions, the calculative Mr. Panda would like to beat Rar the Cat at this new game. Assuming both players play optimally and given the results of the preparation stage, you are to help Mr. Panda calculate the probability of him winning if he goes first or second. All sections and corners have equal probability of being chosen for the start and end points.
The first line of input contains 2 integers, N and D, separated by a space.
The next N lines of input contains an integer i followed by i integers representing the cards in each of Mr. Panda's hand respectively.
The next N lines of input contains an integer i followed by i integers representing the cards in each of Rar the Cat's hand respectively.
Output the probability of Mr. Panda winning if he starts first or second respectively on two separate lines, and give your answers to 2 decimal places.
For all subtasks, 1 ≤ i ≤ 6
Subtask 1(8%): N=1, 1 ≤ D ≤ 10
Subtask 2(12%): N=1, 1 ≤ D ≤ 100
Subtask 3(33%): N=2, 1 ≤ D ≤ 100
Subtask 4(47%): N=3, 1 ≤ D ≤ 100
Subtask 5(0%): Samples
Sample Input 1
2 2 3
Sample Output 1
The game is a 1-dimensional game on the tube of length 5. If Mr.Panda goes first, he will win if the ball is 1 or 2 units away from the goal since if it is 3 or 4 units away, Rar the Cat can force a win on the second move. Hence, he has a 2/5 chance of winning. If he goes second, he will win if the ball is 0, 1 or 4 units away by similar arguments. Hence, he has a 3/5 chance of winning. Therefore, he should choose to go second.
Sample Input 2
Sample Output 2