P - ParašutistiČasový limit: 1s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Herný priemysel má za sebou dlhý vývoj. Začiatkom 90-tych rokov boli v našom regióne veľmi populárne digitálne hry (najmä ruskej produkcie). Jedna z nich mala názov Parašutisti. Myšlienka hry bola jednoduchá. Vrtuľník zhadzoval parašutistov nad riekou plnou pažravých rýb. Aby parašutista prežil, nesmel pristáť vo vode. Na rieke plával čln, ktorý zachraňoval parašutistov pred pádom do vody. Čln bol ovládaný hráčom. Za každého zachráneného parašutistu bol jeden bod. Ak traja parašutisti skončili vo vode (t.j. nepristáli v člne), hra končila. Technické možnosti vtedajšej doby sa prejavili aj v hrách. Napríklad čln sa mohol nachádzať len na niekoľkých pozíciach. Hra prebiehala v diskrétnych časových krokoch. V rámci každého kroku sa loď mohla posunúť o jednu pozíciu vľavo alebo vpravo (alebo ostala stáť na mieste). Nuž a ani tie generátory náhodných čísel (určujúce kedy a kam parašutista dopadne) neboli vždy super náhodné. ÚlohaPoznáme časy a pozície dopadov jednotlivých parašutistov. Vytvorte program, ktorý vypočíta koľko najviac bodov môžeme získať. Upozorňujeme, že hra končí akonáhle nezachránime určený počet parašutistov.VstupPrvý riadok obsahuje trojicu medzerou oddelených čísel N, M a K, kde N (1 ≤ N ≤ 50000) je počet parašutistov, M (1 ≤ M ≤ 100) je počet pozícii člna a K (1 ≤ K ≤ 60) je počet nezachránených parašutistov, pri ktorom končí hra. Jednotlivé pozície člnu sú číslované od 0 po M-1. Ďalej bude nasledovať N riadkov popisujúcich pristátia jednotlivých parašutistov. Každý riadok obsahuje dvojicu medzerou oddelených čísel T (1 ≤ T ≤ 1000000) a P (0 ≤ P ≤ M-1). Číslo T určuje čas (počet diskrétnych časových krokov od začiatku hry), kedy parašutisti dopadá na hladinu. Číslo P určuje polohu, v ktorej sa parašutista pri dopade nachádza. Parašutisti sú na vstupe usporiadaný podľa času dopadu. V jednom čase môže dopadnúť aj viacero parašutistov.VýstupVypíšte maximálny počet bodov (zachránených parašutistov), ktorý je možné získať.PríkladVstup:40 30 4 63 27 86 9 188 17 293 0 334 3 384 17 413 15 426 5 512 29 614 15 648 29 675 2 728 14 833 3 848 1 915 15 1017 5 1113 6 1150 2 1177 0 1180 4 1280 10 1348 11 1441 6 1452 26 1513 26 1521 6 1533 14 1566 25 1652 25 1751 0 1793 26 1813 5 1833 0 1899 21 1972 4 2007 14 2046 26 2096 8 2102 20 Výstup:29 |