COCI '06 Contest 1 #5 Bond

Points: 12

Time limit: 0.6s

Memory limit: 32M

Problem type

Everyone knows of the secret agent double-oh-seven, the popular Bond (James Bond). A lesser known fact is that he actually did not perform most of his missions by himself; they were instead done by his cousins, Jimmy Bonds. Bond (James Bond) has grown weary of having to assign missions to Jimmy Bonds every time he gets new missions so he has asked you to help him out.

Every month Bond (James Bond) receives a list of missions. Using his detailed intelligence from past missions, for every mission and for every Jimmy Bond he calculates the probability of that particular mission being successfully completed by that particular Jimmy Bond. Your program should process that data and find the arrangement that will result in the greatest probability that all missions are completed successfully.

Note: the probability of all missions being completed successfully is equal to the product of the probabilities of the single missions being completed successfully.

Input Specification

The first line will contain an integer $N$ ~N~, the number of Jimmy Bonds and missions $(1 \le N \le 20)$ ~(1 \le N \le 20)~.
The following $N$ ~N~ lines will contain $N$ ~N~ integers between $0$ ~0~ and $100$ ~100~, inclusive. The $j^{th}$ ~j^{th}~ integer on the $i^{th}$ ~i^{th}~ line is the probability that Jimmy Bond $i$ ~i~ would successfully complete mission $j$ ~j~, given as a percentage.

Output Specification

Output the maximum probability of Jimmy Bonds successfully completing all the missions, as a percentage.

Note: Outputs within $\pm 0.000001$ ~\pm 0.000001~ of the official solution will be accepted.

Sample Input 1

2
100 100
50 50

Sample Output 1

50.000000

Sample Input 2

2
0 50
50 0

Sample Output 2

25.00000

Sample Input 3

Sample Output 3

9.10000

Explanation for Sample Output 3

If Jimmy Bond 1 is assigned the $3^{rd}$ ~3^{rd}~ mission, Jimmy Bond 2 the $1^{st}$ ~1^{st}~ mission and Jimmy Bond 3 the $2^{nd}$ ~2^{nd}~ mission the probability is: $1.0 \times 0.13 \times 0.7 = 0.091 = 9.1\%$ . All other arrangements give a smaller probability of success.

Comments

14

bariumlanthanum commented on Jan. 13, 2022, 8:39 p.m.

Everyone knows of the secret agent double-oh-seven, the popular Bond (James Bond).

if he's the most popular secret agent ever, doesn't that mean he's the worst?

1

DM__Oscar commented on Sept. 4, 2020, 6:54 p.m.

TFW you didn't print enough float precision.

8

ross_cleary commented on April 7, 2020, 8:11 p.m.

If this problem is worth 12 points, shouldn't this one also be worth 12?