2. kolo - Vězení

Nepochopili jste zadání či naopak vzorové řešení? Chcete se zeptat na některé jiné algoritmy?
Zamčeno
juhelak
Příspěvky: 2
Registrován: 05-12-2016 12:33
Škola: Arcibiskupské gymnázium
Rok ukončení studia: 2017

2. kolo - Vězení

Příspěvek od juhelak »

Zdravím,
zabýval jsem se touto úlohou a myslím si, že v zadání úlohy chybí informace. Konkrétně:

1. na kterém z hlídaných míst jsou prvotně umístěny hlídky
2. jestli se hlídky na začátku pohybují, nebo jsou již hned na místě (tzn. jestli na prvotní místo na začátku teprve jdou, nebo na něm automaticky již jsou)
3. jak se řeší případ, že chci jít na místo, na které chce ve stejném tahu přijít hlídka a z kterého ve stejném tahu chce odejít hlídka. Například - chci se posunout o jednu "ulici" doprava, přičemž nějaká hlídka tohle "kolo" udělá to samé - je to validní tah, nebo ne? (předpokládám, že ne)
A naopak - chci se posunout o jednu "ulici" doprava, přičemž je na daném místě hlídka, která se ale tohle "kolo" posune jinam... (předpokládám, že tohle jde)

Díky za odpověď,
juhelak

EDIT: ještě jeden postřeh - v příkladovém vstupu číslo dva jsou v prvním problému u určování domu pouze souřadnice, není uvedena hlídka, která tento dům hlídá ("2 2" místo "2 2 0"). Je to protože existuje jenom jedna hlídka?

simon
Příspěvky: 7
Registrován: 07-12-2016 22:32
Škola: FIT ČVUT
Rok ukončení studia: 2100

Re: 2. kolo - Vězení

Příspěvek od simon »

Ahoj juhelak,
děkujeme za zájem o seminář. Nyní k tvým dotazům:
na kterém z hlídaných míst jsou prvotně umístěny hlídky
Obávám se, že zde došlo zřejmě k nepochopení zadání, respektive je možná zadání nejasně formulované. Dovol mi vypůjčit si pojmenování z vojenství, myslím, že by to mohlo být pro objasnění prospěšné. To, co je v zadání označováno jako skupina hlídek, si můžeš představit jako rotu. Každá tato skupina hlídek (rota) se skládá z několika hlídek (čet). Počet těchto hlídek (čet) je přímo úměrný počtu objektů, které má skupina (rota) na starosti. Všechny hlídky (čety) v jedné skupině (rotě) mají nařízeno, jaký čas mají zůstat na jednom místě. Stejný čas jim pak trvá i přesun mezi objekty. Je to nyní jasnější?
jestli se hlídky na začátku pohybují, nebo jsou již hned na místě (tzn. jestli na prvotní místo na začátku teprve jdou, nebo na něm automaticky již jsou)
Hlídky jsou v čase 0 na svých pozicích.
jak se řeší případ, že chci jít na místo, na které chce ve stejném tahu přijít hlídka a z kterého ve stejném tahu chce odejít hlídka. Například - chci se posunout o jednu "ulici" doprava, přičemž nějaká hlídka tohle "kolo" udělá to samé - je to validní tah, nebo ne? (předpokládám, že ne)
A naopak - chci se posunout o jednu "ulici" doprava, přičemž je na daném místě hlídka, která se ale tohle "kolo" posune jinam... (předpokládám, že tohle jde)
Předpokládáš správně. Nikdy nesmí nastat případ, kdy bys byl na nějakém místě ve stejný čas, jako některá z hlídek. Tedy na políčko, kde stráží hlídka s intervalem 2 nemůžeš vstoupit v čas 0, 1, 4, 5, 8, 9 atd.
v příkladovém vstupu číslo dva jsou v prvním problému u určování domu pouze souřadnice, není uvedena hlídka, která tento dům hlídá ("2 2" místo "2 2 0"). Je to protože existuje jenom jedna hlídka?
Dobrý postřeh. Vstup je, přesně jak říkáš, špatně, opravdu tam chybí ta 0. Zadání by již mělo být opraveno a nahráno na web.

Když bys narazil na nějaký další problém, neváhej nám napsat.

Hodně radosti při řešení úloh přeje
Šimon

nulam
Příspěvky: 9
Registrován: 04-10-2016 08:18
Škola: SŠT a VOŠ Česká Třebová
Rok ukončení studia: 2017

Re: 2. kolo - Vězení

Příspěvek od nulam »

Není mi jasné, jak funguje zadání plochy vězení. V druhém případě druhého vstupu je plocha 4x4 a ve vysvětlení je napsané, že se snažíme dostat do bodu [5,5] a některé domy se nacházejí na bodech se souřadnicemi větší než 4. V prvním vstupu je velikost 5x5, ale také se snažíme dostat na pole [5,5]. Je v zadání chyba, nebo mi něco uniká :?:

tfurst99
Příspěvky: 1
Registrován: 14-01-2017 08:42
Škola: Gymnázium Oty Pavla
Rok ukončení studia: 2019

Re: 2. kolo - Vězení

Příspěvek od tfurst99 »

nulam píše:Není mi jasné, jak funguje zadání plochy vězení. V druhém případě druhého vstupu je plocha 4x4 a ve vysvětlení je napsané, že se snažíme dostat do bodu [5,5] a některé domy se nacházejí na bodech se souřadnicemi větší než 4. V prvním vstupu je velikost 5x5, ale také se snažíme dostat na pole [5,5]. Je v zadání chyba, nebo mi něco uniká :?:
Předpokládám, že se jedná o chybu zadání, nejspíše to má být 5x5. Nicméně pak by se jednalo i o chybu ve výstupu, neboť nejmenší možný čas (bez hlídek) by byl 10.

nulam
Příspěvky: 9
Registrován: 04-10-2016 08:18
Škola: SŠT a VOŠ Česká Třebová
Rok ukončení studia: 2017

Re: 2. kolo - Vězení

Příspěvek od nulam »

Čím víc nad tím přemýšlím, tím víc se mi nezdá zadání. První dvě čísla by měly být ROZMĚRY obdélníkové oblasti, ale vysvětlení s nimi pracuje jako se souřadnicemi cíle. Pokud je plocha 5x5 a pole se počítají od nuly, cílové pole by mělo být [4,4]. Také zadání je poněkud nekonzistentní, jak jsem psal výše - pro dvě různé plochy je stejné cílové pole ve vysvětlení. :roll:

Marleft
Příspěvky: 3
Registrován: 28-01-2017 13:24
Škola: Gymnázium Nad Kavalírkou 1
Rok ukončení studia: 2017

Re: 2. kolo - Vězení

Příspěvek od Marleft »

No vzhledem k tomu, ze velikost pole je u posledního vstupu 5x5, neměl by tudíž výsledek být 11 ?

Epanemu
Příspěvky: 1
Registrován: 28-01-2017 22:23
Škola: Gymnazium Ceske Budejovice
Rok ukončení studia: 2017

Re: 2. kolo - Vězení

Příspěvek od Epanemu »

simon píše: Předpokládáš správně. Nikdy nesmí nastat případ, kdy bys byl na nějakém místě ve stejný čas, jako některá z hlídek. Tedy na políčko, kde stráží hlídka s intervalem 2 nemůžeš vstoupit v čas 0, 1, 4, 5, 8, 9 atd.
Jestli tomu dobre rozumim, tak by melo byt mozne udelat posledni ze vstupu na pouhych 8 kroku, jelikoz v case 0 je pozice [0,1] obsazena, ale v case 1 tam muzeme vkrocit, protoze je hlidka ve vymene, pricemz v case 2 zase tesne pred dalsi hlidkou odejdeme na pole [0,2] a pak dojdeme nejkratsi cestou az do cile... Nebo mam nekde chybu?

Diky za odpoved, i za kvalitni ulohy ;)

Zamčeno