Combo timer 1s memory 256MB

당신은 액션 비디오 게임을 하고 있다. 게임 컨트롤러는 4개의 버튼 A, B, X, Y를 가지고 있다. 게임에서 당신은 콤보 동작을 통해 동전을 얻을 수 있다. 당신은 버튼을 연속해서 눌러서 콤보 동작을 만들 수 있다.

이 게임에는 눌러야 할 버튼들의 비밀 순서가 있고, 비밀 순서를 4개 문자 A, B, X, Y로 이루어진 문자열 S로 설명할 수 있다. 당신은 문자열 S을 알지 못하지만 그것의 길이 N(1 ≤ N ≤ 2,000)은 알고 있다.

당신은 S의 첫 번째 문자가 S안에서 다시 나타나지 않는다는 것도 알고 있다. 예를 들어, S는"ABXYY" 또는 "XYYAA"일 수 있지만 "AAAAA" 또는 "BXYBX"가 될 수는 없다.

콤보 동작을 위해서는 4N개 이하의 버튼들을 누른다. p가 당신이 누르는 버튼들의 순서를 나타내는 문자열이라고 하자. 콤보 동작으로 얻는 동전의 수는 p의 부분문자열이 되는 S의 가장 긴 접두사의 길이로 계산된다. 문자열 t의 부분문자열은 t안의 연속된 문자들의 순서(길이가 0인 문자열 가능)이다. t의 접두사는 길이가 0인 문자열 이거나 t의 첫 번째 문자를 포함하는 t의 부분문자열이다.

​당신은 콤보 동작을 사용해서 비밀 문자열을 찾아야 한다.​​​

해야 할 일

당신은 아래 함수를 구현해야 한다.

string guess_sequence(int N)

• N : 문자열 S의 길이.

• 이 함수는 각 테스트 케이스 마다 정확히 한번 호출된다.

• 이 함수는 문자열 S를 반환해야 한다.

프로그램은 다음 함수를 호출할 수 있다.

int press(string p)

• p : 당신이 누르는 버튼들의 순서.

• p는 0이상 4N이하 길이의 문자열이여야 한다. p의 각 문자는 A, B, X, Y 중 하나여야 한다.

• 각 테스트 케이스에 대해 이 함수를 8,000번을 초과해서 호출할 수 없다.

• 이 함수는 p로 표현된 버튼들의 순서을 눌렸을 때 얻을 수 있는 동전의 수를 반환한다.​

예를 들어, S가 "ABXYY"이고 p가 "XXYYABYABXAY"이면, "ABX"가 p의 부분문자열이면서 S의 가장 긴 접두사이기 때문에 당신은 3개의 동전을 얻는다.