3383 - CompuTenis Reloaded 3383 - CompuTenis Recargado 3383 - CompuTenis Reloaded

Statistics Sub: 205 | AC: 139 | AC%: 67,80 | Score: 1,20
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Juan Cruz Piñero
Added by fidels (2015-10-12)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

You may remember from a previous edition of TAP about CompuTenis, that sport specially adapted to a public without any mensurable physical qualities and whose rules involve coding with your elbow glued to your ear. This time we will have another problem concerning this exciting subject, in case you found the solution to that one too easy.

Once more, for the purposes of this problem the only thing you have to know about CompuTenis is that two players, which we will call A and B, compete in a match. The match is won by the player who first wins S sets, each set being composed of one or more games. In each set the two players play as many games as is required for one of them to win in at least J games, with a difference of at least D games won in excess of his opponent. The player satisfying both of these conditions is then the winner of the corresponding set.

The Modern Club Association (MCA) has recently found a trove of records of pre-historic CompuTenis matches. Each record consists of a string composed of N characters 'A' or 'B', indicating which player won each of the games the match had, in the order in which they occurred. Now the MCA wants to know, for each record, what the result of the match was.
Posiblemente recuerden de un TAP anterior al CompuTenis, aquel deporte especialmente adaptado a un público sin estado físico mensurable y cuyas reglas involucran programar con el codo pegado a la oreja. En esta ocasión volvemos a tener un problema sobre esta apasionante disciplina, por si la solución de aquel problema les resultó demasiado fácil.

Nuevamente, para los efectos de este problema lo único que hace falta saber sobre el CompuTenis es que en un partido compiten dos jugadores, a los que denominaremos A y B. Gana el partido aquel jugador que gane primero S sets, cada uno de los cuales está compuesto por uno o más juegos. En cada set se disputan tantos juegos como hagan falta para que alguno de los dos jugadores venza en al menos J juegos, con una diferencia de al menos D juegos ganados más que su oponente. Aquel jugador que cumpla con ambas condiciones es entonces el ganador del set correspondiente.

La Asociación de Clubes Modernos (ACM) encontró recientemente un registro de partidos de CompuTenis prehistóricos. Cada registro consiste en una cadena compuesta por N caracteres 'A' o 'B', indicando el jugador que ganó cada uno de los N juegos que tuvo el partido, en el orden en el que fueron sucediendo. Ahora la ACM quiere saber, para cada registro, cuál fue el resultado del partido.
You may remember from a previous edition of TAP about CompuTenis, that sport specially adapted to a public without any mensurable physical qualities and whose rules involve coding with your elbow glued to your ear. This time we will have another problem concerning this exciting subject, in case you found the solution to that one too easy.

Once more, for the purposes of this problem the only thing you have to know about CompuTenis is that two players, which we will call A and B, compete in a match. The match is won by the player who first wins S sets, each set being composed of one or more games. In each set the two players play as many games as is required for one of them to win in at least J games, with a difference of at least D games won in excess of his opponent. The player satisfying both of these conditions is then the winner of the corresponding set.

The Modern Club Association (MCA) has recently found a trove of records of pre-historic CompuTenis matches. Each record consists of a string composed of N characters 'A' or 'B', indicating which player won each of the games the match had, in the order in which they occurred. Now the MCA wants to know, for each record, what the result of the match was.

Input specification

The first line contains four integers N, S, J and D. The value N represents the number of games in the record to be analyzed (1 <= N <= 10^5). The value S indicates the number of sets a player is required to win in order to win the match (1 <= S <= 10). The value J is the minimum number of games it is necessary to win in order to win a set, whereas the value D indicates that a player should win at least that number of games more than his opponent in order to win the set (1 <= D <= J <= 100). The second line contains a string composed of N characters 'A' or 'B'. The i-th character of the string indicates which player won the i-th game played in the match. The input string will represent a valid record of a complete match.
La primera línea contiene cuatro enteros N, S, J y D. El valor N representa la cantidad de juegos presentes en el registro a analizar (1 <= N <= 10^5). El valor S indica la cantidad de sets que es necesario ganar para ganar un partido (1 <= S <= 10). El valor J es la cantidad mínima de juegos que es necesario ganar para ganar un set, mientras que el valor D indica que un jugador debe ganar al menos esa cantidad de juegos más que su oponente para ganar el set (1 <= D <= J <= 100). La segunda línea contiene una cadena compuesta por N caracteres 'A' o 'B'. El i-ésimo caracter de la cadena indica qué jugador ganó el i-ésimo juego disputado en el partido. La cadena de la entrada representa un registro válido de un partido completo.
The first line contains four integers N, S, J and D. The value N represents the number of games in the record to be analyzed (1 <= N <= 10^5). The value S indicates the number of sets a player is required to win in order to win the match (1 <= S <= 10). The value J is the minimum number of games it is necessary to win in order to win a set, whereas the value D indicates that a player should win at least that number of games more than his opponent in order to win the set (1 <= D <= J <= 100). The second line contains a string composed of N characters 'A' or 'B'. The i-th character of the string indicates which player won the i-th game played in the match. The input string will represent a valid record of a complete match.

Output specification

Print a single line containing two integers representing the number of sets won by player A and player B, respectively.
Imprimir en la salida una línea conteniendo dos enteros que representan la cantidad de sets ganados por el jugador A y por el jugador B, respectivamente.
The first line contains four integers N, S, J and D. The value N represents the number of games in the record to be analyzed (1 <= N <= 10^5). The value S indicates the number of sets a player is required to win in order to win the match (1 <= S <= 10). The value J is the minimum number of games it is necessary to win in order to win a set, whereas the value D indicates that a player should win at least that number of games more than his opponent in order to win the set (1 <= D <= J <= 100). The second line contains a string composed of N characters 'A' or 'B'. The i-th character of the string indicates which player won the i-th game played in the match. The input string will represent a valid record of a complete match.

Sample input

10 5 2 1
AAAAAAAAAA

Sample output

5 0

Hint(s)

Sample input #2
21 3 3 2
AABABBBABBBABABABBABB

Sample output #2
1 3
Sample input #2
21 3 3 2
AABABBBABBBABABABBABB

Sample output #2
1 3
Sample input #2
21 3 3 2
AABABBBABBBABABABBABB

Sample output #2
1 3

Recommendation

We have carefully selected several similar problems: 3376 | 2441 | 2534 | 2141 | 3232 | 3344