Stránka 1 z 1

Zbojníci

Napsal: 15-09-2017 14:45
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

Re: Zbojníci

Napsal: 15-09-2017 16:05
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

Re: Zbojníci

Napsal: 15-09-2017 20:05
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

Re: Zbojníci

Napsal: 18-09-2017 13:42
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

Re: Zbojníci

Napsal: 18-09-2017 20:24
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 13282 x
Díky za odpověď

Re: Zbojníci

Napsal: 20-09-2017 20:54
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

Re: Zbojníci

Napsal: 20-09-2017 22:07
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