Zadanie

Fatima na doučovaní

Počet bodov: 40, časový limit: 1000ms

Fatima na hodine informatiky nedávala pozor, a teraz nevie, ako funguje efektívny algoritmus na nájdenie \(k\) najväčších čísel. Dohodla si teda doučovanie.

Teraz je pred ňou učiteľka a diktuje jej \(n\) čísel, z ktorých má Fatima vybrať a povedať \(k\) najväčších. Avšak, Fatima má slabú pamäť, veľkosti iba \(1\) kilobajt, a všetkých \(n\) čísel sa jej do pamäte určite nezmestí. Môže ale učiteľku požiadať, aby celú postupnosť čísel zopakovala. To samozrejme učiteľku irituje, ale tak čo narobí. Hlavne nech to Fatime netrvá pridlho…

Úloha

Toto je interaktívna úloha, a váš program bude hrať rolu Fatimy. Má k dispozícii iba \(4\) kilobajty pamäte. Na začiatku sú na vstupe iba čísla \(n\) a \(k\): počet všetkých čísel, a koľko najväčších z nich máte vypísať.

S učiteľkou (testovačom) viete komunikovať pomocou štandardného výstupu. Keď vypíšete riadok este raz, na vstup vám testovač pošle riadok so všetkými \(n\) číslami, oddelenými medzerou. Je zaručené, že vám ich vždy pošle v rovnakom poradí. Čísla na vstupe sú nezáporné, menšie alebo rovné \(10^9\), a sú navzájom rôzne.

Keď už ste si istí tým, že niektoré číslo \(x\) patrí medzi prvých \(k\) najväčších, vypíšte na výstup jeden riadok velke <x>. Po vypísaní \(k\)-teho riadku tohto tvaru by váš program mal skončiť.

Nezabudnite, že keďže je táto úloha interaktívna, po každom vašom výstupe flushnite, aby sa objavil hneď na vstupe pre testovač. (V C++ funguje cout << flush, v Pythone print(..., flush = True).)

Je \(6\) testovacích sád, s nasledovnými obmedzeniami: - V sadách \(1\) a \(2\) je \(n\) postupne rovné \(1\,000\) a \(10\,000\). V ostatných sadách je \(n = 100\,000\). - V sadách \(1\) až \(3\) je \(k \leq 100\). V sadách \(4, 5, 6\) postupne platí \(k \leq 1\,000\), \(k \leq 10\,000\) a \(k \leq 100\,000\).

Príklad

10 5
> este raz
4 3 17 2 1 6 13 9 5 7
> velke 6
> velke 17
> este raz
4 3 17 2 1 6 13 9 5 7
> velke 13
> velke 7
> velke 9

Riadky začínajúce > sú výstupy nášho programu, ostatné riadky sú výstupy z testovača (vstup do nášho programu). Všimnite si, že sa môžeme spýtať este raz aj po tom, čo sme pre niektoré číslo povedali velke.