Juego AB

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
Problem types
Allowed languages
C, C++, Java, Pascal, Python

Fernando y su amigo Ricardo están jugando con un string \(S\) de longitud \(N(1 \le N \le 10^5)\) compuesto por caracteres \(\{A, B\}\). Los dos jugadores se turnan para jugar, Fernando juega primero. Un movimiento consiste en elegir una subcadena no vacía de \(S\) que no se superponga con ninguna subcadena elegida anteriormente. El juego termina cuando todos los elementos del \(S\) son elegidos, y el ganador del juego es el jugador que seleccionó menos \(A\) entre sus subcadenas. En caso de que ambos elijan el mismo número de \(A\) el juego es un empate. Fernando quiere que descubras quien ganará el juego dado el string inicial, si ambos jugadores juegan de forma óptima.

Entrada

La primera línea de entrada contiene un número entero \(T(1 \le T \le 5)\), el número de casos d prueba a procesar. Le siguen \(2 \cdot T\) líneas donde cada par especifica para cada caso, el número \(N\) que es el tamaño de la cadena, y la siguiente línea contiene la cadena \(S\).

Salida

La salida debe contener el resultado del juego para cada caso de prueba. Si Fernando gana, imprima \(F\), si Ricardo gana, imprima \(R\) y si el juego termina en un empate, imprima \(-1\).

Ejemplo de Entrada

3
2
AA
9
AABABABBA
11
ABAABBABBBA

Ejemplo de Salida

-1
F
R

Comments


  • 1
    aniervs  commented on Feb. 17, 2020, 1:28 p.m. edited

    Este problema yo lo resolví reduciéndolo a un juego Nim clásico: tenemos \(n\) pilas, la pila \(i\) tiene \(a_i\) piedras, y dos jugadores, en cada turno un jugador puede seleccionar una cantidad de piedras mayor que 0 de una de las pilas y quitar esa cantidad, gana el jugador que quite la última piedra. Es conocido que este juego lo gana el primer jugador si y solo si \(a_1 \text{^ } a_2 \text{^ } \dots\text{^ } a_n\ne0\), pero me gustaría ver una demostración de eso.