|
|
VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004 |
Zadanie D - Akwarium |
Czasami można usłyszeć o rozterkach badaczy, którzy zastanawiają się nad tym, czy we wszechświecie jesteśmy sami, czy może istnieją jakieś inne istoty myślące, które rozwojem technicznym nas przewyższają. Jak na razie są to tylko ich teorie bazujące głównie na domysłach i nie mają żadnych dowodów. Jednak właśnie dzisiaj idąc do pracy poczułeś jakiś dziwny wir powietrza wokół siebie i nagle zostałeś wciągnięty do dziwnego Niezidentyfikowanego Obiektu Latającego (w skrócie UFO ;-) ). Gdy zacząłeś się rozglądać w tymże statku dojrzałeś kilka małych, śmiesznie wyglądających stworków, które zaczęły się z Tobą porozumiewać telepatycznie. Przedstawiły Ci swoje żądania, a po ich spełnieniu obiecały uwolnić i sprawić, że nie będziesz nic o nich pamiętał i znajdziesz się z powrotem na swojej drodze do pracy (cóż za wspaniałomyślne ufoludki... a może po prostu dbają o to, aby Ziemianie o nich nie wiedzieli? kto to wie... w każdym razie Twoim zadaniem nie będzie filozoficzna rozprawa na ten temat ;P).
Ufoludki zażądały od Ciebie programu, który pomoże dziecku ich władcy rozwiązywać pewną zagadkę, którą sobie wymyślił. Wyobraża on sobie akwarium w kształcie prostopadłościanu o wysokości H decymetrów, szerokości W decymetrów oraz "grubości" jednego decymetra (w takim wypadku jego objętość jest równa H*W litrów; jakby ktoś nie pamiętał: decymetr sześcienny to jest to samo co litr ;P). Następnie na jego dnie, jeden obok drugiego ustawia pionowo dokładnie W klocków. Klocki, o kształcie prostopadłościanu, mają szerokości i grubości równe jednemu decymetrowi oraz pewne ściśle określone wysokości (które syn władcy też sobie wymyśla). Po ustawieniu klocków w akwarium, wyobraża sobie, że nalewa do niego L litrów wody (musi sobie wyobrażać, bo akurat wody im brakuje i nie mogą jej bez potrzeby marnować). Przy nalewaniu uważa na to, by utrzymywać ten sam poziom wody nad wszystkimi klockami (oczywiście nie dotyczy to tych klocków, które są wyższe bądź równe aktualnemu poziomowi wody). Jego problem polega na tym, aby obliczyć jaki poziom osiągnie woda po nalaniu L litrów wody. W przypadku gdy poziom wody dojdzie do wysokości akwarium, woda nie podnosi się już więcej ponieważ się przelewa.
Mając dane wymiary akwarium, wysokości kolejnych klocków oraz ilość wody wlewanej do akwarium, należy podać do jakiej wysokości sięgnie woda, jeżeli będzie ona wlewana zgodnie z regułami podanymi w treści zadania.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajdują się trzy liczby całkowite W, H i L (1 ≤ W ≤ 30.000, 1 ≤ H ≤ 10.000.000, 1 ≤ L ≤ 1.000.000.000), oznaczające odpowiednio szerokość akwarium, wysokość akwarium oraz ilość wlewanych litrów wody. W kolejnych W wierszach znajdują się wysokości kolejnych klocków pi (1 ≤ pi ≤ H), które zostały włożone do akwarium. Należy założyć, że akwarium nie jest w pełni wypełnione klockami (tzn. co najmniej jeden klocek ma wysokość mniejszą od H).
Dla każdego zestawu testowego należy wypisać pojedynczy wiersz zawierający jedną liczbę rzeczywistą, będącą wysokością do której sięgnie woda przy zachowaniu reguł wymyślonych przez syna władcy ufoludków. Wynik należy podać z dokładnością do pięciu miejsc po przecinku.
3 1 2 2 1 2 3 1 2 1 3 5 4 2 4 1
2.00000 2.00000 3.50000