KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Príklady prvého kola letnej časti 26. ročníka KSP

Milé naše riešiteľky, milí naši riešitelia.

Opäť sa vám dostávajú do rúk zadania Vášho obľúbeného semináru a určite sa tešíte na riešenie skvelých príkladov. Aby ste náhodou nenadobudli pocit, že to robíte nadarmo, pripomíname Vám, že najlepších čaká pozvánka na sústredko, a tých najlepších z najlepších navyše aj úžasné knižné ceny. A pre víťaza kategórie T samozrejme okrem knižnej odmeny aj nehynúca sláva, a dav rozvášnených fanyniek (KSP neručí, za žiadnu súčasť ceny s výnimkou knižnej).

A dokedy toto všetko? Termín odoslania riešení tejto série je už pondelok 9. marca 2009.

Lenivec je ten, čo nerobí zbytočné pohyby.

1. Zabudnutý PIN

10 bodov, kategíria: Z
Etome je informatik a má zlú pamäť na čísla. Zato počítanie, to mu ide. Vie napríklad z hlavy vypočítať ľubovoľný faktoriál. ( faktoriál, značené , je súčin čísel od 1 po vrátane.)

Táto jeho schopnosť má kopu praktických využití. Napríklad si takto pamätá svoj päťmiestny PIN (Nie, nie je to preklep, Etome naozaj používa päťmiestny PIN kód) -- miesto neho si pamätá len číslo a vie, že jeho PIN je tvorený poslednými piatimi ciframi .

Počas minulého leta Etome brigádoval jedna radosť. Zo svojich prvých zarobených peňazí sa rozhodol kúpiť si televízor. Prišiel do miestneho obchodu s elektronikou, kde sa odohral nasledujúci rozhovor

-- Dobrý deň, máte prosím vás farebné televízory?
-- Máme.
-- Tak si prosím jeden zelený.
-- V poriadku, tie máme po štyristo. Budete platiť v hotovosti alebo kartou?
-- Kartou.
A tu nastal problém. Bohužiaľ, Etome bol zase do šiestej ráno hore a teraz mu to rátanie z hlavy nejde až tak dobre.

Úloha

Dané je kladné celé číslo . Pomôžte Etomovi a vypočítajte jeho PIN. Inými slovami, vypočítajte posledných päť cifier čísla . (Ak má menej ako 5 cifier, vypíšte ich zľava doplnené nulami.)

Keďže Etome môže v budúcnosti chcieť bezpečnejší PIN (primalé by mohlo spôsobiť bezpečnostné riziko), mal by váš program fungovať pre ľubovoľne veľké , aké sa vám ešte zmestí do premennej.

Príklad

Vstup

N=4

Výstup

00024

Vstup

N=9

Výstup

62880
$9!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9=362880$

2. Zapichnutá hrana

10 bodov, kategória: Z
Traja prestarnutí dôchodcovia Miško, Kubko a Vladko, ktorých už pozeranie slovenského futbalu začalo nudiť, si na svojom fialovom televízore naladili najnovšiu argentínsku telenovelu. Zrovna fičal asi 507. diel. Situácia v telenovele sa začala prudko zamotávať. Každú polminútu sa objavil nový vzťah, takže bol z toho akurát pekný bordel. Nasledovala reklamná prestávka, počas ktorej sa odohral nasledujúci rozhovor

-- Vladko: "Tušíte vôbec, kto je hlavný hrdina?"
-- Kubko: "To bude tá Mária, tu chcú asi desiati..."
-- Miško: "Podľa mňa to bude zas tá Lucia, tá chcela asi štrnástich..."
-- Vladko: "Ehm ten, ako sa volá... Peter... toho chcelo asi dvanásť."
-- Kubko: "To si koho zarátal? Učili ťa na tom matfyze vôbec počítať?"
Ako vidíte, schyľuje sa k miernej hádke, takže vašou úlohou je porátať, kto je v danej telenovele najväčšia ihelnička a kto najväčší ježko.

Úloha

Na vstupe je počet postáv a počet vzťahov . Postavy sú očíslované prirodzenými číslami od po . Nasleduje dvojíc čísel a~b , pričom každá dvojica vyjadruje, že postava chce (Resp. niekedy počas deja chcela) postavu . Môžete predpokladať, že každá informácia sa na vstupe vyskytne práve raz -- ale pozor, môže sa najprv vyskytnúť najskôr dvojica a~b a potom aj b~a .

Vašou úlohou je vypísať dve čísla postáv -- číslo postavy, ktorú chce najviac iných (tzv. ihelnička) a číslo postavy, ktorá chce najviac iných (tzv. ježko). Zároveň zistite pre každého jeho stupeň -- počet postáv ktoré chcú ihelničku/chce ježko. Pokiaľ existuje viac správnych možností, vypíšte ľubovoľnú z nich.

Dôležité upozornenie: Nepredpokladajte nič o pohlaviach postáv zodpovedajúcich vstupu!

Príklad

Vstup

N=9 , M=10
1 4
2 4
3 4
4 3
5 2
6 7
6 5
6 8
8 6
9 7

Výstup

Ihelnicka je: 4, stupen 3
Jezko je: 6, stupen 3
P.S.: Kto zistí, ktorí ľudia sa skrývajú za danými vrcholmi, má u U$Ámu kofolu :).

3. Zoltánove televízory

10 bodov, kategória: Z

Keď bol Malý Zoltán ešte malý, dostal na narodeniny takú skvelú stavebnicu. Skladala sa z tyčí a spojníc. Tyče boli rôznej dĺžky a spojnice boli také guličky, ktoré vedeli spojiť konce 1 až 5 tyčí. Malému Zoltánovi (V čase, keď bol ešte malý.) sa táto stavebnica veľmi páčila a denno-denne sa s ňou hrával.

Zoltán časom vyrástol, vyštudoval matfyz, založil si rodinu a mal syna Malého Zoltána mladšieho. Malý Zoltán mladší má momentálne svoje druhé narodeniny a tak dostal od Malého Zoltána jeho obľúbenú(Obľúbená bola v čase, keď bol ešte malý.) stavebnicu. Malý Zoltán mladší pri takom darčeku nadšene vykríkol a hneď sa začal so stavebnicou hrať. Keďže malý Zoltán mladší je ešte veľmi malý, tak to neskladal len tak s rozmyslom, ale len tak náhodne. Keď sa dohral, tak od vyčerpania zaspal.

Malý Zoltán uložil Malého Zoltána mladšieho spať a rozhodol sa to upratať. Pritom si všimol, že Malý Zoltán mladší postavil niekoľko televízorov. Tak si Malý Zoltán(Ako správny matfyzák...) prepísal popisy jednotlivých výtvorov do počítača a rozhodol sa, že si spraví program, ktorý mu zistí, ktoré z nich sú televízory.

Úloha

Prvý riadok vstupu obsahuje čísla a , kde je počet spojovníkov (spojovníky sú očíslované od po ) a je počet tyčí. Druhý riadok vstupu obsahuje čísiel a_1, a_2, a_3, a_4, a_5 , pričom a_i označuje počet spojovníkov, ktoré spájajú práve tyčí (Platí, že a_1+a_2+a_3+a_4+a_5=N .) Ďalej nasleduje riadkov, pričom každý z nich obsahuje dve čísla a , ktoré hovoria, že medzi spojovníkmi a vedie tyč.

Samozrejme medzi každou dvojicou spojovníkov môže viesť maximálne jedna tyč. Každá tyč má na každom svojom konci jeden spojovník. Navyše môžete predpokladať, že útvar popísaný vstupom programu "drží pokope" -- teda že by mravce vedeli preliezť z ľubovoľného miesta na ľubovoľné iné bez toho, aby museli opustiť povrch útvaru.

Ako spoznáme televízor? Televízor je "bedňa" s dvoma "anténami", ktoré vychádzajú z toho istého miesta. Bedňu vyrobíme tak, že zoberieme niekoľko spojovníkov (aspoň tri) a toľko isto tyčí a zapojíme ich do jedného veľkého kruhu -- teda z každého spojovníka povedú práve dve tyče. Potom si vyberieme ľubovoľný spojovník a pridáme mu dve (môžu byť aj rôzne dlhé) antény. Anténa je niekoľko (aspoň ) tyčí pospájaných do radu za sebou.

Vašou úlohou je pre daný vstup povedať, či je daný kus stavebnice televízor alebo nie.

Príklad

Vstup

8 8
2 5 0 1 0
1 3
2 3
3 4
4 5
5 6
6 7
7 3
2 8

Výstup

Vstup je televizor.

Vstup

7 7
3 3 0 0 1
1 3
2 3
3 4
4 5
5 6
6 3
7 3

Výstup

Vstup nie je televizor.
(Lebo zo spojovníka idú až 3 antény.)

4. Obrazovka je na eskykráliky malá

15 bodov, kategória: Z a O

Ako iste všetci viete, na Sibíri bývajú Eskimáci a Eskimáčky. Po dlhšom pobyte sa dajú odpozorovať aj eskikocúry a rôzne iné zvery. Upriamme ale našu pozornosť na eskikráliky. Veľmi sa nelíšia od obyčajných králikov, žijú podobným životom až na dva rozdiely.

Prvý sa týka rozmnožovania. Naše slovenské králiky sa rozmnožujú podľa Fibonacciho postupnosti ( http://www.novinky.cz/clanek/109771-hrajeme-zdarma-fibonacci-chytejte-kraliky.html ). Ale eskikráliky to dokážu ešte rýchlejšie -- každú sekundu sa z jedného eskikrálika stanú dvaja~-- severný a južný. Líšia sa v tom, že severný skáče na sever a južný na juh. Každý eskikrálik spraví jeden skok za jednu sekundu a jeho skok má dĺžku presne jeden meter.

Druhý rozdiel sa týka stravy. Naše králiky sú vyberavé, nezožerú len tak hocičo. Zvykli si zväčša na mrkvu a iné obilniny. Eskikráliky žijú v drsnom prostredí, takže nie sú také chúlostivé. Uspokoja sa s hocičím, čo sa hýbe. Takže keď sa stretnú severný a južný králik, tak sa navzájom zožerú a nezostane z nich nič. Ak sa v jednom momente má králik aj rozmnožovať aj zjesť iného králika, prioritu má jedlo.

Na Sibíri bol na začiatku jeden králik. Odvtedy sa opakuje nasledovný kolobeh:

Každý králik sa rozmnoží. Jeho severná verzia skočí na sever, južná verzia skočí na juh.
Ak sú na nejakom mieste dva králiky, tak sa navzájom zožerú a nezostane z nich nič.

Novinári prišli na Sibír v čase (keď ešte existival iba jeden králik) a hneď začali natáčať dokumentárny film o králikoch. Snímky robili na začiatku každej sekundy (tesne pred rozmnožovaním). Králikov však bolo časom tak veľa, že sa skoro nezmestili na obrazovku televízora. Preto sa film dá pozerať len na najkvalitnejších 47-palcových HD ready fialových televízoroch. Kameru novinári fialovú nemali, iba takú nekvalitnú zelenú, preto im vypadol -tý obrázok. A práve ten bol dôležitý! Preto sa obracajú na vás, programátorov, aby ste im zrekonštruovali situáciu v -tej sekunde.

Úloha

Na vstupe máte dané -- sekunda, ktorú chceme zrekonštruovať. Výstupom majú byť počty králikov na jednotlivých pozíciách od najjužnejšieho po najsevernejšieho.

Príklad

Vstup

Výstup

1 0 0 0 1
(V nultej sekunde je jeden eskikrálik. Potom sa rozmnoží, potomkovia bežia a v prvej sekunde sú dvaja na pozíciách 0 a 2. Potom sa rozmnožia, bežia, zožerú a v druhej sekunde sú tak ako vo výstupe (na fialovom televízore).)

5. Zlý príjem

15 bodov, kategória: Z a O

Nech nastavíte anténu na žltom televízore Merkur ako len chcete, akonáhle si sadnete do kresla, začne sa príjem postupne zhoršovať, až nakoniec dostanete len šum.

Kvalitu príjmu môžeme označiť číslom od 9 (skoro dokonalé) po 0 (samé zrno). Spravme teraz nasledovný experiment: Nastavíme anténu, sadneme do kresla a každých 5 minút zapíšeme kvalitu obrazu. Keď už zostane len zrnenie, experiment ukončíme. Môžeme takto dostať napríklad číslo 7654321 (obraz sa postupne zhoršoval), 999 (štvrť hodiny to šlo, potom bum a zrazu nič) alebo 9111111 (chvíľku to šlo pekne, a potom ešte pol hodinky bolo vidieť obrysy postáv).

Čísla, ktoré môžeme pri experimente dostať, nazveme zrnité. Postupnosť všetkých zrnitých čísel (usporiadaných vzostupne podľa numerickej hodnoty) vyzerá nasledovne:

$1, 2, \dots, 8, 9, 11, 21, 22, 31, 32, \dots, 98, 99, 111, 211, 221, 222, 311, \dots$

Zrnité číslo sa skladá z cifier $1,2,\dots,9$ a jeho cifry tvoria nerastúcu postupnosť (každá ďalšia cifra je buď rovnaká, alebo menšia ako predchádzajúca cifra). Napríklad číslo 7656 nie je zrnité, lebo po cifre nasleduje cifra . Číslo 3210 nie je zrnité preto, lebo obsahuje cifru .

Úloha

Pre čo najviac z množiny $\{2,3,\dots,16\}$ nájdite číslo, ktoré je v postupnosti zrnitých čísel na mieste 10^k . Čím viac správnych čísel pošlete, tým viac bodov dostanete. (Pošlite nám aj programy, pomocou ktorých ste tieto čísla hľadali.)

Príklad

Vstup

k=1

Výstup

Na pozícii 10^1=10 je číslo 11.

6. Obchod plný televízorov

20 bodov, kategória: O

Mladý Kleofáš dostal bojovú úlohu. Má vybrať pre rodinu nový televízor. Kleofáš dobre vie, že jeden z najdôležitejších parametrov je veľká uhlopriečka, a tak sa vybral do obchodu a hľadal televízor s tou najväčšou uhlopriečkou. Keďže Kleofáš ešte nevie čítať číslice, začal splašene pobehovať po obchode, porovnáva uhlopriečky dvojíc televízorov a zapisuje si výsledky. Teraz prišiel domov a snaží sa zostrojiť rebríček televízorov tak, aby nebol nejaký televízor pred iným, o ktorom vie, že má väčšiu uhlopriečku. Televízorov bolo obchode veľmi veľa, a preto bude potrebovať vašu pomoc.

Úloha

Napíšte program, ktorý na vstupe dostane čísla a , kde je počet televízorov a je počet porovnaní. Za nimi bude nasledovať dvojíc televízorov (Kleofáš nepoužíval čísla, ale my si to uľahčíme a budeme televízory označovať číslami od po .) a_k b_k , ktoré hovoria o tom, že televízor a_k má väčšiu uhlopriečku ako b_k .

Vašou úlohou je zoradiť televízory do postupnosti $t_1, t_2, \dots, t_n$ podľa uhlopriečky tak, aby pre žiadne dva televízory t_i a t_j kde i<j , neexistovalo porovnanie na Kleofášovom zozname, ktoré by hovorilo o tom, že televízor t_j má väčšiu uhlopriečku ako televízor t_i . Inak povedané, každý televízor je v poradí pred všetkými televízormi o ktorých vieme, že majú menšiu uhlopriečku.

Príklad

Vstup

N=7 , M=6
1 5
6 7
3 4
1 2
7 2
6 1

Výstup

3 4 6 7 1 5 2
(Všimnite si, že napríklad aj usporiadanie 6 1 3 7 5 4 2 je správne.)

7. Obchod s televízormi

20 bodov, kategória: O

Marek sa rozhodol, že skončí so školou a založí si obchod s modrými televízormi. Jeho obchod sa stal rýchlo veľmi populárnym najmä medzi študentmi, ktorí si nový televízor kupujú veľakrát do roka a väčšinou viacero naraz. Keďže ide o chudobných študentov, tak chcú kúpiť vždy televízory za najnižšiu možnú cenu. Navyše k Marekovi chodia občas dodávatelia, ktorí dovezú niekoľko rovnakých kusov televízorov. Pomôžte Marekovi, aby vedel prichádzajúcich zákazníkov obslúžiť čo najrýchlejšie.

Úloha

Prvý riadok obsahuje číslo -- počet udalostí. Nasleduje zoznam udalostí. Každá udalosť môže byť dvoch typov: "1 " alebo "2 ". Všetky čísla sú celé. Prvá udalosť je príchod dodávateľa, ktorý priniesol televízorov za jednotkovú cenu (môžete predpokladať, že $B\leq N$ . Druhá udalosť je príchod študenta, ktorý chce kúpiť televízorov za čo najmenšiu cenu. Váš program má vypísať túto cenu alebo "Nedostatok televízorov", ak Marek nemá dosť televízorov na sklade. Ak Marek nemá dosť televízorov, študent od neho odchádza s prázdnymi rukami.

Príklad

Vstup

N=6
1 4 3
1 4 2
2 9
2 5
1 2 2
2 5

Výstup

Nedostatok televizorov
11
13

8. Ovplyvnenie predaja

25 bodov, kategória: O a T

Laci po nociach brigáduje, aby mal z čoho financovať svoj náročný študentský život (Keďže zadania čítajú aj neplnoleté osoby, nebudeme radšej zachádzať do detailov.). Najnovšie si našiel brigádu vo veľkoobchode Plesko, kde predáva televízory.

Predaj televízorov je ťažká práca, lebo televízory sú ťažké. A treba ich nosiť. A zákazníci stále chcú niečo extra. Napríklad minulý týždeň, keď tu boli tie dve slepice. Pekne sa ich spýtal, že či teda chcú farebný (napríklad zelený), a ony že to je jedno, hlavne nech dobre zrní...

Alebo včera, keď prišla nakupovať tá stará krysa. A že ona kašle na to či je zelený alebo cyklámenový, hlavne nech má veľa kanálov!

A na sklade sa hromadia zelené televízory, ktoré nik nechce.

A vtedy Laciho osvietilo a vymyslel skvelý zlepšovák. Spravia koleso šťastia. Vždy, keď niekto pôjde kúpiť televízor, zatočí si kolesom, aby zistil, aký dostane. Samozrejme, koleso bude len program na počítači, a ten vopred nastavia tak, aby pravdepodobnosti jednotlivých televízorov zodpovedali tomu, čo na začiatku mali v sklade. A už je Laci vo svojom živle -- namiesto fyzickej práce môže programovať.

Úloha

Na vstupe je počet druhov televízorov a potom reálnych čísel $p_1,\dots,p_N$ . Číslo p_i je pravdepodobnosť, s akou má na kolese vyjsť druh . (Platí $0\leq p_i$ a tiež $p_1+\cdots+p_N = 1$ .)

Máte k dispozícii funkciu random(), ktorá vždy, keď ju zavoláte, vráti náhodné reálne číslo z intervalu $\left< 0,1 \right)$ . Toto je jediný zdroj náhody, ktorý smiete použiť (Ak váš programovací jazyk nemá presne takúto funkciu, v programe si túto funkciu vyrobte pomocou toho, čo máte k dispozícii.).

Napíšte program, ktorý načíta tieto údaje, spracuje ich a následne bude čo najrýchlejšie generovať výstup -- čísla od 1 do , pričom v každom kroku musí byť pravdepodobnosť toho, že dostaneme výstup , rovná p_i .

Obmedzenia a upozornenia:

Čas behu programu počas úvodného spracovania vstupu musí byť polynomiálny od a nesmie závisieť od konkrétnych hodnôt p_i .

Za riešenie, ktoré na vygenerovanie jedného výstupu potrebuje čas priamo úmerný $\log N$ , veľa bodov nebude. A už tobôž nie za ešte pomalšie riešenia.

Príklad

Vstup

N=3
pravdepodobnosti: 0.7, 0.2, 0.1

Výstup

1, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, ...

9. Tatranské panorámy

25 bodov, kategória: T

Keď mladý Anton na svojom farebnom televízore pozeral reláciu pre Národniarskych Geografov, ukazovali v nej ako vyrobiť z dvoch fotografií panorámu. Náruživý fotograf a programátor Anton sa rozhodol, že si na to vytvorí program.

Na vytvorenie panorámy zoberieme dve fotografie. Prvá bude naľavo a druhá napravo. Následne treba nájsť vertikálny prekryv týchto dvoch fotografií. Prekryv je nenulový počet stĺpcov pixelov na pravom kraji prvej fotografie, ktorý sa zhodne nachádza aj na ľavom kraji druhej fotografie. Keďže Anton chce čo najväčšie panorámy, potrebuje vždy nájsť prekryv, ktorý je minimálny. S týmto si však už nevie poradiť a preto bude potrebovať Vašu pomoc.

Úloha

Váš program bude pracovať s fotografiami v jemne-stratovom formáte ASCII. Vstup programu začína dvomi číslami , . Za nimi nasledujú dve matice znakov , s rozmermi $N\times M$ -- fotografie. Výstupom programu bude číslo -- minimálny nenulový počet stĺpcov, ktorými sa dve fotografie prekrývajú. Formálne sa dá prekryv vyjadriť nasledovne: $\forall i, j, 1\leq i\leq K: a_{N-K+i,j} = b_{i,j}$ . Ak takéto neexistuje, tak vypíšte .

Príklad

Vstup

N=3 , M=8

../\....
./..\___
/.......
........
__../\..
..\/..\_

Výstup

Komentár

(Výsledná panoráma vyzerá nasledovne:)

../\...........
./..\____../\..
/........\/..\_

-----------------

10. Televízni lenivci

25 bodov, kategória: T

Georgova stavebná firma v poslednej dobe úspešne prosperuje. Preto sa snaží nájsť si svoje miesto aj v iných krajinách a presadzovať sa na tamojších trhoch. A tak sa nedávno stalo, že expandovala na veľký pracovný trh Lenivostanu.

Lenivostan je krajina, ktorej obyvatelia neoplývajú prílišnou usilovnosťou. Dá sa dokonca povedať, že sú nadmieru leniví a absolútne nemotivovaní. Preto aj prvá zákazka, ktorú dostala Georgova firma, dopadla ako dopadla -- po prvom dni nič nepripomínalo budúci aquapark. Viac to pripomínalo bandu lenivých robotníkov, váľajúcich sa na zemi a jediacich tresku. Preto sa Georg rozhodol, že si na kontrolu lenivých lenivcov zoženie účinné prostriedky -- kameru, pomocou ktorej bude schopný sledovať činnosť všetkých pracovníkov. Kameru umiestnil na vrtuľník, ktorý sa pohybuje nad staveniskom.

Keď sa robotníci dozvedeli, že ich práca bude takto neľudsky kontrolovaná, spanikárili a rýchlo začali utekať niečo robiť. Celkovo sa každý robotník dá popísať miestom, kde sa váľal a jedol tresku, a vektorom, ktorým sa rozbehol. Robotníci majú v montérkach rôzne veľké a ťažké náradie, preto sa každý pohybuje rôznou rýchlosťou. Avšak ich rýchlosť a ani smer ich behu sa nemení. Ak má robotník štartovnú pozíciu [s_x, s_y] a vektor jeho pohybu je [v_x, v_y] , potom jeho pozícia v čase bude [s_x+tv_x, s_y+tv_y] .

Georg, sediaci v kontrolnej veži staveniska, ich môže pozorovať na svojom televízore. Veľmi sa mu páči, ako pobehujú a úplne najviac sa mu páči, ak vidí, ako pobehujú všetci. Avšak na to potrebuje dosť veľký televízor, no a veľké televízory sú drahé televízory. Preto mu pomôžte a zistite, aký najmenší televízor mu stačí, aby aspoň na chvíľočku videl na obrazovke všetkých robotníkov, ak bude kamera snímať správnu oblasť staveniska!

Keďže v Lenivostane boli takí leniví, že ešte nevymysleli obdĺžnik, tak obrazovky všetkých televízorov majú tvar štvorca. Pre jednoduchosť v tomto zadaní predpokladáme, že oblasť, ktorú možno pozorovať na obrazovke televízora, je priamo úmerná veľkosti obrazovky. Rovnako predpokladáme, že oblasť, ktorú sníma kamera, má tvar štvorca a ten má navyše svoje strany rovnobežné so súradnicovými osami.

Úloha

Pre dané pozície a vektory robotníkov zistite, aký najmenší televízor si musí Georg kúpiť, aby aspoň v jednom momente videl všetkých robotníkov. Keďže obrazovka televízora má tvar štvorca, výstupom by malo byť jedno reálne číslo -- veľkosť jej hrany. Robotník, ktorý je presne na hranici záberu, sa považuje za zachyteného. V príkladoch je pri robotníkoch uvedený najprv štartový bod a potom vektor posunu.