1038 : Bond
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

ทุกคนคงจะรู้จักสายลับศูนย์ศูนย์เจ็ด เจมส์ บอนด์ ผู้โด่งดัง แต่ก็ยังไม่มีคนทราบว่าความจริงแล้ว เขาไม่ได้ปฏิบัติภารกิจส่วนใหญ่ด้วยตัวเขาเอง แต่เป็นลูกพี่ลูกน้องของเขา จิมมี่ บอนด์ ต่างหาก ส่วนเจมส์บอนด์จะเป็นคนกำหนดลำดับภารกิจสำหรับจิมมี่ ทุกครั้งที่มีภารกิจใหม่เข้ามา ดังนั้นเขาจึงต้องการให้คุณช่วย

ทุกเดือนจะมีรายการของภารกิจเข้ามา ด้วยความอัจฉริยะและประสบการณ์ของเจมส์ เขาสามารถคาดคะเนความน่าจะเป็นที่จิมมี่จะปฏิบัติภารกิจนั้นๆ สำเร็จได้ เมื่อเขาลงมือปฏิบัติภารกิจนั้นเป็นลำดับที่ต่างๆกันไป (ภารกิจหนึ่งอาจจะมีความน่าจะเป็นไม่เท่ากัน เมื่อเลือกทำเป็นลำดับแรก หรือ ลำดับที่สอง หรือ ลำดับที่สาม)

โจทย์

จงเขียนโปรแกรมที่รับจำนวนภารกิจและความน่าจะเป็นของความสำเร็จของภารกิจต่างๆ และหาว่าความน่าจะเป็นสูงสุดที่จิมมี่จะปฏิบัติภารกิจทุกภารกิจสำเร็จเป็นเท่าใด โดยที่ความน่าจะเป็นที่จะปฏิบัติภารกิจทุกภารกิจสำเร็จคือผลคูณของความน่าจะเป็นของทุกภารกิจที่ปฏิบัติ

ข้อมูลนำเข้า

บรรทัดแรก เป็นจำนวนเต็ม N (1 ≤ N ≤ 20) คือจำนวนภารกิตที่ได้รับมอบหมาย

บรรทัดอีก N บรรทัดถัดมา จะประกอบไปด้วยจำนวนเต็ม N จำนวนคือความน่าจะเป็นที่จะปฏิบัติภารกิจ โดยในบรรทัดที่ i ตัวเลขตัวที่ j คือความน่าจะเป็นของภารกิจที่ j เมื่อเลือกทำเป็นลำดับที่ i โดยค่าเหล่านี้จะเป็นร้อยละ ซึ่งมีค่าในช่วง 0 ถึง 100

ข้อมูลส่งออก

บรรทัดเดียว แสดงความน่าจะเป็นที่สูงที่สุดของการปฏิบัติภารกิจของจิมมี่ ด้วยร้อยละเป็นจำนวนทศนิยม โดยผลลัพธ์จะต้องต่างกับคำตอบไม่เกิน 0.000001 (หนึ่งในล้านส่วน) จึงจะถือว่าถูกต้อง

อธิบายตัวอย่างที่สาม (ด้านล่าง)

ถ้าจิมมี่เลือกทำภารกิจตามลำดับเป็น ภารกิจที่ 3 ภารกิจที่ 1 และภารกิจที่ 2 ตามลำดับ

จะได้ความน่าจะเป็นเท่ากับ 1.0 * 0.13 * 0.7 = 0.091 = 9.1%

ส่วนรูปแบบลำดับของภารกิจอื่นนั้นจะได้ความน่าจะเป็นที่น้อยกว่าเสมอ

 

ที่มา: COCI 2006/2007, Contest #1 – October 28, 2008
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
2
100 100
50 50
50.000000
2
0 50
50 0
25.00000
3
25 60 100
13 0 50
12 70 90
9.10000

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 5 สมาชิก (0 บอท)