Zoznam úloh

4. Názov úlohy

Zadanie

Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Ak máš hocijaké otázky k tejto úlohe, napíš Lucke na lucia.klescova@prask.ksp.sk.

Štepi, Hanka a Miška sa už chystali odísť z dedinky.Kým sa lúčíli s dedinčanmi, ich zrak upútali deti, ktoré sa hrali na zemi.

Deti sedeli okolo šachovnice, na ktorej boli uložené 4 kamienky, ktorými zvláštne pohybovali do štyroch smerov. Keď sa k nim Štepi priblížíl, deti mu s radosťou začali vysvetľovať pravidlá hry, ktorú sa hrali.

Úloha

Je daná tabuľka m x n. V tabuľke sa nachádzajú 4 roboti. Roboti sa môžu pohybovať hore, dole, vpravo a vľavo a hýbu sa dovtedy, kým nenarazia na iného robota alebo na stenu tabuľky. Naraz sa pohybuje stále maximálne jeden robot, teda robot sa môže začať pohybovať iba ak sa všetci ostatní roboti nehýbu.

  1. Roboti sú umiestnení do tvaru štvorca v pravom dolnom rohu tabuľky. Vieme robotov presunúť tak, aby celý štvorec bol o 1 riadok tabuľky vyššie?

  1. Roboti sú umiestnení do tvaru štvorca dole v strede dolnej hrany tabuľky. Vieme robotov presunúť tak, aby celý štvorec bol o 1 riadok tabuľky vyššie?

  1. Roboti sú umiestnení do tvaru štvorca v pravom dolnom rohu tabuľky. Vieme presunúť jedného z robotov na nejaké konkrétne určené miesto? Ak áno, ako?

  2. Roboti sú umiestnení do tvaru štvorca v pravom dolnom rohu tabuľky. Vieme presunúť 2 robotov na nejaké konkrétne určené miesto? Ak áno, ako?

Pomenujme si robotov A, B, C a D ako na obrázku.

  1. Na začiatok si musíme uvedomiť, že na to, aby celý štvorec bol posunutý o 1 vyššie stačí posunúť spodných robotov (C, D) o 2 vyššie.

To vieme docieliť už jednoducho: Robota C posunieme najprv doľava, potom hore a doprava. Následne posunieme robota D doľava, hore a doprava. Potom už iba oboch robotov postupne posunieme dole a máme celý štvorec posunutý o 1 hore.

  1. V tejto podúlohe použijeme rovnaký spôsob posunutia štvorca a to je posunutie iba spodných dvoch robotov:

Robota C posunieme najprv doľava a potom hore. Následne posunieme robota B hore, aby zastavil robota C. Robota C potom pošleme doprava a po náraze do robota B ho posunieme dole. Potom sa robot B vráti zas dole. Toto zopakujeme aj pre robota D: najprv ho posunieme doprava a hore, potom posunieme robota A hore, robota D doľava a následne robotov A aj D dole.

  1. Na základe druhej podúlohy si vieme uvedomiť jednu vec: keďže vieme štvorec robotov posúvať hore, tak analogicky ho vieme posúvať stále do všetkých smerov. Čo znamená, že štvorec vieme presunúť na každé miesto v tabuľke. Teda stále vieme presunúť štvorec tak, aby nejaký robot stál na nami určenom mieste.

  2. Túto úlohu si vieme rozdeliť na dve - presunutie jedného robota na konkrétne miesto pomocou štvorca a presunutie druhého robota na konkrétne miesto pomocou zvyšných dvoch robotov. Stačí nám už iba dokázať, že aj troch robotov vieme presunúť tak, aby jeden z nich stál na určenom mieste. To vieme spraviť jednoducho:

Najprv si ukážeme, že troch robotov vieme posúvať popri hrane tabuľky:

Potom vieme v smere kolmom na hranu, ktorej sa 2 roboti dotýkajú posúvať robotov týmto spôsobom:

Ešte si musíme uvedomiť, že tento spôsob nebude fungovať ak týmto robotom bude stáť v ceste štvrtý, už umiestnený robot, preto je dôležité vhodne si zvoliť, po ktorej hrane budeme robotov posúvať.

Pre odovzdávanie sa musíš prihlásiť.