Algoritmizace B4B33ALG
Algoritmizace

Testování čerpadla

Zadání

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.

img1.png
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říklady

Příklad 1

Vstup
12
4
3
5
2
4
5
4
6
2
3
4
2
Výstup
7 2

Data a řešení příkladu 1 jsou znázorněna na obrázku 1.

Příklad 2

Vstup
16
1
2
0
3
5
8
8
8
6
8
2
3
7
0
7
7
Výstup
9 1

Příklad 3

Vstup
18
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