Problem L
I Could Have Won

“We will be closing in about 5 minutes. Thank you for visiting the ICPC gym today.”

With this announcement, Alice and Bob stopped playing their rock-paper-scissors marathon in the middle of the $10$th game. Each player scores a point if their throw beats the other player’s throw. Each game was played by the first-to-11 rule, meaning that whoever scores $11$ points first wins the game. Today, Bob narrowly defeated Alice by a single game; he scored 11 points first in five games, while Alice only scored 11 points first in four games.

After carefully inspecting how each game was played, however, Alice realized that she could have won more games than Bob if they played under slightly different rules, such as first-to-5 or first-to-8, instead of the regular first-to-11.

Given the sequence of points scored by Alice and Bob, determine all values of $k$ such that Alice would have won more games than Bob under the first-to-$k$ rule.

Both Alice and Bob start with zero points at the beginning of a game. As soon as one player reaches $k$ points, that player wins the game, and a new game starts. Alice wins a game if she scores $k$ points before Bob does. Neither player wins the game if it’s interrupted by the gym closing before either player reaches $k$ points.


The single line of input consists of a string of uppercase letters “A” or “B”, denoting who scored each point from the beginning of the rock-paper-scissors marathon. The length of the string is between $1$ and $2\, 000$ letters, inclusive. “A” means Alice scored the point, “B” means Bob scored the point.


On the first line, output the number of positive integers $k$ for which a first-to-$k$ rule would have made Alice win more games than Bob. If this number isn’t zero, on the next line output all such values of $k$ in increasing order, separated by spaces.

Sample Input 1 Sample Output 1
3 6 7
Sample Input 2 Sample Output 2
2 4

Please log in to submit a solution to this problem

Log in