TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Dobrý den, chtěl bych váš poprosit o nějaký nápad (kód), pro tuto zákeřnou úlohu:
Je dána čokoláda o rozměrech 3xN čtverečků. Čokoláda má na některých čtvereččích umístěnu hrozinku. V zadání je dáno číslo N ("délka čokolády") a souřadnice [x;y] políček s hrozinkami. Určete počet způsobů, kolika můžeme rozdělit čokoládu na obdélníky 1x2, aby žádný z obdélníků neobsahoval hrozinku a tak byla čokoláda rozdělena na bezhrozinkové obdélníky 2x1 a čtverečky 1x1 s hrozinkou.
K zadání byl přiložen tento obrázek:
A jeho řešení: Pro čokoládu vlevo je 0 možností a pro čokoládu vpravo 3 možnosti.
Zkoušel jsem vyřešit případy, kdyby čokoláda hrozinky neobsahovala, a to pro N=2 a N=3. Přišel jsem na to, že pro případ N=2 jsou 3 možnosti a pro N=3 je 0 možností (je lichý počet políček, tak jedno vždy zbyde). Můj závěr pro čokoládu bez hrozinek je 3^(N/2) možností pro sudé N a 0 možností pro každé liché N. Bohužel ale nevím jak vytvořit algoritmus, který by to zjistil i pro čokoládu s hrozinkami :(.
Už jsem se ptal na konkurenčním fóru, bohužel nikdo mi nedokázal odpovědět a s problémem si nevěděli rady. Děkuji za případné odpovědi a doufám, že jste tu větší machři než na jiném nejmenovaném fóru.
