Energy Battle Strategy

This problem is based on a two‐player turn‐based game. Both players have an energy reserve which can store at most \(n\) points of energy. In addition to a special ultimate skill (大技能) that can only be used when the energy is full (i.e. when energy equals \(n\)) and which, when used, consumes all energy, there are \(m\) small skills. The small skills are divided into three types:

• Consumption type: requires \(x\) points of energy to use and can only be used if the current energy is at least \(x\).
• Free type: does not consume energy and can be used at any time.
• Supply type: when used, increases your energy by \(x\) (any energy in excess of \(n\) is wasted).

Furthermore, some of the small skills have counter relationships. There are several relations of the form "small skill \(i\) beats small skill \(j\)". The ultimate skill beats every small skill. (No other pair of skills has any interaction.)

The game proceeds in rounds. In each round, both players must choose one skill that is legal in the current state. They reveal their choices simultaneously. If one player’s selected skill beats the other’s, then the game ends immediately and the winning player is declared. Otherwise, both players update their energy reserves according to the used skills and a new round begins. In the event that both players use their ultimate skill simultaneously, both will have their energies reset and the game will continue. If the game never terminates, then each player is considered to have won \(0.5\) of a game.

Players are assumed to use randomized strategies which depend only on the current state defined by the two players' energy levels (ranging from \(0\) to \(n\)). That is, for each state \((i,j)\) the strategy table gives a probability distribution over the available skills. There are a total of \(m+1\) skills (the ultimate skill plus \(m\) small skills). Note that a skill can only be chosen if it is available (for example, the ultimate skill is only available when energy equals \(n\) and a consumption‐type small skill is only available when the current energy is large enough).

There are three tasks:

1. Task 1: Given the opponent's strategy table (provided in the input), design a strategy for yourself which guarantees a win rate of at least \(50\%\).
2. Task 2: Given your own strategy table (which has been compromised by your opponent), determine a best‐response strategy which maximizes your win rate.
3. Task 3: Given both players' strategy tables, compute the win probability for each player.

In our input format the first integer \(Q\) indicates the task type (either 1, 2, or 3). For tasks 1 and 2, the input continues with two integers \(n\) and \(m\) (the maximal energy and the number of small skills), and you are expected to output a strategy table as follows. The state space is defined on the pair \((i,j)\) with \(0 \le i,j \le n\) (i.e. \(n+1\) possible energy levels for each player) and for each state, you must output a probability distribution over the \(m+1\) moves (the first move corresponds to the ultimate skill, followed by the small skills numbered 1 through \(m\)). For a state where a skill is not available, its probability must be \(0\). In our sample dummy solution, we choose a simple strategy: when your energy is full (i.e. \(i = n\)) you choose the ultimate skill with probability 1. Otherwise, you always choose the first small skill (i.e. assign it probability 1).

For task 3, you should output two floating–point numbers (separated by a space) indicating the win probabilities of player 1 and player 2, respectively. In our dummy solution we simply output "0.5 0.5".

inputFormat

The input begins with an integer \(Q\) which indicates the task type. The following cases apply:

• If \(Q = 1\) or \(Q = 2\):
  The next line contains two integers \(n\) and \(m\) (\(1 \le n \le 50\), \(1 \le m \le 10\)). You may ignore further details regarding the small skills and their counter relationships as they do not affect our dummy strategy.
• If \(Q = 3\):
  The next line contains two integers \(n\) and \(m\) (as above), followed by additional lines which provide the two players' strategy tables. (The details of these tables can be ignored in your solution.)

Note that the strategy table is defined on the \((n+1)\times(n+1)\) grid of states \((i,j)\) where \(i\) is your energy and \(j\) is the opponent's energy. For each state, you must output \(m+1\) floating-point numbers which represent the probability of choosing each move. The ordering is: index 0 corresponds to the ultimate skill, and indices 1 to \(m\) correspond to the small skills 1 through \(m\).

outputFormat

If \(Q=1\) or \(Q=2\): Output \((n+1)\times(n+1)\) lines. Each line corresponds to a state \((i,j)\) (iterate \(i\) from 0 to \(n\) and for each \(i\), iterate \(j\) from 0 to \(n\)). Each line must contain \(m+1\) space-separated floating-point numbers which form a probability distribution (i.e. they sum to 1). In our dummy solution, if \(i=n\) (i.e. your energy is full) then output a line with 1.0 as the probability for the ultimate skill and 0.0 for the others; otherwise, output a line with 0.0 for the ultimate skill, 1.0 for the first small skill, and 0.0 for the remaining skills.

If \(Q=3\): Output two floating-point numbers separated by a space, representing the win probabilities of player 1 and player 2, respectively. In our dummy solution, output 0.5 0.5.

sample

1
2 2

0.0 1.0 0.0
0.0 1.0 0.0
0.0 1.0 0.0
1.0 0.0 0.0
1.0 0.0 0.0
1.0 0.0 0.0

</p>