Optimal Strategies in the Smuggling Game

The Smuggling Game is played between two players: the smuggler and the prosecutor. In a single round the smuggler secretly chooses an integer amount \( x \) in the range \( [0, n] \) (in Japanese yen) to smuggle, while the prosecutor tries to guess the amount by choosing an integer \( y \). The payoff rules are given in \( \LaTeX \) as follows:

[ \text{Payoff}(x,y)= \begin{cases} 0, & \text{if } x = y,\ x, & \text{if } x > y,\ \dfrac{y}{2}, & \text{if } x < y. \end{cases} ]

If \( x=y \) the smuggling fails and the smuggler gains nothing; if \( x>y \) the smuggler succeeds and gains \( x \) yen; if \( x<y \) the smuggling fails but the prosecutor must pay \( \frac{y}{2} \) yen to the smuggler as compensation. Both players play repeatedly with roles interchanged, and it can be proved that in the optimal (Nash equilibrium) the smuggler and the prosecutor each use a fixed mixed strategy each round.

Your task is: given \( n \) (the maximum amount), determine the optimal mixed strategies for both players in one round. In other words, compute two probability distributions:

• For the smuggler: probabilities \( p_0, p_1, \dots, p_n \) for choosing amounts \( 0,1,\dots,n \) (note that some actions may have zero probability in equilibrium).
• For the prosecutor: probabilities \( q_0, q_1, \dots, q_n \) for guessing \( 0,1,\dots,n \).

The equilibrium conditions are derived from the indifference principle. For every action in the support of the smuggler, the expected payoff

[ E[u(x)] = \Bigl( x\sum_{y=0}^{x-1}q_y+ \frac{1}{2}\sum_{y=x+1}^{n} y,q_y \Bigr) ]

must equal a constant ( v ) (the value of the game). Similarly, for every action in the support of the prosecutor, we have

[ E[u(y)] = \Bigl( \frac{y}{2}\sum_{x=0}^{y-1}p_x + \sum_{x=y+1}^{n} x,p_x \Bigr) = v. ]

In this problem, \( n \) will be small (for example, \( n=1,2,3 \)). You are guaranteed that the unique Nash equilibrium probabilities (rounded to 6 decimals) for these cases are as follows:

• For \( n=1 \):
  • Smuggler: 0.666667 0.333333
  • Prosecutor: 0.333333 0.666667
• For \( n=2 \):
  • Smuggler: 0.500000 0.250000 0.250000
  • Prosecutor: 0.125000 0.250000 0.625000
• For \( n=3 \):
  • Smuggler: 0.400000 0.200000 0.200000 0.200000
  • Prosecutor: 0.130435 0.000000 0.260870 0.608695 (approximated)

When \( n \) is not one of these values, you may output any valid pair of probability distributions (each summing to 1) — they will not be tested. However, for the official test cases the input will be one of \( 1, 2, 3 \).

Input Format: A single integer \( n \) (\( n\ge1 \)).

Output Format: Output two lines. The first line contains \( n+1 \) space‐separated real numbers representing the smuggler's probabilities for \( 0,1,\dots,n \) (rounded to 6 decimals). The second line contains \( n+1 \) space‐separated real numbers representing the prosecutor's probabilities for \( 0,1,\dots,n \) (rounded to 6 decimals).

inputFormat

A single integer \( n \) representing the maximum amount (in yen) that can be smuggled. In the official test cases, \( n \) will be one of: 1, 2, or 3.

outputFormat

Two lines: the first line contains \( n+1 \) space‐separated real numbers (each rounded to 6 decimals) which are the probabilities for the smuggler’s choices from 0 to \( n \). The second line contains \( n+1 \) space‐separated real numbers (rounded to 6 decimals) which are the probabilities for the prosecutor’s guesses from 0 to \( n \).

sample

1

0.666667 0.333333
0.333333 0.666667