[Solution] The Mind solution codeforces | ICPC WF Moscow Invitational Contest

The Mind solution codeforces

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.0pi1.0,5i=1pi10.0≤pi≤1.0,∑i=15pi≤1, where pipi — the probability of playing the player’s smallest card in their hand on ii-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=1000n=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 nn 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 2020 randomly generated tests with n=1000n=1000.

The Mind solution codeforces

Input

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

Each of the next nn lines contains 5 numbers aiai (1ai100,ai<ai+11≤ai≤100,ai<ai+1) — the cards in the hand. It is guaranteed that each possible set of 5 cards has an equal probability of being chosen.

Output

For each of the nn hands you need to output 5 numbers 0.0pi1.0,5i=1pi10.0≤pi≤1.0,∑i=15pi≤1, where pipi — probability of playing the smallest card on ii-th turn.

The Mind solution codeforces

Example

The Mind solution codeforces

input

Copy
2
2 12 27 71 100

22 29 39 68 90
output

Copy
0.8 0.2 0.0 0.0 0.0 

0.0 0.2 0.2 0.2 0.3

The Mind solution codeforces

Note

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(10.2)=0.960.8+0.2⋅(1−0.2)=0.96. Also note that the second player will not play a card at all with probability 0.1.


 

The Mind solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment