Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Kości zostały rzucone


W pewnym bajtockim turnieju gry w kości stawiło się wielu znanych na całym świecie graczy. Rozegrano tu wiele fascynujących partii, których przebiegi zostaną udostępnione w bajtockiej gazecie. Zasady partii są następujące:

każdy z dwóch graczy dysponuje dwiema kostkami do gry. Między dwoma zawodnikami zostaje rozegranych n partii. W pojedynczej partii wygrywa ten, który wyrzuci w sumie większą liczbę oczek.

Niestety z jakiś powodów zamiast liczb oczek komputer zanotował ich odpowiedniki literowe ze zbioru: {A, B, C, D, E, F}. Dodatkowo wiadomo, że litera A nie koniecznie odpowiada jednemu oczku, litera B dwom oczkom itd. Na podstawie wyników określ jakie wartości zostały przypisane literom. 

 

Wejście

W pierwszym wierszu jedna liczba określająca liczbę zestawów danych. (nie więcej niż tysiąc).

Każdy zestaw danych składa się z jednej liczby n określającej ilość partii (0 < n < 1000).

Każda partia składa się z czterech liter i jednego znaku ze zbioru {r, 1, 2}. Pierwsze dwie litery to oczka wyrzucone przez pierwszego gracza, następne dwie przez drugiego, natomiast znak r oznacza, że w tej partii jest remis, 1, że wygrał gracz nr 1, a 2 gracz nr 2.

Wyjście

Dla każdego zestawu danych kolejne litery od A do F oraz przyporządkowana im liczba oczek (między literą a liczbą oczek jest znak "-") lub napis "Brak jednoznacznej odpowiedzi" w przypadku, gdy nie da się jednoznacznie udzielić odpowiedzi.

Przykład

Wejście:
2
6
A B C D 2
C D B F r
A C B D r
F A B E 1
D F C E 1
B C A C 2
6
A C E F r
B E C F 1
A C E A 2
A E C C r
A A F C r
D D B E r
Wyjście:
Brak jednoznacznej odpowiedzi
A-2 B-6 C-3 D-5 E-4 F-1
Wyjaśnienie
Dla pierwszego zestawu danych istnieją co najmniej dwa różne kombinacje jakie możemy przypisać do liter np.:
A-2 B-1 C-3 D-4 E-5 F-6 
A-3 B-1 C-2 D-4 E-6 F-5 
W drugim zestawie jest tylko jedno takie dopasowanie.

Szkic rozwiązania

Najprostszym rozwiązaniem jest analiza wszystkich permutacji zbioru $$X= \{1, 2, 3, 4, 5, 6\}$$ , przyporządkowując dla każdej permutacji odpowiedniki literowe w kolejności $$el1 - A, el2 - B, .., el6 - F$$, gdzie $$el1, el2, ..., el6$$ to porządek liczb w danej permutacji:

Najpierw podstawiamy za litery zbiór $$\{1-A, 2-B, 3-C, 4-D, 5-E, 6-F\}$$. Następnie sprawdzamy całą partię. Jeśli coś nie będzie się zgadzać, przerywamy pętlę, w przeciwnym razie, permutujemy zbiór $$X$$ i tworzymy następne przyporządkowanie: $$\{1-A, 2-B, 3-C, 4-D, 6-E, 5-F\}$$. Czynności te powtarzamy do momentu otrzymania permutacji $$\{6, 5, 4, 3, 2, 1\}$$ lub sytuacji, gdy po raz drugi będzie się wszystko zgadzać - wtedy brak jednoznacznej odpowiedzi.

Jak łatwo zauważyć, dla danego zbioru jest $$6!=720$$ możliwości i tyle należy zbadać, aby stwierdzić, czy jest więcej niż jedno dopasowanie. Dobrym pomysłem, jest użycie funkcji $$nextpermutation$$ z języka C++ do permutowania zbioru $$X$$.

Oprócz takiego rozwiązania były zgłoszenia oparte na grafach oraz próby odgadnięcia wartości liter analizując przebieg partii.