The Mind

题意翻译

**这是一道交互题。** 在这道题中，你需要设计对于一个合作游戏的策略。这个游戏中有两名玩家。每个玩家会收到 $5$ 张牌。每张牌上写有 $1$ 到 $100$ 之间的随机整数。保证牌面上所有数字两两不同。 游戏的目标是在其他牌打出之前，打出目前发给玩家的 $10$ 张牌中牌面数字最小的一张。问题在于每个玩家只能看到他们自己手中的牌，并且不能以任何方式与任何玩家交流。 这个游戏有 $5$ 轮，每轮中，玩家同时行动。每个玩家要么打出他们手中最小的牌，要么不动。如果在某些轮次中是最小值的牌被打出，并且在此轮及之前没有任何牌被打出，玩家获胜。如果两张牌同时在相同的一轮被打出，或者在 $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$ 个？）策略计算获胜概率。 **为了保证对于不同的手牌答案是独立的，在读入下一组手牌情况之前你必须输出这组手牌的策略并调用 $\texttt{flush}$ 函数清理输出。** 如果对于所有合法的手牌对来说，平均有超过 $85\%$ 的概率获胜的话，这组测试数据就被认为是通过的。这道题包含样例和 $20$ 组随机生成且 $n=1000$ 的测试数据。 第一行包含一个整数 $n$，表示手牌的组数。保证除了第一组样例外，其余测试数据 $n=1000$。 接下来 $n$ 行，每行 $5$ 个数字 $a_i\ (1\le a_i\le 100,a_i<a_{i+1})$，表示目前手牌的情况，保证这 $5$ 张牌都是等概率选取的。 对于这 $n$ 组手牌，你需要对于每组都输出 $5$ 个数字 $0.0\le p_i\le 1.0,\sum_{i=1}^5 p_i\le 1$，这里 $p_i$ 表示在第 $i$ 轮玩家打出最小的牌的概率。 在样例中只有一组有效的手牌。样例输出的获胜概率为 $0.8+0.2\cdot(1-0.2)=0.96$。同时注意第二个玩家有 $0.1$ 的概率根本不会打出任何一张牌。

题目描述

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 $ .

输入输出格式

输入格式

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 < 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.

输出格式

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.

输入输出样例

输入样例 #1

2
2 12 27 71 100

22 29 39 68 90

输出样例 #1

0.8 0.2 0.0 0.0 0.0 

0.0 0.2 0.2 0.2 0.3

说明

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.