Úloha: Sklad - výběr nejlepších položek ve skladu
Velká zahraniční firma Stall & Fall inc. (S&F) chrlí každodenně do světa množství počítačově řízených ultralehkých letadel pro všechny druhy využití. Jedním z důležitých prvků jejího úspěchu je způsob, jakým počítače integruje s řídícími prvky svých letounů.Výroba je centralizována a všechny počítače jsou uloženy v jediném centrálním skladu, odkud jsou průběžně po jednom odesílány do výroby podle požadavků jednotlivých linek.
S&F má dlouhodobě uzavřen kontrakt s N dodavateli počítačů, a počítače odebírá výhradně od nich. Pro maximalizaci kvality svých výrobků firma S&F adoptovala následující strategii při osazování letounu počítačem. Kdykoli kterákoli linka požádá sklad o vydání počítače, sklad ji vždy dodá nejlepší počítač, který aktuálně má.
Rozhodování, který počítač je nejlepší, se děje podle více kriterií. Zaprvé ve skladu působí N znalců, každý z nich je orientován na právě jednoho dodavatele počítačů. Každý počítač, který do skladu dorazí, je ohodnocen příslušným znalcem. Znalec počítači přiřadí celé číslo, takzvanou charakteristiku, pomocí níž lze srovnávat počítače tohoto výrobce. Čím vyšší charakteristika, tím je počítač kvalitnější ve srovnání s ostatními počítači tohoto výrobce. Pokud dva počítače ve skladu pocházejí od různých výrobců, nelze je pomocí charakteristik nijak srovnávat. Každý znalec má svůj systém číslování, používá celá čísla a má pevně stanovenu minimální a maximální možnou hodnotu charakteristiky. Obě tato čísla mohou ležet v rozpětí od 1 do 2^30.
Výzkumné oddělení S&F zjistilo, že rozhodující jsou tři parametry každého počítače: střední doba chyby (t), odolnost proti výkyvům teploty (v) a mechanická robustnost (r). Ukázalo se, že pro každého dodavatele počítačů platí, že všechny jeho výrobky mají dlouhodobě stejnou hodnotu těchto parametrů. S vývojem software, izolačních materiálů a letových vlastností letadel však průběžně tyto parametry získávají různou váhu pro konstruktéry S&F . Výzkumné oddělení určuje kvalitu počítače pomocí lineární kombinace těchto tří faktorů. K tomu používá hodnotící formuli
kv(t, v, r) = a×t + b×v + c×r.
Čím je vyšší hodnota kv(t, v, r), tím je počítač považován za kvalitnější. Hodnoty parametrů a, b, c, se v čase mění a při každé změně sklad ihned obdrží jejich aktuální hodnoty.
Při porovnávání kvality dvou počítačů ve skladu rozhoduje nejprve hodnotící formule výzkumného oddělení s aktuálními parametry a potom, pokud je toho zapotřebí, charakteristika znalce. Tím je dáno, že lze vždy vybrat ve skladu nejkvalitnější počítač. (Speciální nerozhodné případy jsou probrány níže.)
Díky častým změnám v hodnotící formuli a nepravidelnému přísunu počítačů od dodavatelů se občas stává, že i při dodržení všech pravidel sklad vydává do výroby počítače, které jsou ve skutečnosti jejich znalci hodnoceny poměrně nízko. Oddělení kvality výroby proto chce vědět, kolikrát za sledované období taková situace nastala, to jest, kolikrát byl do výroby dodán počítač, který se umístil v dolní polovině stupnice charakteristik některého, nezáleží na tom, kterého, znalce. Například pokud znalec hodnotí počítače na stupnici od 2 do 8 včetně, sledovaná situace by nastala, kdyby do výroby putoval počítač s charakteristikou 2, 3 nebo 4. Nepočítá se umístění přesně v polovině, v tomto případě charakteristika 5.
Pokud hodnotící formule hodnotí stejně počítače různých výrobců, vybírají se vždy jako nejlepší počítače výrobce s nejvyšším pořadovým číslem. Pokud existuje ve skladu více počítačů, které jsou nejlepší podle hodnotící formule a zároveň mají stejnou charakteristiku znalce, vybírá se jako nejlepší kterýkoli z nich.
Počet výrobců nepřesahuje 1 000 000, kapacita skladu nepřesahuje 1 000 000 počítačů. Je zaručeno, že nedojde k přeplnění skladu, jedna zásilka výrobce však může obsahovat až počet počítačů rovnající se kapacitě skladu (např. na začátku sledovaného období). Ve skladu nemusí být zastoupeny počítače všech výrobců. Při každém požadavku výroby je ve skladu vždy alespoň jeden počítač.
Vstup
První řádek vstupu obsahuje jediné číslo, hodnotu N. Za ním následuje N řádků, každý řádek obsahuje čísla vztahující se k počítačům jednoho výrobce, výrobci jsou uvažováni v pořadí od 1 do N. Na řádku jsou uvedeny nejprve parametry t, v, r počítačů příslušného výrobce a za nimi následují dvě čísla určující nejmenší a největší možné hodnoty charakteristik znalce vyhodnocujícího počítače tohoto výrobce.Dále následuje seznam všech událostí za sledované období. Události mohou být trojího druhu, každá událost je specifikována na jednom řádku.
Událost označená 0 na první pozici řádku odpovídá aktuálnímu určení parametrů a, b, c hodnotící formule. Za mezerou následují tři celá čísla, a, b, c.
Událost označená 1 na první pozici řádku odpovídá přísunu počítačů od jednoho výrobce do skladu. Za mezerou je uveden identifikátor výrobce (1..N), pak počet dodaných počítačů a dále počet různých charakteristik, které těmto počítačům znalec přiřadil. Následuje (na témže řádku) seznam dvojic čísel x y, kde x určuje počet počítačů, které obdržely charakteristiku y. Dvojice jsou uvedeny v libovolném pořadí.
Událost označená označená 2 na první pozici řádku odpovídá přesunům nějakého počtu počítačů ze skladu do výroby. Za mezerou je jediné číslo, představující počet počítačů přesunutých ze skladu do výroby aniž mezi tím nastala jiná událost.
Seznam událostí je uzavřen řádkem s jediným číslem 3 na první pozici řádku.
Předpokládáme, že seznam událostí začíná událostí typu 0. Všechny hodnoty na každém řádku vstupu jsou odděleny jedinou mezerou. Všechny hodnoty na vstupu jsou nezáporné.
Výstup
Výstupem je jediné celé číslo udávající, kolikrát byl ze skladu do výroby dodán počítač, jehož příslušný expert hodnotil v dolní polovině své stupnice.Příklad
Vstup:2 1 2 3 10 20 3 2 1 100 220 0 1000 2000 4000 1 1 10 2 5 13 5 18 2 6 1 2 5 5 1 100 1 120 1 130 1 170 1 180 2 1 0 5000 1000 1000 2 4 3Vstup opakujeme s komentáři pro pohodlí čtenáře, datové soubory komentáře neobsahují.
2 // dve dodavatelske firmy 1 2 3 10 20 // 1. firma, t = 1, v = 2, r = 3, min char. 10, max char. 20 3 2 1 100 220 // 2. firma, t = 3, v = 2, r = 1, min char. 100, max char. 220 0 1000 2000 4000 // hodn. formule: a = 1000, b = 2000, c = 4000 1 1 10 2 5 13 5 18 // prislo 10 stroju firmy 1, 5 x char. 13 a 5 x char. 18 2 6 // 6 stroju do vyroby (od firmy 1) 1 2 5 5 1 100 1 120 1 130 1 170 1 180 // prislo 5 stroju firmy 2 s char. 100, 120, ... 2 1 // 1 stroj do vyroby (od firmy 1) 0 5000 1000 1000 // zmena hodn. formule: a = 5000, b = 1000, c = 1000 2 4 // 4 stroje do vyroby (od firmy 2, diky jine hodn. formuli) 3 // konecVýstup:
4
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.