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. A legalacsonyabb pontszámú versenyző esik ki. FeladatA 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.
BemenetAz 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éretek0 <= si <= 100 és si > 0 valamilyen i-re, vagyis legalább egy versenyző pozitív pontot kap a zsűritől.Kis bemenet1 <= T <= 20, 2 <= N <= 10Nagy bemenet1 <= T <= 50, 2 <= N <= 200KimenetMinden 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
TesztadatokCímkékA feladat forrása: Google Code Jam 2013 R1B (https://code.google.com/codejam/contest/1836486/dashboard)
Algoritmusok: bináris keresés
megoldás |
Programozás > Feladatok >
