# Pergel

<{ForumPost(poster="neznamymatfyzak", timestamp=2021-06-28 21:11:26)}>
**Originální pdf zadání zde** 

210628_zk_auticka.pdf

Pro ty, co nechtějí stahovat, následuje přepis zadání:  
  
**Písemná část**  
1 úloha  
Po zodpovězení všech otázek k zadání jsme měli 2 hodiny čistého času na řešení  
  
**Autíčka**  
Autíčka se pohybují v krocích po celočíselných souřadnicích (čtverečkovaný papír). Cílem je dojet ze startu do cíle na co nejmenší počet kroků.  
**Rychlost** znamená vektor – rozdíl mezi minulou a aktuální polohou.Na začátku má autíčko rychlost **(0,0)**.  
**Krok** spočívá v tom, že se autíčko posune o rychlost, ale může k ní ve směru **X** i ve směru **Y** přičíst nebo od ní odečíst jedničku, tj. přesune se na políčko v jedničkovém okolí políčka, na které by ho zanesla dosavadní rychlost. Tím bude určena rychlost pro příští krok.  
Autíčko se pohybuje po **průsečících** čtverečkové sítě, některé hranyčtverečků mohou tvořit **překážky**. Překážka má vždy podobu hrany jednoho čtverečku. Autíčko při pohybu nesmí projet překážkou.  
**Cílová páska** je úsečka spojující dva celočíselné body (průsečíky). Projetí cílové pásky autíčkem je cílem závodu.  
**Vstupní data** jsou v textovém souboru, přičemž první znak na řádce vždy určuje, jakou informaci řádka obsahuje:  
    • **S** start: **x** (int) a **y** (int)  
    • **C** cílová páska: **x1** (int), **y1** (int), **x2** (int), **y2** (int),  
    • **P** překážka: **x1** (int), **y1** (int), **x2** (int), **y2** (int)  
  
**Zadání**  
Navrhněte program, který ze zadaných vstupních dat spočte nejmenší počet kroků potřebných k tomu, aby autíčko projelo cílovou páskou.  
**Počty a omezení:**  
rozměry hrací plochy: <= 100×100  
maximální rychlost autíčka: 10 v každé ose v každém směru.  
paměť = 10MB, v případě nouze bez omezení,  
čas = přiměřeně (sekundy až minuty).   
V odpovědi popište  
1) postřehy  
2) zdůvodněnou volbu algoritmu  
3) representaci dat  
4) dekompozici programu  
5) diskusi,   
v případě potřeby i  0) upřesnění zadání.  
  
**Řešení, které mě napadlo:**  
BFS  
  
**Ústní část**  
Témata, na která se ptal Pergel: halda a její definice, vnější třídění, diskrétní simulace, dynamické programování, virtuální metody  
(u diskrétní simulace a dynamického programování chtěl slyšet co to zhruba je a následně to i předvést na nějakém příkladu - např. převod Dijkstrova algoritmu na diskrétní simulaci, násobení matic)  
Témate, na která se ptal Holan: tabulka virtuálních metod, co je to dynamické programování + příklad, hešování, unit testy, vnější třídění, halda, generické třídy

*Attachments:*

- *[210628_zk_auticka.pdf](/Forum%20archiv/Attachments/7358_db360a71c22eeca33a5b2f61b062256d)*

<{/ForumPost}>