Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť, ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máš hocijaké otázky k tejto úlohe, napíš Miškovi na [email protected].
Vedúci Prasku majú stretnutie, na ktorom vymýšľajú, aké úlohy budú v ďalšej sérii. V tom však zrazu všetkým chlapcom naraz začne byť treba ísť na záchod. Ale pomestia sa tam vôbec všetci? A ešte viac cool by bolo, keby sa tam dokázali postaviť tak, aby tam už nemohol prísť nikto ďalší a mali by záchody len pre seba!
Na záchode je vedľa seba niekoľko pisoárov a pri nich sa chce vycikať niekoľko vedúcich. Je ale veľmi neslušné postaviť sa k takému pisoáru, že tesne vedľa neho už niekto je.
Vedia sa vedúci postaviť k pisoárom tak, aby žiadni dvaja neboli tesne vedľa seba, ale aby ak tam príde ľubovoľný ďalší človek, tak už by sa musel postaviť vedľa niekoho? Ak áno, ako sa majú postaviť?
Na vstupe sú dve čísla – počet ľudí a počet pisoárov (oddelené medzerou).
Na výstup vypíš, ako sa majú vedúci postaviť.
Teda reťazec zo znakov X a -: X znamená, že pri tom pisoáre stojí vedúci,
a -, že pri pisoáre nikto nestojí.
Ak sa to nedá, vypíš neda sa.
Sú 4 sady vstupov, za každú je 25 bodov. V jednotlivých sadách:
| sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| počet pisoárov $\leq$ | $5$ | $10$ | $500$ | $100\,000$ |
2 5
-X-X-
Máme $5$ pisoárov a $2$ vedúcich. Ak sa postavia k tým dvom stredným, tak už sa tam nikto ďalší nezmestí, lebo by bol tesne vedľa aspoň jedného vedúceho.
1 5
neda sa
Nech sa jeden vedúci postaví hocikde, vždy tam bude dostatok miesta.
Vzoráky z tohto kola si môžeš pozrieť aj ako video
Keď chceme, aby nejaký počet ľudí obsadil čo najmenej pisoárov, môžeme ich dávať čo najviac natesno:
$$ \begin{array}{} X & - & X & - & X & \cdots & X & - & X \end{array} $$
Takto, ak máme $n$ ľudí, tak obsadíme najmenej $2n - 1$ pisoárov. Naopak, keď chceme obsadiť pisoárov čo najviac, môžeme dávať čo najviac natesno prázdne miesta:
$$ \begin{array}{} - & X & - & - & X & \cdots & - & X & - \end{array} $$
V prvom prípade môžeme postupnosť miest vyskladať z dvojíc $\begin{array}{} X & - \end{array}$ a v druhom z trojíc $\begin{array}{} X & - \end{array}$. Keď chceme niečo medzi, môžeme dať niekoľko trojíc a niekoľko dvojíc. Tie vždy obsadia všetky pisoáre, takže ich stačí dať toľko, aby bol pisoárov správny počet.
Keď máme dvakrát toľko pisoárov ako ľudí, tak tam môžeme dať samé dvojice (a prípadne jedného človeka na koniec, ak je pisoárov nepárny počet). Inak môžeme postupne dávať trojice, až kým nám nebude ostávať taký počet pisoárov a ľudí, že ich vyplníme dvojicami.
Vieme takto dostať všetky počty pisoárov medzi tými dvoma krajnými prípadmi? Predstavme si, že na začiatku spravíme samé dvojice. To nám obsadí niekoľko pisoárov, ale ak ostanú nejaké voľné, tak môžeme vymeniť jednu dvojicu za trojicu. Tak pri rovnakom počet ľudí obsadíme o jeden pisoár viac. Keď toto budeme opakovať, dostaneme pri danom počet ľudí všetky počty pisoárov, až pokým nebudeme mať samé trojice.
A nevieme dostať aj iné počty? Predstavme si, že by sme mali $n$ ľudí a menej než $2n - 1$ pisoárov. Pisoáre si rozdelíme na skupinky po dvoch (a prípadne jeden samotný na konci):
$$ \begin{array}{cc|cc|c|cc|c} - & - & - & - & \cdots & - & - & -\phantom{X} \end{array} $$
Skupiniek je potom menej ako ľudí, takže v nejakej skupinke musia byť dvaja ľudia a tí budú vedľa seba.
Naopak, každý človek obsadí najviac $3$ miesta (svoje a tie dve susedné), takže keď je pisoárov viac ako trojnásobok ľudí, tak je určite nejaké miesto voľné. Iné počty sa teda nedajú.
este_ludi, este_pisoarov = map(int, input().split())
if este_pisoarov < 2 * este_ludi - 1 or este_pisoarov > 3 * este_ludi:
print("neda sa")
else:
while 2 * este_ludi < este_pisoarov:
print("-X-", end = "")
este_ludi -= 1
este_pisoarov -= 3
print("X-" * (este_pisoarov // 2) + "X" * (este_pisoarov % 2))