CF1578M.The Mind

This is an interactive problem.

In this problem, you need to come up with a strategy for a cooperative game. This game is played by two players. Each player receives 5 cards. Each card has a random integer between 1 and 100 on it. It is guaranteed that all numbers on cards are distinct.

The goal of the game is to play a card with a minimal number on it out of all 10 cards dealt to the players before any other card. The problem is that each player can only see their own cards and cannot communicate with another player in any way.

The game consists of 5 turns. During each turn, players simultaneously make a move. Each player can either play their smallest card or do nothing. If on some turn the smallest card is played, and no other card is played on or before that turn, players win. If two cards are played at the same turn or if after all 5 turns, no card is still played, players lose.

Players cannot communicate, so a strategy for the game should only be based on 5 cards that the player has. You can describe a strategy as five numbers $0.0 \le p_i \le 1.0, \sum_{i=1}^{5}p_i \le 1$, where $p_i$ — the probability of playing the player's smallest card in their hand on $i$-th turn. If you know the cards dealt to the players, and the strategies that players choose, you can compute the probability of winning by a simple formula.

You will be given $n=1000$ randomly generated hands of 5 cards. You need to generate a strategy for each of the hands to maximize the probability of winning. After the judge program receives all $n$ strategies, it generates all possible valid pairs of those hands (pairs which have the same numbers are discarded), and computes a probability of winning based on two strategies provided by your program.

To ensure that answers for different hands are independent, you must output a strategy for a hand and flush the standard output before reading information about the next hand.

If the average probability of winning a game is more than 85% over all valid pairs of hands, the test is considered passed. This problem contains the sample test and $20$ randomly generated tests with $n = 1000$.

这是一个交互式问题。

本题中，你需要为一个合作博弈设计一种策略。该博弈由两名玩家参与。每名玩家会收到 5 张牌，每张牌上印有一个 $1$ 到 $100$ 之间的随机整数。保证所有牌上的数字互不相同。

游戏的目标是：在全部 10 张牌中数值最小的那张牌被打出时，恰好是第一张被打出的牌（即在此之前没有任何牌被打出）。但问题在于，每名玩家只能看到自己手中的牌，且两名玩家之间完全无法进行任何形式的通信。

游戏共进行 5 轮。每轮中，两名玩家同时行动。每名玩家在每轮中可选择：打出自己手中当前最小的牌，或选择不行动（即跳过该轮）。若在某一轮中，全局最小的那张牌被打出，且此前（含该轮之前）没有任何其他牌被打出，则玩家获胜；若某一轮中有两张牌同时被打出，或经过全部 5 轮后仍未有任何牌被打出，则玩家失败。

由于玩家之间无法通信，因此每位玩家所采用的策略只能依赖于自己手中的 5 张牌。你可以将一个策略描述为五个数 $0.0 \le p_i \le 1.0$，满足 $\sum_{i=1}^{5}p_i \le 1$，其中 $p_i$ 表示该玩家在第 $i$ 轮打出其手中当前最小牌的概率。若已知双方各自的手牌以及他们所采用的策略，则可通过一个简单公式计算出获胜概率。

你将收到 $n = 1000$ 组随机生成的、每组含 5 张牌的手牌。你需要为每一组手牌生成一个策略，以最大化获胜概率。评测程序在接收全部 $n$ 个策略后，将枚举所有可能的、合法的手牌对（即从这 $n$ 组手牌中选出两组构成配对，且要求两组手牌所含数字集合不完全相同），并基于你为这两组手牌分别提供的策略，计算对应配对下的获胜概率。

为确保不同手牌对应的策略输出相互独立，你必须在为某一手牌输出策略后，立即刷新标准输出缓冲区，然后再读取下一组手牌的信息。

若在所有合法手牌对上计算得到的平均获胜概率超过 $85\%$，则该测试用例视为通过。本题包含一个样例测试以及 $20$ 个随机生成的测试用例，每个测试用例中 $n = 1000$。

The first line contains one integer $n$ — the number of hands. It is guaranteed that $n = 1000$ for all cases except the first sample case.

Each of the next $n$ lines contains 5 numbers $a_i$ ($1 \le a_i \le 100, a_i \lt a_{i+1}$) — the cards in the hand. It is guaranteed that each possible set of 5 cards has an equal probability of being chosen.

第一行包含一个整数 $n$ —— 手牌的数量。除第一个样例外，所有测试用例均保证 $n = 1000$。

接下来的 $n$ 行中，每行包含 5 个数字 $a_i$（$1 \le a_i \le 100$，且 $a_i \lt a_{i+1}$）—— 表示该手牌中的五张牌。保证每种可能的五张牌组合被选中的概率均相等。

For each of the $n$ hands you need to output 5 numbers $0.0 \le p_i \le 1.0, \sum_{i=1}^{5}p_i \le 1$, where $p_i$ — probability of playing the smallest card on $i$-th turn.

对于每手牌（共 $n$ 手），你需要输出 5 个数 $0.0 \le p_i \le 1.0$，满足 $\sum_{i=1}^{5}p_i \le 1$，其中 $p_i$ 表示在第 $i$ 轮出最小牌的概率。

In the example test there is only one valid pair of hands. The winning probability for the example output is equal to $0.8 + 0.2 \cdot (1 - 0.2) = 0.96$. Also note that the second player will not play a card at all with probability 0.1.

在示例测试中，仅存在一对有效的手牌。示例输出的获胜概率等于 $0.8 + 0.2 \cdot (1 - 0.2) = 0.96$。另外请注意，第二位玩家完全不打出任何牌的概率为 $0.1$。