← 返回题目列表

Codeforces · 65/D

D. 哈利·波特与分院帽

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

如您所知,霍格沃茨有四个学院:格兰芬多、赫奇帕奇、拉文克劳和斯莱特林。将一年级新生分入各个学院是由分院帽完成的。学生们按照字母顺序一一被叫到,每人头上戴一顶帽子,经过深思熟虑,帽子上庄严地宣布了该学生应该进入的房子的名字。

帽子被认为是根据学生的个人品质来考虑的:它将勇敢和高贵的学生送到格兰芬多,将聪明和精明的学生送到拉文克劳,将执着和诚实的学生送到赫奇帕奇,将聪明狡猾的学生送到斯莱特林。然而,一年级学生赫敏·格兰杰对即将到来的排序非常担心。她研究了有关分院帽的所有文献,并得出结论:它比这简单得多。如果学生的亲戚已经在霍格沃茨学习,帽子会将学生带到他的家人曾经学习过的同一所房子。在有争议的情况下,当亲戚在不同的学院学习或者当他们都是像赫敏的父母一样的麻瓜时,帽子会将学生分类到当时被送到的一年级学生数量最少的学院。如果有多个这样的房子,则由学生自己选择。然后,学生可以选择迄今为止被送入的一年级学生数量最少的任何一个学院。

赫敏已经向名单上排在她之前的学生询问了他们的亲戚。现在她和她的新朋友哈利·波特和罗恩·韦斯莱想知道帽子会把赫敏安置在哪个房子里。

输入

第一个输入行包含一个整数 n (1 ≤ n ≤ 10000)。这是列表中赫敏之前的学生人数。下一行包含 n 个符号。如果一个学生的所有亲戚都曾经在同一所房子里学习,那么字符串中的第 i 个字符与该房子名称的第一个字母一致。否则,第 i 个符号等于“?”。

输出

打印赫敏可以被送到的所有可能的房屋。房屋名称应按字母顺序打印,每行一个。

示例

输入 #1

11
G????SS???H

输出 #1

Gryffindor
Ravenclaw

输入 #2

2
H?

输出 #2

Gryffindor
Ravenclaw
Slytherin

注意

考虑第二个例子。赫敏之前只有两个学生。第一个学生被送到赫奇帕奇。第二个弟子可以在派出学生人数最少的学院(即格兰芬多、斯莱特林和拉文克劳)之间进行选择。如果他选择格兰芬多,赫敏将被迫在拉文克劳和斯莱特林之间做出选择,如果他选择拉文克劳,赫敏将在格兰芬多和斯莱特林之间做出选择,如果他选择斯莱特林,赫敏将在格兰芬多和拉文克劳之间做出选择。最终,有可能出现以下情况(取决于第二个学生和赫敏的选择)。赫敏最终会 1) 格兰芬多,2) 拉文克劳,3) 斯莱特林。请注意,尽管在这两种情况下赫敏都不会在所有三个选项之间进行选择,但它们都是可能的,并且都应该打印在答案中。在任何情况下,赫敏都不会进入赫奇帕奇。