4. Záhradka vzorové riešenie

6 5

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

9 12

Neda sa

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\)?