Vedúci KSP sú hladní a nevedia sa dočkať, kedy konečne bude obed hotový. Krtko dostal extrémne dobrý nápad, že si poskladá robota, ktorý nám bude pripravovať obedy, aby to netrvalo tak dlho. Po dlhej chvíle pozerania rôznych možností na e-shopoch sa rozhodol, že najefektívnejšie bude si kúpiť továrenské pásy z Bazošu a tie zapojiť za seba. Pásy samozrejme nestačia – potrebujeme robotov, ktorý ten samotný obed budú pripravovať, kým sa vozí na páse. Zároveň sa krtkovi podarilo na matfyze vybaviť miestnosť, kde sa nám tento dlhý pás zmestí.
Máme miestnosť, ktorá je dlhá $l$. Na začiatku miestnosti máme kopu prázdnych tanierov na ktoré potrebujeme pripraviť obedy. Na to aby bol obed hotový, potrebuje, aby počas prípravy prešiel cez aspoň $r$ robotov. Zároveň potrebujeme zaručiť, aby došiel presne na koniec miestnosti, kde je výdajné okienko. Na bazoši je viacero inzerátov s rôznymi pásmi – každý z nich má nejakú priepustnosť $p$ (koľko obedov za hodinu vie tento pás previesť), dĺžku $d$ a buď pri tomto páse je, alebo nie je robot.
Zistite, ktoré pásy má Krtko kúpiť, aby jeho výtvor vedel pripravovať obedy čo najrýchlejšie.
V prvom riadku vstupu sú 3 čísla $n$ ($1 \leq n \leq 1000$), $l$ ($1 \leq n \leq 10^5$), $r$ ($1 \leq r \leq n$) udávajúce počet inzerátov na bazoši, dĺžku miestnosti a to koľko robotov potrebujeme na prichystanie obedu.
Potom nasleduje $n$ riadkov –
popis jednotlivých inzerátov. Pre každý inzerát máme 3 hodnoty $d_i$, $p_i$ ($1 \leq
p_i \leq 10^6$), $r_i$. $d_i$ je dĺžka pásu na tomto inzeráte,
$p_i$ je jeho priepustnosť a $r_i$ je A ak tento pás
obsahuje robota a N ak nie.
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq N \leq$ | $20$ | $100$ | $700$ | $700$ |
| $1 \leq l \leq$ | $500$ | $10^4$ | $25\,000$ | $25\,000$ |
Navyše v 3. sade je $r = 0$, teda netreba žiadnych robotov.
Na výstup vypíš jedno číslo - najväčšiu priepustnosť, ktorú vie mať pás dlhý presne $l$ a s aspoň $r$ robotmi.
Ak pás zostrojiť nevieme, tak vypíš -1.
Input:
4 100 0
40 1500 N
60 700 A
25 850 N
35 2700 A
Output:
850
Najviac sa oplatí kúpiť prvý, tretí a štvrtý pás. Mohli by sme aj prvý a druhý, ale potom by sme mali menšiu priepustnosť
Input:
3 200 2
100 1700 N
100 1500 A
100 1300 A
Output:
1300
Musíme použiť všetky pásy s robotmi, inak nevieme pripraviť obed
Input:
1 100 0
110 4747 A
Output:
-1
Jediný inzerát, čo máme nám ponúka až príliš dlhý pás - nezmestí sa nám do miestnosti
Prvé, čo si vieme všimnúť, je to, že nezáleží na poradí v akom budeme pásy umiestňovať.
Ak riešenie existuje, tak musí existovať nejaká podmnožina pásov, ktoré používa. Teda stačí skúsiť všetky podmnožiny a vybrať z nich tú najlepšiu. Toto riešenie bude mať časovú složitosť $O(2^n)$, lebo máme $n$ pásov a pre každú podmnožinu pásov musíme skúsiť, či spĺňa podmienky.
Tým, že chceme čo najväčšiu priepustnosť, tak môžeme postupne skúšať to vyrobiť z stále horších pásov. Teda pásy si vieme zoradiť od najviac priepustných po najmenej priepustné. Potom ak budeme pridávať pásy od najviac priepustných, tak vieme, že ak nájdeme riešenie, tak musí byť optimálne.
Postupne si generujeme všteky kombinácie pásov. Pre každú si pamätáme jej dĺžku a počet robotov. Vždy keď pridáme nový pás, tak prejdeme cez všetky predošlé kombinácie a ku každej z nich spravíme novú kombináciu, ktorá má už nový pás napojený. Ak je pás moc dlhý vieme túto kombináciu ignorovať - nemôže viesť k správnemu riešeniu. Zároveň, ak máme viac ako $r$ robotov v nejakej kombinácii, tak je to identické ako keby sme mali tých robotov práve $r$. Celkovo teda máme $O(lr)$ kombinácii. Pri každom pridaní nového pásu musíme cez všetky prejsť. Takže časová zložitosť bude $O(nl*r)$.
Od optimálneho riešenia nás delí iba jedno pozorovanie - ak vieme spraviť pás dlhý $200$, ktorý má $4$ robotov alebo pás dlhý $200$, ktorý má $2$ robotov, tak tá prvá možnosť je lepšia. Ak bude totiž riešenie existovať využívajuce druhú kombináciu, tak musí existovať aj iné, ktoré využíva prvú. Naopak to však neplatí. Čiže nám stačí len pre každú dĺžku $x$ vedieť na koľko najviac robotov vieme vyskladať pás dlhý $x$. Nadpájanie bude fungovať tak, že pre všetky dĺžky tento pás napojíme, ak to ide a aktualizujeme maximálny počet robotov na novej dĺžke. Naraz si teda pamäťáme iba $l$ čísel - maximálne počty robotov. Každý nový pás vyriešime jedným prejdením týmto poľom. Časová zložitosť bude $O(n*l)$.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete