ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Space Poker 2

Time limit: 0.5 second
Memory limit: 64 MB
At the First Lunar Casino there are new rules for playing space poker. A pack contains N cards. A player pays the croupier 20 space rubles and chooses a card from his pack. The croupier chooses a card from his pack. If the selected cards are identical, then the player wins 1000 rubles. If the cards are different, then he/she may win a sum not exceeding 10 rubles. This sum depends on the cards that have been chosen and is specied in the prize-table.
Your task is to write a program that tells the croupier which card to choose in order to maximize the mean profit of the casino. It is supposed that all players know the prize-table by heart and choose their strategies in the best possible way.
If you ask any mathematician how to write such a program, you'll learn that this is a classical minimax problem, which was solved decades ago, and that everyone should know about matrix games with mixed strategies. The croupier should choose a card at random with such probabilities that the mathematical expectation of the gain is independent of the card chosen by the player. And if you ask about a mathematical expectation, this is a kind of a mean value: the sum of possible gains multiplied by probabilities of getting them.

Input

The first line contains the number of cards N (1 < N ≤ 100). Then follows the prize-table. Each row of the table shows possible gains of a player who has chosen the card corresponding to the number of the row. The number of the column corresponds to the card chosen by the croupier. The numbers in the main diagonal of the table are 1000, other numbers are in the range from 0 to 10.

Output

You should output with accuracy to the fifth digit the probabilities with which the croupier should choose a card.

Sample

inputoutput
3
1000 10 10
0 1000 1
5 3 1000
0.32986
0.33623
0.33391
Problem Author: Stanislav Vasilyev
Problem Source: The Ural State University Championship, October 29, 2005
To submit the solution for this problem go to the Problem set: 1417. Space Poker 2