Found one interesting task. I will think over the decision and it would be nice to hear your suggestions:

Each month, James Bond receives a list of missions. Based on his wealth of experience, he calculates the probability of successfully completing the missions of each of his cousins ​​Jimi Bond number X.

Your program must process this data and find such a separation of missions between cousins ​​to get the greatest chance that all missions will be successfully completed.

Note: the probability that all missions will be successfully completed is equal to the product of the probabilities that individual missions will be completed successfully.

Input format

The first line contains an integer N - the number of missions (1 <= N <= 20). The next N lines contain N integers from 0 to 100, inclusive. The j-th integer on the i-th line means the probability that cousin i will successfully complete the mission j. The probability is given as a percentage.

Output format

Print the maximum probability of successful completion of all missions, as a percentage.

Conclusion that differs from the official response by no more than +0.000001 will be accepted.

Examples

input input input 2 2 3 100 100 0 50 25 60 100 50 50 50 0 13 0 50 12 70 90 output output output 50.000000 25.00000 9.10000

Explanation of the 3rd example:

If Jimmy 1 is assigned to the 3rd mission, Jimmy 2 is assigned to the 1st mission, and Jimmy 3 is assigned to the 2nd mission, then we will get the success rate equal to 1.0 * 0.13 * 0.7 = 0.091 = 9.1%. All other mission distribution options are less likely to succeed.

PS Question to the administration: I often solve problems of this type (sports programming) and, if I offer them to solve (too often) on this forum, would you consider that I flood your website and will not follow this ban?

  • four
    It seems to me that really interesting algorithmic problems are good. The only thing I would recommend is to write a more meaningful title, otherwise the portal will have dozens of questions with the title “Interesting Task” or “Are there any other solutions”, among which it will be very difficult to find the interesting one. - Fiztex
  • Hour task is not on minimax? In the first approximation, I did this: 1) I would find the maximum probability. Would mark her. 2) would reduce the table on this line and on this column. 3) I would conduct the process for the remainder of the table. So I get the maximum product. Because each member will be max. If during the transition between item 1 and item 2 there is a situation that the maximum probability occurs several times, then it is obvious that it is advantageous to choose the line in which the remaining probabilities are worse. - gecube
  • Those. from 25 60 100 and 26 59 100 it is necessary to choose the second to get 1.00 * 0.6, otherwise max. we get 1.00 * 0.59, which is worse. Check and express your suggestions on this train of thought =) - gecube
  • one
    If I understand correctly, you are proposing an essentially greedy strategy. I have already stepped on this rake - it does not work. It is enough to imagine a case when in the end there remains a zero probability, which kills all the greedy winnings. Apparently, here you need to use a strategy such as dynamic programming, reducing this task to solving problems of a lower dimension. Maybe tomorrow I’ll draw this thought in more detail. - Fiztex
  • one
    It's not about zero probabilities (just the most obvious example). Imagine 4 numbers a> b> c> d. a d can easily be less than b c. This greedy strategy does not take into account. - Fiztex

2 answers 2

It seems to come up with. Tonight I will test and report the results.

Decision:

DP by bitmasks. We will store in the array f answers of a lesser dimension to our problem. Indexes f - distribution missions for cousins.

Consider f [i] . Let's look at the binary representation of the number i . For example, i = 100110.

 |**№ бита** | 5 | 4 | 3 | 2 | 1 | 0 | |------------+---+---+---+---+---+---| |**знач. i** | 1 | 0 | 0 | 1 | 1 | 0 |

This means that the answer is in f [i] , and if you gave the task to cousin number k , then the k- th bit is 1. Moreover, if the number of non-zero bits in the number i is 3, then we distributed the cousins ​​for the first 3 missions.

More specifically, the implementation:

We look through all the masks (from 0 to 2 ^ 20 - 1 ~ 10 ^ 6), representing our distribution (1). For each mask we count the number of units in it - this is the number of distributed missions m (2). We look: what cousins ​​we do not perform any tasks (3). We try to assign some cousin job v + 1 . (4) everything

a [i, j] is the probability of fulfilling mission j by cousin i

  for msk := 0 to pow[n] - 1 do begin //pow[w] = 2^w; (1) v := q(msk); //(2) for i := 1 to n do // перебираем всех кузин if msk and pow[i-1] = 0 then //(3) f[msk or pow[i-1]] := max(f[msk or pow[i-1]],f[msk]*a[v+1,i]);// (4) end;

we get the answer when all the cousins ​​are distributed, that is, all bits = 1 (f [2 ^ n-1]).

Thus, the solution works in N * 2 ^ N ~ 20.000.000 (<1 second the algorithm will be executed).

Full code:

 const maxN = 21; maxS = 1 shl maxN; var n,m,i,j,msk,v : longint; a : array [1..maxN,1..maxN] of double; f : array [1..maxS] of double; pow : array [0..maxN] of longint; function q(w : longint) : longint; var res : longint; begin res := 0; while w > 0 do begin if w and 1 = 1 then inc(res); w := w shr 1; end; q := res; end; function max(w1,w2 : double) : double; begin if w1 > w2 then max := w1 else max := w2; end; begin readln(n); for i := 1 to n do for j := 1 to n do begin read(a[i,j]); a[i,j] := a[i,j] / 100; end; pow[0] := 1; for i := 1 to maxN do pow[i] := pow[i-1] shl 1; for i := 1 to n do f[pow[i-1]] := a[1,i]; for msk := 0 to pow[n] - 1 do begin v := q(msk); for i := 1 to n do if msk and pow[i-1] = 0 then f[msk or pow[i-1]] := max(f[msk or pow[i-1]],f[msk]*a[v+1,i]); end; writeln(f[pow[n]-1]*100:0:10); end.
  • HOORAY! Tested - absolutely the right decision! - megacoder

I have no opportunity to comment (little reputation), so I give the answer. What are the limitations on the speed of the algorithm? You can try a brute force. If the number of cousins ​​(X) == the number of missions, then all the options X !. You can iterate through all the numbers from 1 to X ^ X, translate them into X-ary number system (for example, itoa (number, outString, X)), then divide the number into digits (The figure will say cousin number which makes the mission number equal to ordinal the number of the digit in the number), if some 2 digits are the same, then we immediately proceed to the next iteration of the cycle, otherwise we consider the total probability and write to the global variable max.

Yes, the decision is ugly and inefficient, but this is the first thing that came to mind. With a large number of cousins ​​it will be very long to count, but then it is reliable.

  • I have already written a simple solution. But I need "beautiful and effective"! - megacoder
  • time limit of 1 second. - megacoder