Starí KSPáci idú spoločne jedným autom na svadobnú cestu. Aby sa v stiesnených podmienkach vyhli hádkam, rozhodli sa, že si každý z nich zoberie vlastný box na občerstvenie. Zároveň chcú, aby mali všetci z jedla úplne rovnaký zážitok. To znamená, že každý box musí obsahovať presne rovnakú hmotnosť z každej pochutiny (napr. ak Adík dostane 300 g čokolády, potom aj Kristína, Sabinka a Marcel musia dostať presne 300 g čokolády). Okrem toho, aby im z cesty nebolo ťažko, celková hmotnosť všetkých pochutín v jednom boxe musí byť presne 1000 gramov.
Má to však háčik. Každý KSPák má iné prísne diétne obmedzenia a alergie, ktoré určujú, koľko gramov z ktorej pochutiny môže najviac bezpečne zjesť.
Zistite, či je možné vyskladať boxy s pochutinami tak, aby celková hmotnosť pochutín v každom boxe bola presne 1000 gramov, a zároveň aby žiaden KSPák nemal vo svojom boxe viac gramov niektorej pochutiny, ako dokáže bezpečne zjesť (všetci majú zloženie boxu rovnaké). Ak to je možné, navrhnite jedno takéto rozdelenie hmotností.
Na vstupe nájdete 4 riadky, každý pre jedného KSPáka (postupne pre Adíka, Kristínu, Sabinku a Marcela). Každý riadok obsahuje 4 medzerou oddelené celé čísla, ktoré určujú limity pre jednotlivé pochutiny v gramoch (postupne pre čokoládu, čipsy, oriešky a gumené medvedíky).
Napríklad tretie číslo na druhom riadku nám hovorí, koľko gramov orieškov môže najviac zjesť Kristína. Všetky tieto limity sú nezáporné a nepresahujú 2000.
Ak vhodné rozdelenie pochutín neexistuje, vypíšte jeden riadok a v ňom slovo NEMOZNE.
V opačnom prípade vypíšte jeden riadok a v ňom 4 nezáporné celé čísla, čiže hmotnosti
jednotlivých pochutín v gramoch (postupne pre čokoládu, čipsy, oriešky a gumené
medvedíky), ktoré sa majú nachádzať v každom z boxov. Ich súčet musí byť presne
1000. Ak existuje viacero správnych riešení, môžete vypísať ľubovoľné z nich.
500 500 500 1000
500 1000 500 500
1000 500 1000 2000
250 300 250 500
250 250 250 250
Keď poskladáme box tak, že doňho dáme 250 gramov z každej zo 4 pochutín, sumárna hmotnosť bude 1000 gramov. Zároveň vidíme, že v každom stĺpci (pre každú pochutinu) je u každého KSPáka limit aspoň 250 gramov, takže nikomu nebude zle.
Máme štyroch KSPákov a štyri pochutiny: čokoládu, čipsy, oriešky a gumené medvedíky. Každý KSPák má pre každú pochutinu maximálny počet gramov, ktorý môže zjesť. Všetci štyria musia dostať rovnaký box a celková hmotnosť boxu musí byť presne 1000 gramov.
Keďže všetci dostanú úplne rovnaký box, pre každú pochutinu platí, že jej hmotnosť v boxe nesmie prekročiť limit žiadneho z KSPákov. Inak povedané, z čokolády môžeme dať do boxu najviac toľko gramov, koľko zvládne najcitlivejší KSPák, čiže minimum z jej štyroch limitov. To isté platí pre čipsy, oriešky aj gumené medvedíky. Tieto štyri minimá si označme $m_{čoko}, m_{čipsy}, m_{oriešky}, m_{medvedíky}$.
Tým sa celý problém zjednoduší na nasledujúcu otázku: vieme zvoliť štyri nezáporné celé čísla $x_{čoko}, x_{čipsy}, x_{oriešky}, x_{medvedíky}$ tak, aby $x_{čoko} \leq m_{čoko}$, $x_{čipsy} \leq m_{čipsy}$, $x_{oriešky} \leq m_{oriešky}$, $x_{medvedíky} \leq m_{medvedíky}$ a zároveň $x_{čoko} + x_{čipsy} + x_{oriešky} + x_{medvedíky} = 1000$?
Ak $m_{čoko} + m_{čipsy} + m_{oriešky} + m_{medvedíky} < 1000$, tak je to nemožné. Aj keby sme pre každú pochutinu použili jej maximum, neposkladáme dosť gramov. Naopak, ak $m_{čoko} + m_{čipsy} + m_{oriešky} + m_{medvedíky} \geq 1000$, vieme vždy rozdelenie nájsť.
Ak je súčet miním aspoň 1000, postupujeme pažravo: prechádzame pochutiny jednu po druhej a pri každej zoberieme toľko gramov, koľko ešte potrebujeme, ale najviac jej minimum:
To, že $r$ na konci bude naozaj $0$, je zaručené tým, že $m_{čoko} + m_{čipsy} + m_{oriešky} + m_{medvedíky} \geq 1000$.
Prečítame $4 \times 4 = 16$ čísel, pre každú zo $4$ pochutín nájdeme minimum zo $4$ hodnôt, a potom váhy pažravo rozdelíme. Časová aj pamäťová zložitosť je $O(1)$, keďže veľkosť vstupu je fixná.
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