Разбор: Алиса и Боб играют в простую игру

Обозначения и определения

• $N$ — количество раундов в игре
• $A_{\text{wins}}$ — количество раундов, выигранных Алисой
• $B_{\text{wins}}$ — количество раундов, выигранных Бобом
• Поскольку ровно один игрок выигрывает каждый раунд: $A_{\text{wins}} + B_{\text{wins}} = N$

Подзадача 1 ($N = 1$)

Когда есть только один раунд, победитель этого единственного раунда является общим победителем игры.

Алгоритм:

1. Прочитать единственный символ из ввода
2. Если символ A, Алиса выигрывает игру
3. Если символ B, Боб выигрывает игру

Временная сложность: $O(1)$
Пространственная сложность: $O(1)$

Подзадача 2 (Общий случай, $N \leq 9$)

Для общего случая нам нужно подсчитать, сколько раундов выиграл каждый игрок, и определить, кто имеет больше побед.

Ключевое наблюдение:
Поскольку $N$ всегда нечетное, не может быть ничьей. Следовательно, один игрок всегда будет иметь строго больше побед, чем другой.

Алгоритм:

1. Прочитать количество раундов $N$
2. Прочитать строку результатов раундов
3. Подсчитать количество символов A, чтобы получить $A_{\text{wins}}$
4. Подсчитать количество символов B, чтобы получить $B_{\text{wins}}$ (в качестве альтернативы, $B_{\text{wins}} = N - A_{\text{wins}}$)

Временная сложность: $O(N)$ — для подсчета символов в строке
Пространственная сложность: $O(N)$ — для хранения входной строки (или $O(1)$, если мы считаем во время чтения)

---