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

Betting Sets

Betting Sets

Your local casino (which here in California is a fair distance away) has decided to try out a new betting game. The player is given a table on a card with \textbf{N} rows and \textbf{M} columns. Each entry \textbf{i j} of the table corresponds to a coin flip with a probability \textbf{p_ij} of coming up heads. All the coin flips are independent of each other. The player must choose \textbf{N} sets of \textbf{M}entries, with each set having exactly one entry from each column, and each entry being used exactly once. For each chosen set where all \textbf{M} coins come up heads, the player wins \textbf{1} dollar. The casino is feeling uncharacteristically generous, and so as part of the promotion of this new game, they have been handing out one card to each patron. Since you have nothing to lose, you're going to give this game a shot. How can you maximize your expected winnings from this card? \InputFile The input consists of multiple test cases. Each test case begins with a line with two integers \textbf{N} and \textbf{M}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100}, \textbf{1} ≤\textbf{M} ≤ \textbf{10}, separated by a space. This is followed by \textbf{N} lines with \textbf{M} space-separated numbers each, denoting the entries\textbf{p_ij} of the table. Input is followed by a single line with \textbf{N = M =0}, which should not be processed. \OutputFile For each test case, print out a single line with the maximum expected winnings from the given table, accurate to \textbf{4}decimal places.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
2 3
1.0 1.0 1.0
0.5 0.4 0.3
0 0
Çıxış verilənləri #1
1.0600