Jak rozwiązać zadanie Jędnoręki Bandyta?

Question

Bajtek przyszedł do kasyna, gdzie od razu zainteresował go automat do gry w jednorękiego bandytę. Najważniejszą częścią automatu są trzy bębny. Każdy z nich podzielony jest na równych pól, na których namalowane są różne symbole. Jest możliwych symboli i każdy z nich występuje na każdym bębnie dokładnie raz. Dla uproszczenia ponumerujmy symbole liczbami od 1 do . Poniższy rysunek przedstawia przykładowy automat z trzema bębnami podzielonymi na pól:

Po pociągnięciu wajchy, każdy z bębnów przesuwa się cyklicznie o pewną liczbę pozycji. Wygrana gracza zależy od liczby poziomych rzędów, w których znajdą się trzy takie same symbole.

Bajtek wie, że jednoręki bandyta może zabrać wszystkie jego pieniądze, więc wolałby najpierw stwierdzić, jaka może być jego maksymalna wygrana. Pomóż mu i wyznacz liczbę rzędów, w których mogą znaleźć się trzy takie same symbole przy najkorzystniejszym ustawieniu bębnów.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą wielkość bębnów. Trzy następne wiersze opisują układy symboli na poszczególnych bębnach.

Opis bębna składa się z parami różnych liczb całkowitych (), gdzie oznacza symbol znajdujący się na pozycji .

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej liczbie rzędów, w których mogą się jednocześnie znaleźć po trzy takie same symbole.

Przykład

Dla danych wejściowych:

5
1 5 4 3 2
1 3 2 4 5
2 1 5 4 3

poprawną odpowiedzią jest:

3

 

Jakieś pomysły?

Comments

Jakiś hype na dawanie minusów chyba nastał. Pytanie zgodne z regulaminem a kolega prosi tylko o wskazówkę jak zacząć.

Answer 1

Baaardzo bym chciał pomóc, ale znam aktualnie(14VII2017) trwający zdalny contest, w którym to zadanie pojawia się po raz pierwszy (przed contestem nie dało się go znaleźć). Jestem więc zmuszony milczeć aż do sierpnia i proszę innych o respektowanie tego contestu, nawet jeśli to tylko kwalifikacje :X  LINK

Ok, contest się skończył.
Podpowiedź jest taka: jeśli wymyślimy jakąś reprezentacje obracania bębnów, która pozwoli danej liczbie być w jednym rzędzie i ta reprezentacja będzie jednoznaczna (wymślona tak, by nie dało się opisać obrotów dla tej samej liczby na dwa sposoby), to możemy taką reprezentacje przygotować dla każdej liczby od 1 do n i zliczyć dla każdej reprezentacji ile razy się powtórzyła wśród wszystkich reprezentacji, ta która powtórzyła się najwięcej razy oznacza ile najwięcej może być takich samych liczb w rzędzie. To, jaka może być reprezentacja, jak szybko zaimplementować te wszystkie rzeczy pozostawiam Tobie =)