Dobra, to daję (na wszelki wypadek rozpisałem sobie odpowiedź już wcześniej
).
Rozwiązanie wersji "a" (tej drugiej nadal nie zrobiłem):
Oznaczmy początkowe położenie dźwigni jako 0.
Następnie spośród n krasnoludków wybierzmy jednego Krasnoludka-Strażnika (KS). Pozostałe n-1 będziemy nazywali Zwykłymi Krasnoludkami (ZK).
Algorytm postępowania ZK:
Zadaniem każdego ZK jest dokładnie raz w życiu przesunąć dźwignię z położenia 0 na 1, przy czym powinien zrobić to najwcześniej jak to możliwe.
Czyli:
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 1, to nic nie robi
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 0, a jeszcze nigdy jej nie przestawił, to przesuwa ją do położenia 1
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 0, ale pamięta, że już kiedyś ją przesuwał, to nic nie robi
Algorytm postępowania KS:
Zadaniem KS jest podać we właściwym momencie odpowiedź czarownikowi.
KS przechowuje w swojej pamięci zmienną całkowitą x, której początkowa wartość wynosi 0 (zawsze i wszędzie pamiętajmy o zerowaniu zmiennych!
http://roflcopter.pl/2861 ).
Kiedy KS wchodzi do komnaty:
- jeśli dźwignia jest ustawiona na 0, to nic nie robi
- jeśli dźwignia jest ustawiona na 1 to resetuje ją, przesuwając do położenia 0 i jednocześnie inkrementuje (czyli zwiększa wartość o 1) zmienną x w swojej pamięci
- jeśli zachodzi x=n-1, to wiadomo, że wszystkie krasnoludki były już w komnacie z dźwignią, zatem KS może powiadomić o tym czarownika
I jak? Pasuje takie rozwiązanie czy gdzieś jest jakaś nieścisłość/błąd? Czy może coś rozjaśnić w wytłumaczeniu?
Teraz czekam na krytykę