QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[-2]

# 6180. 滚动雪人游戏问题

Statistics

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

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

输入格式

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

输出格式

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

样例数据

样例输入

5
ABCCC
3
ABC

样例输出

C
N

子任务

测试数据中 20% 的数据满足 n1000

测试数据中 100% 的数据满足 n10000


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