Szachwonica 8x*
-
studciak123
- Użytkownik
- Posty: 29
- Rejestracja: 19 lis 2017, o 17:30
- Płeć: Mężczyzna
- Lokalizacja: A kto to wie
- Podziękował: 11 razy
Szachwonica 8x*
Czy po usunięciu z szachownicy \(\displaystyle{ 8}\) x \(\displaystyle{ 8}\) jednego pola czrnego i jednego białego zawsze można pokryć resztę szachownicy kostkami domina? Jedna kostka ma rozmiar dwóch pól. Usunięte pola nie muszą ze sobą sąsiadować.
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Szachwonica 8x*
To zadanie z 41 OM - I - 4:
Ponadto to zadanie było też na II etapie II Olimpiady Informatycznej - zadanie Szachownica (tam usuwano trzy pola).
W skrócie rozwiązanie z OI polega na przerobieniu szachownicy na graf w standardowy sposób (pola to wierzchołki, łączymy krawędziami pola sąsiadujące jednym bokiem) i znalezieniu ścieżki Hamiltona w pozostałym grafie tak, aby po usunięciu dwóch zadanych pól ścieżka rozpadała się na części o parzystych długościach. Następnie układamy kostki domina po kolei na częściach tej ścieżki.
Ponadto to zadanie było też na II etapie II Olimpiady Informatycznej - zadanie Szachownica (tam usuwano trzy pola).
W skrócie rozwiązanie z OI polega na przerobieniu szachownicy na graf w standardowy sposób (pola to wierzchołki, łączymy krawędziami pola sąsiadujące jednym bokiem) i znalezieniu ścieżki Hamiltona w pozostałym grafie tak, aby po usunięciu dwóch zadanych pól ścieżka rozpadała się na części o parzystych długościach. Następnie układamy kostki domina po kolei na częściach tej ścieżki.