\(2^K\) 명의 선수가 \(1\)번부터 \(2^K\)번까지 한 줄로 서서 단판 토너먼트를 벌인다. 각 선수는 처음부터 끝까지 같은 손만 낸다. 손은 바위(R), 가위(S), 보(P) 중 하나이다.

토너먼트는 다음과 같이 진행된다. 매 라운드마다 살아남은 선수들을 줄 선 순서대로 두 명씩 묶어( \(1\)번째와 \(2\)번째, \(3\)번째와 \(4\)번째, \(\dots\) ) 경기를 치르고, 각 경기의 승자만 다음 라운드로 올라간다. 이때 진출한 선수들의 상대적인 순서는 그대로 유지된다. 한 명만 남을 때까지 라운드를 반복하며, 마지막에 남은 선수가 우승자이다.

한 경기의 승패는 가위바위보의 일반적인 규칙으로 정해진다. 즉, 바위는 가위를, 가위는 보를, 보는 바위를 이긴다. 두 선수가 같은 손을 내서 비기는 경우에는 번호가 더 작은(줄에서 앞에 선) 선수가 진출한다.

선수들이 내는 손이 주어질 때, 우승자의 원래 번호를 구하라.

\(0 \le K \le 20\)

둘째 줄 문자열의 길이는 정확히 \(2^K\) 이며, 각 문자는 R, S, P 중 하나이다.

첫째 줄에 정수 \(K\) (\(0 \le K \le 20\)) 가 주어진다.

둘째 줄에 길이 \(2^K\) 인 문자열이 주어지며, \(i\)번째 문자는 \(i\)번 선수가 내는 손을 나타낸다. 문자는 R(바위), S(가위), P(보) 중 하나이다.

우승자의 원래 번호(1-based)를 한 줄에 출력한다.

riseoj 작성

출처 Original