QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 6180. 滚动雪人游戏问题

统计

在滚动雪人游戏中,已经堆好了 $n$ 个不同类型的雪人。这些雪人共有 $A$, $B$, $C$ 三种不同的类型。滚动雪人游戏的规则是,在当前的雪人队列中,任意选择 $2$ 个不同类型的雪人,将他们合并改造成与合并前的 $2$ 种类型不同类型的一个新的雪人。例如,选择了 $2$ 个不同类型的雪人,它们的类型分别为 $A$ 和 $B$,则合并改造后的新的雪人的类型为 $C$。选择类型分别为 $A$ 和 $C$,则合并改造后的类型为 $B$;选择类型分别为 $B$ 和 $C$,则合并改造后的类型为 $A$。当雪人队列中只剩下同一种类型的雪人时,游戏结束。小明和小雪希望用最少的合并次数完成滚动雪人游戏。

滚动雪人游戏问题:对于给定的雪人队列,计算出用最少的合并次数完成滚动雪人游戏后,留在在雪人队列中的雪人类型。

输入格式

每个测试项有多组测试数据。每组测试数据的第一行有一个正整数 $n$,第二行是一个由大写英文字母 A, B, C 组成的,长度为 $n$ 的字符串,表示初始雪人队列。

输出格式

对每组测试数据,依次输出对于给定的初始雪人队列,用最少的合并次数完成滚动雪人游戏后,留在在雪人队列中的雪人类型 A, BC。如果不能确定最终的雪人类型,则输出大写英文字母 N

样例数据

样例输入

5
ABCCC
3
ABC

样例输出

C
N

子任务

测试数据中 $20\%$ 的数据满足 $n \leq 1\,000$。

测试数据中 $100\%$ 的数据满足 $n \leq 10\,000$。


  1. 赛时并未提供数据组数,“请选手自行评估”。