Zoznam úloh

4. Záhradka

Kolo už skončilo. Môžeš si pozrieť vzorové riešenie.

Kleofáša omrzelo kšeftovať s vysávačmi a rozhodol sa dať sa na farmárčinu. Krok jedna je samozrejme zohnať si záhradku, a na takú záhradku treba plot. Preto sa Kleofáš rovno vybral kúpiť tyčky a pletivo. A keďže mali skvelú zľavu na $$s$$ tyčiek, rovno ich kúpil. Následne si kúpil aj kozu, o ktorej vie, že potrebuje $$t$$ metrov štvorcových trávy. A teraz rozmýšľa, ako má vyzerať jeho záhradka, ak chce byť ekonomický – nenechať žiadne tyčky vyjsť navnivoč (t.j záhradka má mať práve $$s$$ rohov, teda aj $$s$$ strán) a dať koze práve $$t~\mathrm{m}^2$$ trávy. Zjavne ekonomickým metariešením je kúpiť si na vyriešenie tohto problému milého študenta

Úloha

Dané sú $$s$$ a $$t$$ také, že $$t \geq s/2$$. Kleofášova záhradka sa má dať nakresliť do štvorcovej siete (t.j. dĺžky strán musia byť celočíselné a všetky priľahlé kusy plotu musia byť na seba kolmé) a musí byť súvislá. Nájdite takú záhradku, ktorá má obsah $$t$$ a $$s$$ strán, alebo vypíšte “Neda sa”, ak sa to nedá.

Navyše v popise riešenia dokážte, že existuje nekonečne veľa dvojíc $$(s, t)$$, pre ktoré $$t < s/2$$ a napriek tomu takáto záhradka existuje.[^1]

Vstup

V jedinom riadku vstupu sú dve čísla: $$s$$ a $$t$$, pričom $$4\leq s\leq 10^3$$ a $$1\leq t\leq 10^6$$. Vždy platí, že $$t \geq s/2$$.

Výstup

Vypíšte $$s$$ riadkov: návod, ako má Kleofáš postaviť plot. Každý riadok je vo formáte $$S~D$$, kde $$S$$ je smer – jedno z písmen “S”, “J”, “V” a “Z” podľa svetovej strany a $$D$$ je dĺžka tohto kusu plota.

Záhradka musí byť uzavretá (teda musí skončiť tam, kde začala) a nasledujúce strany musia byť na seba kolmé.

Niektoré vstupy budú malé ($$s, t < 25$$). Pre niektoré vstupy platí $$t \geq s$$. Nejaké body teda získate aj za čiastkové riešenia.

Príklad

Input:

6 5

Output:

V 1
S 1
V 1
J 3
Z 2
S 2

Input:

9 12

Output:

Neda sa

  1. T.j. nájdite konštrukciu, ktorá funguje pre nekonečne veľa takých dvojíc.
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty