Programozás‎ > ‎Feladatok‎ > ‎

Biztonságos pontszám

Egy valóságshow-ban N versenyző szerepel. Mindenki kap egy pontot a zsűritől és kaphat szavazatokat a nézőktől. A zsűri által adott pont és a közönségszavazatok együtt fogják meghatározni a versenyzők pontszámát: 

A zsűri által kiosztott pontok összege legyen X, és egy versenyző kapjon J pontot a zsűritől. Tegyük fel, hogy ugyanezen versenyző közönségszavazat aránya Y (0 <= Y <= 1). Ekkor a tényleges pontszámát így határozzák meg: J+X*Y. 
(Jegyezzük meg, hogy a versenyzőkhöz rendelt szavazatarányok összege mindig 1.)

A legalacsonyabb pontszámú versenyző esik ki. 

Feladat

A zsűri által adott pontszámok ismeretében határozzuk meg minden versenyzőre, hogy legalább hány százalékát kell megkapnia a közönség szavazatainak, hogy biztosan ne essen ki, függetlenül a többiekre leadott szavazatok megoszlásától. Ha több legkisebb pontszám van, akkor senki nem esik ki. 

Bemenet

Az első sor a tesztesetek T számát adja meg. Ezután soronként egy teszteset következik, ahol az első szám a versenyzők N száma, majd a versenyzők zsűritől kapott pontjai következnek: s0, s1, ..., sN-1. A kapott pontszámok szóközökkel elválasztott egészek. 

Méretek

0 <= si <= 100 és si > 0 valamilyen i-re, vagyis legalább egy versenyző pozitív pontot kap a zsűritől.

Kis bemenet

1 <= T <= 20, 2 <= N <= 10

Nagy bemenet

1 <= T <= 50, 2 <= N <= 200

Kimenet

Minden tesztesethez ki kell írni (a versenyzők eredeti sorrendjében) azt a minimálisan elegendő százalék értéket, amivel már biztosan nem esik ki az adott versenyző. A törteket 10-5 pontossággal kell megadni.

Példa

Bemenet  Kimenet
4
2 20 10
2 10 0
4 25 25 25 25
3 24 30 21

Case #1: 33.333333 66.666667
Case #2: 0.000000 100.000000
Case #3: 25.0 25.0 25.0 25.0
Case #4: 34.666667 26.666667 38.666667



Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2013 R1B (https://code.google.com/codejam/contest/1836486/dashboard)
Algoritmusok: bináris keresés

megoldás