Zbojníci

[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]

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

[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]

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]

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 (2.92 KiB) Zobrazeno 26730 x

Díky za odpověď

[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]

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

Vašek