Quatre en ratlla P31806

Simuleu diverses partides de quatre en ratlla en un tauler d’n columnes infinitament alt.

Hi ha dos jugadors, blau i vermell, que juguen alternadament. Cada partida la comença el blau. Per torns, els jugadors trien una columna del tauler i hi posen una fitxa del seu color, en la fila més baixa de la columna que no estigui ja ocupada. Si en algun moment hi ha quatre o més fitxes adjacents en ratlla, ja sigui en horitzontal, vertical o diagonal, el jugador que acaba de jugar guanya, i la partida acaba immediatament.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, el nombre de columnes del tauler, m, el nombre (màxim) de tirades de cada jugador, i les 2m jugades, cadascuna indicada amb una columna entre 0 i n − 1. Suposeu 4 ≤ n ≤ 100, i 4 ≤ m ≤ 10⁵.

Sortida

Per a cada cas, digueu quin jugador ha guanyat i en quin moviment (començant en 1), o si hi ha hagut un empat perquè s’han fet totes les jugades i ningú ha aconseguit cap quatre en ratlla.