Domácí kolo

D: Rybníčky

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Na Venuši nastalo období dešťů. Kalné kapky sycené oxidem sírovým se slévají do potůčků a pomalu zaplňují venušský protipovodňový systém. Přežijí to Venušané, nebo bude kolonie zaplavena a zničena?

Je dáno N rybníčků s objemy v1,...,vN (litrů) a do každého přitéká 1 (litr za sekundu). Jakmile je nějaký rybníček plný, začne veškerý jeho přítok přetékat do následujícího rybníčku. Voda, která vytéká z posledního rybníčku, odtéká pryč a už nepřitéká do žádného rybníčku. Určete dva časy: Za jak dlouho přeteče poslední rybník? Za jak dlouho budou všechny rybníky plné?

Tvar vstupu

Na prvním řádku je číslo T označující počet problémů, které musíte vyřešit. Každý problém je popsán dvěma řádky, přičemž první z nich obsahuje číslo N (počet rybníčků) a druhý N čísel v1,..., vN (objemy rybníčků).

Tvar výstupu

Pro každý problém vypište na jeden řádek dva časy (v sekundách) zaokrouhlené na dvě desetinná místa a oddělené mezerou. První čas říká, za jak dlouho přeteče poslední rybníček. Druhý udává, za jak dlouho budou všechny rybníčky naplněny.

Poznámka: Zaokrouhlením se myslí to standartní základoškolské. Zaokrouhlení na dvě desetinná místa znamená vzít celou část zaokrouhlovaného čísla spolu s posledními dvěma destetinnými místy a přičíst 0.01 pokud je třetí desetinná cifra mezi 5 až 9. Většina programovacích jazyků umí takto zaokrouhovat pomocí formátování textu. V pythonu '{:.2f}'.format(n), v céčku printf("%.2f", n); v c++ cout<<fixed<<setprecision(2)<<12.5555<< endl;

Novinka:

Všimli jsme si, že máte problémy se zaokrouhlováním. Zadání jsme upravili a nyní je možné odevzdávat bez zaokrouhlování. Výstup vypište zaokrouhleně anebo nezaokrouhleně s přesností alespoň na 3 desetinné místa.

Lehká verze

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 1000
  • 1 ≤ vi ≤ 100 000 000

Těžká verze

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ vi ≤ 100 000 000

Ukázkový vstup

2
4
20 1 1 6
3
1 3 5

Ukázkový výstup

2.67 20.00
3.00 3.00

Vysvětlení ukázkového výstupu

V první úloze po první sekundě začnou přetékat prostřední dva rybníčky do posledního 6 litrového, ve kterém je tou dobou už 1 litr. V posledním rybníčku tedy zbývá 5 litrů místa, a přitékají do něho nyní 3 litry za sekundu. Přeteče za 5/3 sekundy = 1.666... což je 2.666... sekund od začátku. Zaokroulíme a máme první čas: 2.67. Ve 20-té sekundě přeteče i první rybníček, čímž jsou včechny rybníčky plné. Vypíšeme 20.00.

Ve druhé úloze v první sekundě začně přetékat první rybníček, ve druhé sekundě druhý rybníček a ve třetí sekundě třetí rybníček. Čas přetečení posledního rybníčku je tedy roven času přetečení všech rybníčků. Vypíšeme 3.00 3.00.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)