← 返回题目列表

Codeforces · 31/E

E. 电视游戏

中文机器翻译题面 查看原题

BerTV 上有一款新的电视游戏。在这个游戏中,两个玩家得到一个由 2n 位数字组成的数字 A。在每个回合之前,玩家决定谁将采取下一步行动。每个玩家应该精确地进行 n 步。轮到第 i 个玩家时,取出 A 最左边的数字并将其附加到他或她的数字 Si 上。之后,最左边的数字将从 A 中删除。最初,两个玩家(S1 和 S2)的号码都是“空”。数字 A、S1、S2 中允许有前导零。游戏结束时,第一个玩家获得 S1 美元,第二个玩家获得 S2 美元。

有一天,荷马和玛吉来玩游戏。他们事先设法知道了数字A。他们想要找到这样的移动顺序,使得他们两人都恰好进行了 n 步,并且最大化了他们的总奖金。帮助他们。

输入

第一行包含整数 n (1 ≤ n ≤ 18)。第二行包含恰好由 2n 位数字组成的整数 A。该数字可以有前导零。

输出

输出 2n 个字符“H”和“M”的行——Homer 和 Marge 的移动序列,这给了他们最大可能的总奖金。每个玩家必须精确地进行 n 步。如果有多个解,输出任意一个。

示例

输入 #1

2
1234

输出 #1

HHMM

输入 #2

2
9911

输出 #2

HMHM