Game of Chance solution codeforces

Game of Chance solution codeforces

The King wants to marry off his daughter, and he wants her husband to have the greatest innate luckiness possible. To find such a person he decided to hold a heads-or-tails tournament.

If person AA with luckiness xx and person BB with luckiness yy play heads-or-tails against each other, person AA wins with probability x/(x+y)x/(x+y).

The tournament has several rounds. Each round some participants are split into pairs. Each pair plays against each other, and the loser leaves the tournament.

Game of Chance solution codeforces

The participants are numbered from 11 to nn. During the first round, a number kk (1kn1≤k≤n) is selected such that nk/2n−k/2 is a power of 22 (such kk always exists and is unique). Only participants numbered from 11 to kk take part in the first round. It ensures that in all other rounds the number of participants is the power of 22.

During other rounds, all the participants who still have not left the tournament take part. If during some round, participants numbered p1<<p2mp1<…<p2m take part, then they are split into pairs in the following manner: participant p2i1p2i−1 plays against participant p2ip2i for each ii from 11 to mm.

The rounds are held until only one participant is left. He is declared the winner of the tournament and he will marry the King’s daughter. The princess can’t wait to find out who is her future husband. She asked every participant to tell her his luckiness. Assuming they did not lie, she wants to know the probability of each participant winning the tournament. As you are the best friend of the princess, she asks you to help her.


The first line of the input contains the number of participants, nn (2n31052≤n≤3⋅105). The second line of the input contains nn integer numbers, a1,,ana1,…,an (1ai1091≤ai≤109). The luckiness of the ii-th participant equals to aiai.


Print nn numbers pipi. The ii-th number should be the probability of the ii-th participant winning the tournament. The absolute error of your answer must not exceed 10910−9.


Copy Game of Chance solution codeforces

1 4 1 1 4

Copy Game of Chance solution codeforces

0.026 0.3584 0.0676 0.0616 0.4864

Here is an example of a tournament bracket, showing the winning probability in each pair.

Game of Chance solution codeforces

Leave a Reply

Your email address will not be published. Required fields are marked *