Zadanie
Lukáš je mladý a nadšený lyžiar, preto sa rozhodol zúčastniť sa pretekov v zjazdovom lyžovaní, ktorých sa zúčastnilo \(n\geq17\) pretekárov. Preteky sa skladali z \(5\) kôl, každý deň od pondelka do piatka prebehlo jedno kolo. V pondelok skončil Lukáš na \(17\). a v utorok na \(15\). mieste. V stredu sa dostal na \(14\). miesto. Vo štvrtok trochu znervóznel a skončil na \(16\). mieste. V piatkovom, poslednom, zjazde sa Lukášovi darilo o trochu viac a skončil na \(13\). mieste. Na konci bolo všetkých \(n\) pretekárov zoradených do celkového poradia podľa súčtu časov za všetkých päť kôl. V závislosti od \(n\) zistite, ako najlepšie mohol Lukáš skončiť v celkovom poradí.
Máme zistiť, ako najlepšie sa mohol Lukáš umiestniť, takže koľko najviac ľudí mohlo mať väčší súčet časov za päť dní. Je zrejmé, že ak sa niekto každý deň umiestnil pred Lukášom, mal každý deň kratší čas, teda aj celkovo bol rýchlejší a Lukáš ho nepredbehol ani v celkovom poradí.
Relevantní sú pre nás tí ľudia, ktorých Lukáš v niektorom kole predbehol. Na to, aby Lukáš v celkovom poradí mohol poraziť nejakého pretekára, mu stačí predbehnúť ho v jediný deň, pokiaľ si Lukáš spraví dostatočný náskok. Ak je napríklad Lukášov celkový súčet časov \(L\), stačí ak pretekár, ktorého predbehne, má v daný deň čas väčší ako \(L\), a už bude mať určite väčší čas aj v celkovom poradí. (pre lepšiu predstavu, nech Lukáš má celkový čas za \(5\) dní \(10\) sekúnd a pretekár, ktorého predbehne v jeden deň, má v ten deň čas \(1\) minútu.) Chceme, aby čo najviac ľudí bolo v celkovom poradí za Lukášom. To dosiahneme, to dosiahneme, ak každý deň skončia za Lukášom iní ľudia, resp. nikto nebude Lukášom porazený \(2\)-krát, kým Lukáš každého neporazí aspoň raz. Ešte všeobecnejšie, Lukáš nikoho nepredbehne \((n+1)\)-krát, pokiaľ každého nepredbehne \(n\)-krát.
Vezmime si \(n=17\). V prvom kole Lukáš predbehol \(0\) pretekárov, v druhom \(2\), v treťom \(3\), vo štvrtom \(1\) a v piatom \(4\). V takomto prípade je v celkovom poradí za Lukášom \(2+3+1+4=10\) ľudí, čo znamená, že Lukáš mohol byť najlepšie na \(7\). mieste.
Pre \(n=18\) je situácia podobná. V prvom kole Lukáš predbehol \(1\) pretekára, v druhom \(3\), v treťom \(4\), vo štvrtom \(2\) a v piatom \(5\). Najviac teda mohol predbehnúť \(15\) pretekárov a umiestniť sa na \(3.\) mieste.
Pre \(n=19\) Lukáš celkovo predbehol \(2+4+5+3+6=20\) pretekárov, čo znamená, že každého mal možnosť poraziť aspoň raz, niektorých dokonca 2-krát, takže sa mohol umiestniť na prvom mieste. Rovnako to platí aj pre \(n\geq19\), pretože Lukáš mal v priebehu piatich dní možnosť obehnúť \((n-17) + (n-15) + (n-14) + (n-16) + (n-13)=5n-75=n+4n-75\geq n+4\cdot19-75=n+76-75>n-1\) pretekárov, čiže určite mohol každého obehnúť aspoň raz.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.