eolymp
bolt
Try our new interface for solving problems
Məsələlər

A Treasure Or A Bomb

A Treasure Or A Bomb

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

An adventurer seeking a legendary treasure discovered a mysterious door in a deep cavern. The door had many keyholes, and near the door the same number of keys were placed. Keyholes were numbered from 1 to N, and so were the keys.

According to a treasure map he had, the door would open and lead him to the treasure room if he inserted all the keys into the keyholes at the same time. Each key might be inserted into an arbitrary keyhole, so it seemed to be an easy task — in fact it was not true because there was one big trap on the door. When each of the keys was inserted to a keyhole, a bomb planted in the door might explode in some probability.

On the kindly treasure map, all p_ij's (the probability of explosion when the i^{-th} keyhole was plugged by the j^{-th} key) were listed. The cautious but greedy adventurer had decided to insert the keys in the way to maximize the safety, that is, to maximize the probability not to explode. Suppose the situation with two keys and keyholes where p_{11 }= 0.4, p_{12 }= 0.5, p_21 = 0.5, p_22 = 0.6, if he inserts the first key to the first keyhole and the second to the second, the probability of non-explosion is (1-0.4)×(1-0.6) = 0.24. On the other hand, if he inserts the second key to first hole and the first key to the second, then the probability is 0.25, which is better.

You are to find the best way to insert the keys. You may assume the answer is unique. The maximum probability of no-exlopsion is strictly 1.00001 times larger than the probability with any non-optimal key insertion.

Giriş verilənləri

The input for this problem consists of multiple test cases. Each case begins with a line containing single integer N (1 N100), which specifies the number of the keys and keyholes.

In the following N lines, the i^{-th} line contains N real numbers p_i1, ..., p_iN (0.00001p_ij0.99999). p_ij gives the probability of explosion when the i^{-th} keyhole is plugged by the j^{-th} key. Real numbers are represented by decimal form with at most five digits after the decimal point.

The input is terminated by a line which contains a single zero.

Çıxış verilənləri

For each test case, output N lines. The i^{-th} line for each test case should contain only one integer to represent the key which the adventurer should insert into the i^{-th} keyhole. Outputs for different test cases must be separated by one blank line.

Nümunə

Giriş verilənləri #1
3
0.8 0.9 0.1
0.1 0.4 0.5
0.6 0.1 0.7
2
0.4 0.5
0.5 0.6
0
Çıxış verilənləri #1
3
1
2

2
1
Mənbə ACM International Collegiate Programming Contest, Summer Camp (2nd Day), Tokyo, 2005–9–24