Testování čerpadla
Firma Pump and Pump, Ltd. bude testovat mohutné vodní čerpadlo, které bude použito při plánovaném rozšiřování Panamského kanálu v příštím desetiletí. Testování probíhá podle následujícího scénáře.
K čerpadlu se připojí generátor a čerpadlo se spustí. Dále se v půlhodinových intervalech připojují postupně po jednom další generátory, čímž se dosáhne značného výkonu čerpadla. Po půlhodině provozu s maximálním počtem připojených generátorů se opět generátory postupně v půlhodinových intervalech po jednom odpojují až do úplného vypnutí celého zařízení.
Během testování musí stav každého připojeného generátoru sledovat jeden vyškolený technik specialista, což znamená, že v každém okamžiku testování musí běh sledovat tolik specialistů, kolik je právě k čerpadlu připojených generátorů. Uvedení pracovníci však mají ve firmě i další povinnosti, a proto je jich často k dispozici jen omezený počet.
Vedoucímu testování se podařilo sestavit rozvrh, ve kterém je pro každou půlhodinu v potenciálním testovacím období zanesen počet specialistů, kteří v danou půlhodinu budou moci sledovat běh generátorů. Zbývá nyní vybrat co nejdelší časový interval, v němž bude možno realizovat pokusný běh testovaného čerpadla.
Obrázek 1. Situace, kdy jsou počty volných specialistů v po sobě jdoucích půlhodinách dány posloupností (4, 3, 5, 2, 4, 5, 4, 6, 2, 3, 4, 2). Počty dostupných specialistů jsou znázorněny schematicky histogramem na obrázku 1a). Obrázky 1b) a 1c) ukázují, že nejdelší možná testovací doba čerpadla je 7 půlhodin, přičemž tuto dobu lze volit dvěma způsoby. Čísla v histogramu v popředí na obrázku 1b) a 1c) odpovídají počtu specialistů monitorujících běžící generátory. Data odpovídají příkladu 1 níže. |
Úloha
Je dána posloupnost celých nezáporných čísel představující počet volných specialistů v jednotlivých po sobě jdoucích půlhodinách. Určete délku nejdelšího intervalu, v němž může být realizováno testování čerpadla při dodržení uvedených podmínek. Určete také, kolik takovýchto intervalů nejdelší délky existuje.
Vstup
První řádek obsahuje jedno kladné celé číslo N, představující počet půlhodin v potenciálním testovacím období. Dále je na vstupu seznam počtu volných specialistů v jednotlivých půlhodinách v pořadí od začátku potenciálního testovacího období. Seznam zabírá N vstupních řádků, na každém řádku je uveden jeden prvek seznamu, který je nezáporným celým číslem.
Platí N ≤ 3 × 106, všechny další vstupní hodnoty nepřesáhnou N.
Výstup
Na výstupu je jeden textový řádek s dvěma čísly oddělenými mezerou, udávající postupně maximální možnou dobu testování čerpadla vyjádřenou v půlhodinách, a počet možností, jak testování maximální délky uskutečnit.
Příklad 1
Vstup12 4 3 5 2 4 5 4 6 2 3 4 2
Výstup
7 2Data a řešení příkladu 1 jsou znázorněna na obrázku 1.
Příklad 2
Vstup16 1 2 0 3 5 8 8 8 6 8 2 3 7 0 7 7
Výstup
9 1
Příklad 3
Vstup18 5 5 3 2 5 5 5 5 5 5 5 5 5 5 3 4 5 5
Výstup
9 7
Veřejná data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při
každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu
pro každý soubor veřejných dat.
Veřejná data