Algorytm programowania: znalezienie zwycięzcy konkursu

Question

Będę rywalizować w OBI (brazylijska olimpiada informatyki, w języku angielskim) i próbuję wykonać kilka ćwiczeń z ostatnich lat. Ale nie mogę znaleźć rozwiązanie dla tego ćwiczenia (przetłumaczyłem go, więc nie może być kilka błędów):

Chocolate konkurencji

Carlos i Paula właśnie dostała torebkę czekoladowych kulek. Jak oni jedzą wszystko zbyt szybko, zrobili konkurs:

• Będą jeść na przemian, jeden po drugim (Paula zawsze zaczyna).
• Za każdym razem mogą jeść tylko od 1 do M kuleczek, M ustalonych przez matkę Pauli, aby się nie dusić.
• Jeśli jeden zjada kulki K w swojej turze, następny nie może jeść kulki K.
• Kto nie może grać zgodnie z powyższymi zasadami, przegrywa.

W poniższym przykładzie z M = 5 i 20 piłek, Carlos zdobył:

Who plays  How many ate  Balls left 

            20 
Paula   5     15 
Carlos   4     11 
Paula   3     8 
Carlos   4     4 
Paula   2     2 
Carlos   1     1 

Należy zauważyć, że w końcu, Carlos nie mógł jeść 2 kulki, aby wygrać, bo Paula jedli 2 w jej ostatniej turze. Ale Paula nie mogła zjeść ostatniej piłki, ponieważ Carlos zjadł 1 w swojej ostatniej turze, więc Paula nie może grać i przegrywa.

Obie są bardzo inteligentne i grają optymalnie. Jeśli istnieje sekwencja zwojów, która zapewnia mu/jej zwycięstwo niezależnie od zakrętów innych, on/ona zagra te sekwencje.

Zadanie:

Twoim zadaniem jest, aby dowiedzieć się, kto wygra konkurs, jeśli zarówno grać optymalnie.

Wejście:

Wejście zawiera tylko jedną grupę testową, która powinna być odczytywane ze standardowego wejścia (zwykle klawiatura).

Wejście zawiera 2 liczby całkowite N (2 ≤ N ≤ 1000000) i M (2 ≤ M ≤ 1000), będące N liczbą kulek i M liczbą dozwoloną na obrót.

wyjściowa:

Twój program powinien wypisać w standardowe wyjście jeden wiersz zawierający nazwę zwycięzcy.

Przykłady:

Input:   Output: 
5 3    Paula 
20 5   Carlos 
5 6    Paula 

Próbowałem rozwiązać ten problem, ale nie mam pojęcia jak to zrobić.

Rozwiązanie w C można znaleźć tutaj: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt Ale nie mogę zrozumieć algorytmu. Ktoś zadał pytanie na temat tego problemu w innej witrynie, ale nikt nie odpowiedział.

Czy możesz wyjaśnić mi algorytm?

Oto oczekiwanych rezultatów programu: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

Załóżmy, że mamy funkcję boolowską FirstPlayerWin (FPW), która przyjmuje dwa argumenty: liczba czekoladek po lewej (c) i ostatni ruch (l), tj. Liczba czekoladek pobranych w poprzedniej rundzie, która wynosi 0 w pierwszy ruch. Procedura zwraca wartość true wtedy i tylko wtedy, gdy pierwszy gracz, który zagra w tej sytuacji, ma gwarancję wygranej.

sprawa podstawowa odpowiada FPW (0, l) = False dla każdego L! = 1

W przeciwnym razie, w celu obliczenia FPW (C, l), FPW (C, l), jest ważne, jeśli dla każdego x < = M, x < = c, x! = L, FPW (c - x, x) jest fałszywe. W przeciwnym razie jest to fałsz. To tutaj kopie dynamiczne programy, ponieważ teraz obliczanie FPW jest zredukowane do obliczania FPW dla mniejszych wartości c.

Przechowywanie wpisów dla tego sformułowania wymagałoby jednak wpisów w tabelach N * M, gdzie jako wskazane rozwiązanie używane są tylko wpisy w tabeli 2N.

Powodem tego jest to, że jeśli FPW (c, 0) jest prawdziwe (pierwszy gracz wygrywa, jeśli dowolny ruch jest dostępny przy liczbie czekolady c), ale FPW (c, x) jest fałszywe dla x> 0, FPW (c , y) dla i y! = x musi być prawdziwe. Dzieje się tak dlatego, że odmowa wykonania ruchu x powoduje utratę gracza, tj. Gracz wygrałby tylko poprzez grę x, wtedy ruch x jest dostępny, gdy y jest zbanowany w zamian. W związku z tym wystarczy przechowywać dla każdego count 'c' co najwyżej jeden zakazany ruch, który powoduje, że gracz przegrywa. Więc możesz zmienić problem programowania dynamicznego, aby zamiast przechowywać pełną dwuwymiarową tablicę FPW (c, x) masz dwie tablice, jedna przechowuje wartości FPW (c, 0), a druga przechowuje pojedyncze zabronione ruchy, które powodują pierwszy gracz, który przegra, zamiast wygrywać, jeśli taki istnieje.

Sposób uzyskania dokładnego tekstu cytowanego programu C jest pozostawiony ćwiczeniu dla czytelnika.

Answer 2

Myślę, że to kolejny zakamuflowany ćwiczenie programowania dynamicznego. Stan gry opisują dwie wielkości: liczba pozostałych kul i liczba piłek zjedzonych w poprzednim ruchu. Gdy liczba pozostałych kulek to < = M, gra jest wygrana (jeśli liczba pozostałych nie jest równa liczbie zjedzonych w poprzednim ruchu) lub przegrana (jeśli tak - nie można jeść wszystkich piłek, oraz twój przeciwnik może zjeść kulki, które zostawiasz).

Jeśli udało ci się wypracować sytuację, w której wygrywasz/przegrywasz dla wszystkich liczb piłek do H, oraz wszystkich możliwych liczb piłek zjedzonych przez poprzedniego gracza i zapisanych w tabeli, wtedy możesz opracować odpowiedzi dla wszystkie liczby kulek do H + 1. Gracz z H + 1 piłkami i kulami zjedzonymi w poprzednim ruchu rozpatrzy wszystkie możliwości - zjedz piłki za i = 1 do M, z wyjątkiem nielegalnej wartości k, pozostawiając pozycję z kulkami H + 1-i i poprzednią ruch i. Mogą skorzystać z tabeli dającej sytuację, w której przegrywają, aż do H kulek, aby spróbować znaleźć legalne k, które da im wygraną. Jeśli uda im się znaleźć taką wartość, pozycja H + 1/k wygrywa. Jeśli nie, to jest strata, więc mogą przedłużyć stół, aby pokryć piłki do H + 1, i tak dalej.

Nie przejrzałem całego tego nieskomentowanego przykładowego kodu, ale wygląda na to, że może to być coś podobnego - za pomocą dynamicznego programowania, takiego jak rekursja do zbudowania tabeli.