Juego AB

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

ToOma_KFP, wizard98

Problem types

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Fernando y su amigo Ricardo están jugando con un string $S$ ~S~ de longitud $N(1 \le N \le 10^5)$ ~N(1 \le N \le 10^5)~ compuesto por caracteres $\{A, B\}$ ~\{A, B\}~. Los dos jugadores se turnan para jugar, Fernando juega primero. Un movimiento consiste en elegir una subcadena no vacía de $S$ ~S~ que no se superponga con ninguna subcadena elegida anteriormente. El juego termina cuando todos los elementos del $S$ ~S~ son elegidos, y el ganador del juego es el jugador que seleccionó menos $A$ ~A~ entre sus subcadenas. En caso de que ambos elijan el mismo número de $A$ ~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)$ ~T(1 \le T \le 5)~, el número de casos d prueba a procesar. Le siguen $2 \cdot T$ ~2 \cdot T~ líneas donde cada par especifica para cada caso, el número $N$ ~N~ que es el tamaño de la cadena, y la siguiente línea contiene la cadena $S$ ~S~.

Salida

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

Ejemplo de Entrada

3
2
AA
9
AABABABBA
11
ABAABBABBBA

Ejemplo de Salida

-1
F
R

Comments

0

Kojima_Cubano_veriffedXD commented on Jan. 30, 2024, 3:23 a.m.

Coincido con aniervs, me gustaría una explicación de pq esto funciona, quien me lo pueda explicar mi numero esta en mi info del DMOJ

0

Yosbany_ossoby commented on Sept. 27, 2022, 4:56 p.m. ← edited →

este problema sale con un juego nim clasico como dice aniervs. yo lo hice por el principio del juego convirtiendolos en numeros binarios muy lindo este problema

1

Osvaldo23 commented on Sept. 24, 2022, 12:15 a.m.

Sub-cadena,no esta bien definido,es una cadena de elementos consecutivos,de la original?

1
linkyless commented on Sept. 25, 2022, 2:39 a.m.
Una subcadena es cualquier secuencia de caracteres que se encuentra en una cadena.

Ejemplo:

OSV tiene como subcadena a:

OS

SV

OSV

O

S

V

PD: La última es una subcadena vacía.

-4

Primervirgen commented on April 15, 2020, 9:40 p.m.

Este problema tiene una explicación muy mala....

-5

dmesadiaz commented on March 12, 2020, 3:53 a.m.

No entiendo bien este problema, no se de q tamaño puede ser el subarreglo de S q ellos pueden selecionar poq si se puede seleccionar todo siempre ganaria el q empieza no? Por favor podria alguien explicarme.

This comment is hidden due to too much negative feedback. Show it anyway.

1

aniervs commented on March 13, 2020, 4:40 p.m.

A ver, el problema lo gana el que tiene menos A.

-5

dmesadiaz commented on March 14, 2020, 4:51 p.m.

Pero como se cuantas As le corresponden a cada cual?

This comment is hidden due to too much negative feedback. Show it anyway.

0

aniervs commented on March 14, 2020, 5:47 p.m.

Cada uno conoce la estrategia óptima. Si ambos juegan óptimamente, tienes que decir cuál gana.

0

aniervs commented on Feb. 17, 2020, 6:28 p.m. ← edited →

Este problema yo lo resolví reduciéndolo a un juego Nim clásico: tenemos $n$ ~n~ pilas, la pila $i$ ~i~ tiene $a_i$ ~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.