Xəzinə Yoxsa Bomba
Bir macəraçı əfsanəvi xəzinəni axtararkən dərin bir mağarada sirli bir qapı tapdı. Qapının çoxlu açar dəlikləri vardı və qapının yanında eyni sayda açarlar yerləşdirilmişdi. Açar dəlikləri 1-dən N-ə qədər nömrələnmişdi və açarlar da elə.
Onun sahib olduğu xəzinə xəritəsinə görə, əgər o, bütün açarları eyni anda açar dəliklərinə yerləşdirsə, qapı açılacaq və onu xəzinə otağına aparacaq. Hər bir açar istənilən açar dəliyinə yerləşdirilə bilərdi, buna görə də bu asan bir iş kimi görünürdü — əslində bu doğru deyildi, çünki qapıda böyük bir tələ vardı. Hər bir açar açar dəliyinə yerləşdirildikdə, qapıya yerləşdirilmiş bomba müəyyən bir ehtimalla partlaya bilərdi.
Xəzinə xəritəsində, bütün p_ij (açar dəliyinin i-ci açarla bağlandığı zaman partlama ehtimalı) siyahıya alınmışdı. Ehtiyatlı, amma acgöz macəraçı, təhlükəsizliyi maksimum dərəcədə artırmaq, yəni partlamama ehtimalını maksimuma çatdırmaq üçün açarları yerləşdirməyə qərar verdi. İki açar və açar dəliyi olan vəziyyəti nəzərə alsaq, burada p_{11 }= 0.4, p_{12 }= 0.5, p_21 = 0.5, p_22 = 0.6, əgər o, birinci açarı birinci açar dəliyinə və ikinci açarı ikinciyə yerləşdirsə, partlamama ehtimalı (1-0.4)×(1-0.6) = 0.24 olur. Digər tərəfdən, əgər o, ikinci açarı birinci dəliyə və birinci açarı ikinciyə yerləşdirsə, ehtimal 0.25 olur ki, bu daha yaxşıdır.
Siz açarları yerləşdirmək üçün ən yaxşı yolu tapmalısınız. Cavabın unikal olduğunu qəbul edə bilərsiniz. Partlamama ehtimalının maksimumu, hər hansı qeyri-optimal açar yerləşdirmə ilə müqayisədə dəqiq 1.00001 dəfə böyükdür.
Giriş verilənləri
Bu problemin girişi bir neçə test halından ibarətdir. Hər bir hal tək bir tam ədəd N (1 ≤ N ≤ 100) olan bir sətirlə başlayır, bu da açarların və açar dəliklərinin sayını göstərir.
Sonrakı N sətirdə, i-ci sətir N real ədəd p_i1, ..., p_iN (0.00001 ≤ p_ij ≤ 0.99999) ehtiva edir. p_ij, i-ci açar dəliyinin j-ci açarla bağlandığı zaman partlama ehtimalını göstərir. Real ədədlər ondalık formada ən çox beş ondalık rəqəmlə təmsil olunur.
Giriş tək bir sıfır olan bir sətirlə bitir.
Çıxış verilənləri
Hər bir test halı üçün N sətir çıxarın. Hər bir test halı üçün i-ci sətir, macəraçının i-ci açar dəliyinə yerləşdirməli olduğu açarı təmsil edən yalnız bir tam ədəd ehtiva etməlidir. Fərqli test hallarının çıxışları bir boş sətirlə ayrılmalıdır.