Codeforces Beta Round 60 |
---|
Закончено |
Как известно, в Хогвартсе четыре факультета: Гриффиндор, Пуффендуй, Когтевран и Слизерин (Gryffindor, Hufflepuff, Ravenclaw, Slytherin). Распределение первокурсников по факультетам происходит с помощью Распределяющей Шляпы. Ученики вызываются по очереди, в алфавитном порядке, каждый из них должен надеть на голову Шляпу и, после некоторых размышлений, Шляпа торжественно объявляет название факультета, на который следует поступить этому ученику.
Считается, что при этом Шляпа исходит из личных качеств ученика: храбрых и благородных она отправляет в Гриффиндор, умных и сметливых — в Когтевран, упорных и честных — в Пуффендуй, а хитрых и изворотливых — в Слизерин. Однако очень обеспокоенная предстоящим распределением первокурсница Гермиона Грейнджер изучила всю литературу, касающуюся Распределяющей Шляпы, и пришла к выводу, что дело обстоит гораздо проще. В случае если родственники первокурсника уже учились в Хогвартсе, то Шляпа определяет ученика на тот же факультет, где учились его родственники. В спорных ситуациях, когда родственники учились на разных факультетах или когда они все были маглами, как у Гермионы, Шляпа определяет ученика на факультет, на который в данный момент отправлено меньше всего первокурсников. Если таких факультетов несколько, то выбор предоставляется самому ученику. Тогда ученик может выбрать любой из факультетов, на которых пока отправлено наименьшее количество первокурсников.
Гермиона уже опросила всех предшествующих ей по списку учеников об их родственниках. Теперь она и ее новые друзья Гарри Поттер и Рон Уизли хотят узнать, на какой факультет Шляпа определит Гермиону.
В первой строке задано целое число n (1 ≤ n ≤ 10000) — количество учеников, идущих в списке раньше Гермионы. Следующая строка содержит n символов. Если все родственники ученика учились на одном и том же факультете, то i-й символ в строке совпадает с первой буквой названия этого факультета. Иначе i-й символ равен «?».
Выведите все возможные факультеты, на которые может быть отправлена Гермиона. Названия факультетов следует выводить в алфавитном порядке, по одному в строке.
11
G????SS???H
Gryffindor
Ravenclaw
2
H?
Gryffindor
Ravenclaw
Slytherin
Рассмотрим второй пример. Раньше Гермионы только два ученика. Первый ученик отправляется на Пуффендуй (Hufflepuff). Второму ученику предоставляется выбор между факультетами, на которые было отправлено наименьшее количество учеников, т.е. Гриффиндором, Когтевраном и Слизерином. Если он выберет Гриффиндор, то Гермионе придется выбирать между Когтевраном и Слизерином, если Когтевран — между Гриффиндором и Слизерином, если Слизерин — между Гриффиндором и Когтевраном. В итоге возможно такое стечение обстоятельств (зависящее от выбора второго ученика и самой Гермионы), что Гермиона окажется 1) на Гриффиндоре, 2) на Когтеврание, 3) на Слизерине. Отметим, что несмотря на то, что ни в одном случае Гермионе не будет предоставлен выбор между всеми тремя вариантами, они все возможны и их все нужно выводить в ответ. На Пуффендуй в данном примере Гермиона не попадет ни при каких обстоятельствах.
Название |
---|