Runda 17 - Kulki w walcu

25.01.2010 - Przemysław Uznański
TrudnośćTrudność

 

 

Zawody stałe, runda 17.

Limit czasowy: 7s; Limit pamięciowy: 32 MB


Kulki w walcu

 

Mamy daną długą rurkę (walec który jest pusty w środku). Rurka ta stoi na stole i jest otwarta z góry. Promień rurki to 1cm. Mamy też zestaw stalowych kulek. Chcemy wrzucić te kulki do środka rurki tak, by różnica wysokości między najniżej zajętym przez którąkolwiek kulkę punktem a najwyżej zajętym była minimalna. Kulki zawsze spadają maksymalnie w dół jak tylko jest to możliwe (przy wrzuceniu od góry). Innymi słowy chcemy, aby wysokość utworzonej w ten sposób wieży z kulek była jak najmniejsza. Promień kulki zawsze spełnia zależność 0.5 ≤ r ≤ 1.

Wejście

Pierwsza liczba, to 1≤t≤10, liczba przypadków testowych Kolejne t testów jest następującej postaci: Wpierw, 1≤n≤100000, liczba kulek. Kolejna linia zawiera n różnych liczb z przedziału (0.5,1], promieni dostępnych nam kulek.

Wyjście

Dla każdego przypadku testowego - dokładnie jedna liczba, najmniejsza wysokość jaką można uzyskać. Wynik wypisz z dokładnością do 6 cyfr po przecinku.

Przykład

Wejście:

1 3 1 0.7 0.9
Wyjście:

5.122513


Wyjaśnienie przykładu: gdy w walcu umieścimy najpierw kulkę o promieniu 1, potem o promieniu 0.7, a potem 0.9, uzyskamy najmniejszą wysokość.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski10135:38:18
2Bartek Dudek10152:21:05
3Anna Piekarska10180:43:50
4
Twoja ocena: Brak Ocena: 4 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com