G - Goool

Časový limit: 7s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Trenej futbalovej reprezentacie Slovenska si uz niekolko tyzdnov lame hlavu. Jeho zverenci nepodavaju take vysledky, ake by si zelal. Preto sa rozhodol zmenit treningovu strategiu. Niekde na polici vyhrabal kopu zbierok s roznymi variantami treningov. Zbierky boli vydane v rokoch, kedy este ceskoslovensky futbal slavil uspechy, preto je jasne, ze ked zacnu hraci trenovat podla nich, uspechy sa opat dostavia. Na kazdom liste takej zbierky je rozpisana jedna strategia. Strategie sa lisia podla poctu zapojenych hracov a obtiaznosti. Trener si vie vypocitat obtiaznost kazdej strategie. No v knihe je ich strasne vela. To by jeho zverenci urcite nezvladli. Rozhodol sa preto niektore zo zbierky vytrhnut a potom takto upravene zbierky rozdat hracom. Bol by rad, keby v zbierke ostali strategie zoradene podla obtiaznosti od najjednoduchsej po najtazsiu. (Trener nemoze menit poradie v knihe, moze len vytrhat niektore stranky) Zela si, aby ziadne dve strategie nemali rovnaku obtiaznost. Takze v zbierke ostane len podla obtiaznosti rastuca postupnost. No taktiez by bol rad, aby v zbierke ostalo listov co najviac. Pomozte mu. (Ak sa pytate, preco nemoze len napisat poradie treningov miesto ich trhania, tak odpoved je jednoducha. Ma iste pochybnosti, ci by to jeho zverenci psychicky a intelektualne zvladli.)

Uloha

Vasou ulohou je nacitat strategie tak, ako nasleduju v zbierke. Pre kazdu je potrebne vypocitat jej obtiaznost. Ked uz budete mat vypocitane obtiaznosti vsetkych strategii, vyberte iba tie, ktore tvoria rastucu postupnost. Vyberte najdlhsiu moznu takuto postupnost a vypiste len jej dlzku. Obtiaznost strategie sa vypocita nasledovne: Hracie pole je po dlzke rozdelene do usekov. Usek hned pri branke ma cislo 1, dalsi ma cislo 2 a takto az k druhej branke. Kazda strategia ma iny pocet usekov, no nikdy ich nie je viac ako 20. Na kazdom useku moze stat viac hracov, alebo ani jeden. Kazdy hrac ma okrem cisla useku na ktorom stoji aj vzdialenost od praveho okraja ihriska (pravy okraj z pohladu brankara stojaceho v branke). Ked si predstavite cislo useku ako x-ovu suradnicu hraca, tak vzdialenost od okraja je y-ova suradnica. Tato vzdialenost je vzdy v rozmedzi 1 az 100. Na zaciatku ma loptu hrac, ktory stoji v najvzdialenejsom useku od branky a je najblizsie k pravemu okraju. Ziadni dvaja hraci nestoja na tom istom mieste (teda nemaju rovnake cislo useku a aj vzdialenost). Hrac moze vzdy nahrat loptu iba hracovi, ktory stoji v useku blizsom k branke, no vzdy musi nahravat cez co najmensi pocet usekov. Teda ak stoji nejaky hrac hned vo vedlajsom useku, tak musi nahrat jemu. Ak uz nie je ziaden hrac v useku blizsom branke, tak hrac vystreli. Ak je v nejakom useku viac hracov, tak nahravka smeruje tak, aby rozdiel vzialenosti od praveho okraja ihriska medzi adresatom a nahravajucim hracom bol co najvacsi. Ak je rozdiel vzdialenosti k dvom hracom rovnaky, prihravka smeruje na hraca, ktory ma mensiu vzdialenost od praveho okraja. Teda ak hrac s loptou stoji v sekcii 2 a jeho vzdialenost od praveho okraja je 5 a v sekcii 1 stoja dvaja hraci na poziciach 1 a 8, tak hrac nahra na hracovi na pozicii 1, lebo rozdiel vzdialenosti medzi 5 a 1 je 4 a medzi 5 a 8 je len 3. Tento rozdiel vzdialenosti od praveho okraja nazveme dlzka prihravky. Je vidiet, za takymto postupom je vzdy mozne jednoznacne urcit priebeh celej strategie. Jej obtiaznost je sucet dlzok vsetkych jej prihravok od prveho hraca az po kopnutie na branku (uz samotne kopnutie sa do obtiaznosti nepocita, teda ide len o nahravky od prveho hraca k poslednemu). Ukazme si to na priklade:

Suradnice hracov su nasledovne (od hraca 1 po hraca 8): [4,1], [4,9], [3,2], [3,7], [2,1], [2,10], [1,2], [1,7]. Na zaciatku ma loptu hrac 1, kedze je najdalej od branky a ma aj mensiu vzdialenost od praveho okraja (na obrazku dole) ako hrac 2. Ten moze nahrat loptu hracovi 3 alebo 4, no vyberie si hraca 4, lebo rozdiel je 6 a to je viac ako 1. Hrac 4 moze nahrat hracovi 5 alebo 6, ale vyberie si hraca 5, lebo rozdiel je 6 a to je viac ako 3. Hrac 5 si vyberie hraca 8, rozdiel je 6. Hrac 8 uz nema komu nahrat, preto vystreli na branu. Obtiaznost tejto strategie je teda 18.

Vstup

Prvy riadok vstupu obsahuje cele kladne cislo N, pocet listov v knihe, 1 ≤ N ≤ 100. Dalej nasleduje N strategii, kazda obsahuje riadok s poctom hracov M, 1 ≤ M ≤ 100. Dalej nasleduje M riadkov, kazdy obsahuje 2 cisla, sekciu a vzdialenost od praveho okraja. Sekcie su cislovane od 1 po 20 a vzdialenosti od 1 po 100. Poradie hracov nie je nijako usporiadane!

Vystup

Vypiste jedine cislo, maximalny pocet stran, ktore mozu ostat v zbierke.

Priklad

Vstup:

Vystup:

Vysvetlenie:

Prva strategia bola spominana v priklade vyssie, jej obtiaznost je 18. Obtiaznost druhej strategie je 9 a tretej 99. Najdlhsia rastuca postupnost strategii je teda bud 18,99 alebo 9,99. Dlzka je teda 2.

Problem by Samuel BWPOW Kupka

DS2004