Keďže v každom rohu obvod Kleofášovej záhradky zatáča o 90 stupňov, musia sa na obvode striedať vodorovné a zvislé strany. Vodorovných strán je teda presne toľko isto ako zvislých. Inými slovami, počet strán záhradky musí byť párny. Pre všetky vstupy s nepárnym $$s$$ teda môžeme smelo odpovedať, že nemajú riešenie.

Následne ošetríme okrajové prípady: $$t=1$$ aj $$t=2$$ sú možné len ak $$s=4$$. (V prvom prípade tvorí záhradku jeden štvorec, v druhom prípade sú to nutne dva stranou susediace štvorce. Tvar obvodu je v oboch prípadoch jednoznačne určený.) Odteraz teda môžeme predpokladať, že $$t\geq 3$$.

Ako ďalší krok nášho riešenia sa pozrieme na najmenší povolený prípad: situáciu kedy $$s=2t$$. Chceme teda nakresliť útvar s $$2t$$ stranami a obsahom $$t$$.

Ako to bude vyzerať pre $$t=3$$? Ak má mať záhradka tri štvorce, môžu byť buď v rade za sebou (vtedy má ale obvod len štyri strany), alebo môžu byť zatočené “do L” (kedy je strán 6, čo je presne to, čo sme chceli).

`+---+
|   |
|   +---+   <-- 6 strán, obsah 3
|       |
+-------+`

Ďalej máme $$t=4$$. Tu chceme útvar, ktorý bude mať 8 strán. Ideálne by bolo neriešiť úlohu odznova, ale skúsiť upraviť predchádzajúce riešenie – pridať nový štvorec tak, aby nám tým pribudli dve strany. A skutočne to ide spraviť. Jedna dobrá možnosť vyzerá nasledovne:

`+---+
|   |
|   +---+
|       |   <-- 8 strán, obsah 4
+---+   +
    |   |
    +---+`

No a už by malo byť aj jasné, že tento postup vieme ďalej “do nekonečna” opakovať. Pre názornosť sa ešte pozrime na $$t=5$$. Tam opäť pridáme jeden štvorec “na chvost hada”, čím sa nám obsah zväčší o 1 a počet strán o 2.

`+---+
|   |
|   +---+   <-- 10 strán, obsah 5
|       |
+---+   +---+
    |       |
    +-------+`

Takže už vieme riešiť všetky prípady kedy $$t\geq 3$$ a $$s=2t$$: jednoducho vyrobíme $$t$$-políčkového hada. Čo teraz so všeobecným prípadom? Predpokladajme, že $$s$$ je párne a že $$t = s/2 + x$$. Máme teda mať ten istý počet strán, ale o $$x$$ väčší obsah. Ako to dosiahnuť? Jednoducho – stačí napríklad nášmu hadovi “natiahnuť chvost”.

Riešenie si opäť ukážeme na jednom príklade, z ktorého bude jasné, ako to funguje vo všeobecnosti. Majme opäť $$s=10$$, ale tentokrát namiesto $$t=5$$ budeme mať $$t=8$$, teda o tri viac. Spravíme teda nášmu hadovi o tri dlhší chvost:

`+---+
|   |
|   +---+   <-- stále 10 strán, ale už obsah 8
|       |
+---+   +---------------+
    |         1   2   3 |
    +-------------------+`

Tu je implementácia tejto myšlienky:

import sys

S, O = [ int(x) for x in input().split() ]

if S%2 != 0 or S == 2:
    print("Neda sa")
    sys.exit(0)
if S == 4:
    print("S", 1)
    print("V", O)
    print("J", 1)
    print("Z", O)
else:
    chvost = O - S//2
    inner = S - 6
    Sd = inner

    print("Z", chvost+1)
    print("S", 1)
    print("V", chvost+2)
    dole = True
    while Sd > inner//2:
        print("J" if dole else "V", 1); Sd -= 1
        dole = not dole
    print("J" if dole else "V", 2 if dole else 1)
    print("Z" if dole else "J", 1)
    print("S" if dole else "Z", 1 if dole else 2)
    while Sd > 0:
        print("Z" if dole else "S", 1); Sd -= 1
        dole = not dole

Ako vyzerajú nejaké situácie s malým obsahom?

Okrem naprogramovania vyššie popísaného riešenia ste mali ešte jednu úlohu: ukázať, že existuje nekonečne veľa dvojíc $$(s, t)$$, pre ktoré $$t < s/2$$ a napriek tomu hľadaná záhradka existuje. Teraz sa pozrieme na to, ako takéto prípady vyzerajú.

Jeden už vlastne poznáme: $$t=1$$ a $$s=4$$, teda jediný štvorec. To je však patologický prípad, ktorý nevieme zovšeobecniť.

Po troche skúšania však ľahko odhalíme druhý najmenší prípad s obsahom menším ako $$s/2$$. Vyzerá nasledovne:

`    +---+
    |   |
+---+   +---+
|           |  <-- až 12 strán a obsah len 5
+---+   +---+
    |   |
    +---+`

A odtiaľ už ľahko pokračujeme k ďalším, väčším záhradkám s touto vlastnosťou. Tu je nasledujúca:

`    +---+   +---+
    |   |   |   |
+---+   +---+   +---+
|                   |  <-- až 20 strán a obsah len 9
+---+   +---+   +---+
    |   |   |   |
    +---+   +---+`

a už je asi jasné, ako to bude pokračovať ďalej. Tým sme splnili zadanú úlohu – našli sme nekonečne veľa rôznych záhradiek, ktorých obsah $$t$$ je menší ako polovica počtu ich strán.

Hlbšie zamyslenie na záver

Na záver tohto vzorového riešenia si ukážeme dôslednejšiu úvahu, ktorá nás privedie k tomu, ako musia vyzerať záhradky s veľkým počtom strán a malým obsahom.

Začneme tým, že si predstavíme ľubovoľnú záhradku s obsahom $$t$$. Namiesto počtu strán obvodu sa ale sústreďme na jeho dĺžku (pričom strana štvorca má dĺžku 1). Aký najdlhší obvod vieme dosiahnuť?

Máme $$t$$ štvorcov a každý z nich má 4 strany, čiže určite to nebude viac ako $$4t$$. V skutočnosti to ale musí byť ešte výrazne menej. Celá záhradka musí držať pokope, takže niektoré dvojice štvorcov musia susediť. No a vždy, keď dáme dva štvorce jeden vedľa druhého, zmenšíme tým obvod o 2 – ani z jedného ani z druhého už nie je na obvode ich spoločná strana. (Napr. dva izolované štvorce majú celkový obvod dĺžky 8, zatiaľ čo obdĺžnik $$1\times 2$$ má obvod dĺžky 6.)

Koľko dvojíc susediacich štvorcov musí byť v záhradke tvorenej $$t$$ štvorcami? Ľahko nahliadneme, že aspoň $$t-1$$. (Predstavme si, že záhradku ideme pozliepať dokopy z $$t$$ izolovaných štvorcov. Každým zlepením pozdĺž nejakej strany zmenšíme počet kusov o 1. Aby teda celá záhradka držala pokope, musíme lepiť aspoň $$t-1$$ ráz.)

Najväčší možný obvod záhradky je teda $$4t - 2(t-1) = 2t+2$$. (Tento obvod majú všetky záhradky, ktoré majú stromovú topológiu.)

No a počet strán záhradky je zjavne nanajvýš rovný jej obvodu – pričom rovnosť nastáva práve vtedy, keď má každá strana dĺžku 1. Takže najlepšie, čo teoreticky môžeme dosiahnuť, je $$s=2t+2$$. Inými slovami, $$t=(s/2)-1$$.

Ak nám teda niekto povie počet strán $$s$$ a chce od nás, aby sme mu navrhli záhradku s obsahom menším ako $$s/2$$, pôjde to len vo veľmi špecifickom prípade: budeme musieť nakresliť záhradku, ktorá má stromovú topológiu a ktorá má všetky strany dĺžky 1. Vedeli by ste teraz v tejto úvahe pokračovať a dokázať, ako vyzerajú úplne všetky záhradky pre ktoré $$s/2 > t$$?