Zbojníci

Nepochopili jste zadání či naopak vzorové řešení? Chcete se zeptat na některé jiné algoritmy?
Zamčeno
jakubs
Příspěvky: 6
Registrován: 14-09-2017 05:39
Škola: Gymnázium Brno-Řečkovice Terezy Novákové 2, p. o.
Rok ukončení studia: 2019

Zbojníci

Příspěvek od jakubs »

Zdravím,
rád bych se zeptal, zda jsou v úloze lodě "obarvené" či nikoliv. Jinými slovy, pokud mám 2 lodě stejné délky, pak je rozdíl v tom, že loď č. 1 na pozici A a loď č. 2 je na pozici B a v tom, že loď č. 1 je na pozici B a loď č. 2 na pozici A nebo je to ten samý případ (počítá se tedy za 1 rozmístění nebo za 2)?

Díky

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: Zbojníci

Příspěvek od blazeva1 »

Ahoj,
a̶n̶o̶,̶ ̶l̶o̶d̶ě̶ ̶l̶z̶e̶ ̶b̶r̶á̶t̶ ̶j̶a̶k̶o̶ ̶o̶b̶a̶r̶v̶e̶n̶é̶.̶ ̶Ř̶e̶š̶e̶n̶í̶ ̶v̶s̶t̶u̶p̶u̶ ̶"̶3̶ ̶3̶ ̶3̶ ̶3̶"̶ ̶b̶u̶d̶e̶ ̶1̶2̶.̶-̶

Vašek
Naposledy upravil(a) blazeva1 dne 18-09-2017 13:37, celkem upraveno 1 x.

jakubs
Příspěvky: 6
Registrován: 14-09-2017 05:39
Škola: Gymnázium Brno-Řečkovice Terezy Novákové 2, p. o.
Rok ukončení studia: 2019

Re: Zbojníci

Příspěvek od jakubs »

V tom případě bych se zeptal, zda jste si jistí ukázkovým vstupem 5 5 2 2 a výstupem 686. Když totiž provedu jen hrubý (výrazně podsazený) odhad, tak způsobů, jak na mřížku 5x5 umístit první loď je (2x1) je 40 a pro každou pozici první lodi existuje minimálně 20 pozic (hrubě podceněný odhad, reálně je to ve většině případů kolem 30-40), jak k ní přiřadit druhou loď, což mi dává dohromady 800 možností (což je hodně podsazené minimum), proto bych se tedy chtěl zeptat, zda jsem nějak špatně pochopil zadání (případně se nějak hodně mýlím ve svých odhadových výpočtech) nebo zda je chyba v ukázkovém výstupu

děkuji

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: Zbojníci

Příspěvek od blazeva1 »

Pardon,
to jsem si spletl ... banditi proti sobě hrají, a rozestavují svoje lodě na mřížce. Jediné, na čem při hře záleží je, jestli na políčku loď je nebo není. V případě, že jsou lodě stejně dlouhé, tak jsou nerozlišitelné.

V zadání jsem to překontroloval, a mělo by to být v pořádku.

Tenhle speciální případ se bude v řešení kontrolovat, ale jeho zanedbání nebude postiženo velkou ztrátou bodů.

Vašek

jakubs
Příspěvky: 6
Registrován: 14-09-2017 05:39
Škola: Gymnázium Brno-Řečkovice Terezy Novákové 2, p. o.
Rok ukončení studia: 2019

Re: Zbojníci

Příspěvek od jakubs »

Jestli teda záleží pouze na tom, zda na políčku loď je či není, není potom například situace ve vzorovém řešení na pozici [3;3] a [4;1] (číslováno od jedničky z levého horního okraje formátem [řádek; sloupec]) to stejné rozmístění (viz obrázek)? A nebo to funguje tak, že v případě, že jsou lodě jinak dlouhé, tak je lze brát jako obarvené a pokud jsou stejně dlouhé, pak ne?
Výběr_001.png
Výběr_001.png (2.92 KiB) Zobrazeno 13255 x
Díky za odpověď

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: Zbojníci

Příspěvek od blazeva1 »

Je to tak jak píšeš ...lze to brát tak, že stejně dlouhé lodě jsou nerozlišitelné a různě dlouhé lodě jsou rozlišitelné.
Na obrázku jsou toto 2 různé případy.

Vašek

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: Zbojníci

Příspěvek od blazeva1 »

Vyjasnil jsem to i v zadání a přidal pár vstupů, aby se dalo řešení lépe ověřit.

Vašek

Zamčeno