Codeforces Round 908 (Div. 2) |
---|
Закончено |
Рассмотрим игру, в которую играют два человека: A и B. Эта игра характеризуется двумя целыми положительными числами: $$$X$$$ и $$$Y$$$.
Игра состоит из сетов, каждый сет состоит из розыгрышей. В каждом розыгрыше побеждает ровно один из игроков — либо A, либо B. Сет заканчивается ровно тогда, когда один из игроков набирает $$$X$$$ побед в розыгрышах в течении этого сета. Этот игрок объявляется победителем сета. Игроки разыгрывают сеты до тех пор, пока один из них не наберёт $$$Y$$$ побед в сетах. После этого игра заканчивается, и этот игрок объявляется победителем всей игры.
Вы только что посмотрели игру, но не заметили, кого объявили победителем. Вы запомнили, что в течение игры было сыграно $$$n$$$ розыгрышей, а также кто из игроков победил в каждом из розыгрышей. Однако, вам неизвестны значения $$$X$$$ и $$$Y$$$. По имеющейся информации определите, кто из игроков победил во всей игре — A или B. Если информации недостаточно, чтобы определить победителя, вы также должны сообщить об этом.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \leq n \leq 20)$$$ — количество сыгранных розыгрышей в течение игры.
Вторая строка каждого набора входных данных содержит последовательность $$$s$$$ длины $$$n$$$, состоящую из символов $$$\texttt{A}$$$ и $$$\texttt{B}$$$. Если $$$s_i = \texttt{A}$$$, это означает, что в $$$i$$$-м розыгрыше победил игрок A. Если $$$s_i = \texttt{B}$$$, это означает, что в $$$i$$$-м розыгрыше победил игрок B.
Гарантируется, что заданная последовательность розыгрышей соответствует хотя бы одному корректному сценарию игры при некоторых параметрах $$$X$$$ и $$$Y$$$.
Для каждого набора входных данных в отдельной строке выведите:
75ABBAA3BBB7BBAAABA20AAAAAAAABBBAABBBBBAB1A13AAAABABBABBAB7BBBAAAA
A B A B A B A
В первом наборе входных данных игра могла проходить с параметрами $$$X = 3$$$, $$$Y = 1$$$. Игра состояла из $$$1$$$ сета, в котором победил игрок A, так как он первым выиграл $$$3$$$ розыгрыша. При таком сценарии победителем является игрок A. Также игра могла проходить с параметрами $$$X = 1$$$, $$$Y = 3$$$. Можно показать, что не существует таких $$$X$$$ и $$$Y$$$, при которых победителем будет игрок B.
Во втором наборе входных данных все розыгрыши выиграл игрок B. Несложно показать, что тогда игрок B гарантированно является победителем игры.
В четвёртом наборе входных данных игра могла проходить с параметрами $$$X = 3$$$, $$$Y = 3$$$:
В итоге первым игроком, выигравшим $$$3$$$ сета, был игрок B. Он и считается победителем игры.
Название |
---|