문제
당신은 액션 비디오 게임을 하고 있다.
게임 컨트롤러는 4개의 버튼 A, B, X, Y를 가지고 있다.
게임에서 당신은 콤보 동작을 통해 동전을 얻을 수 있다.
당신은 버튼을 연속해서 눌러서 콤보 동작을 만들 수 있다.
이 게임에는 4개 문자 A,B,X,Y로 이루어진 문자열 S로 나타내는 버튼들의 비밀 순서가 있다.
당신은 문자열 S을 알지 못하지만 그것의 길이 N(1 <= N <= 2000)은 알고 있다.
당신은 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 중 하나여야 한다.
- 각 테스트 케이스에 대해 이 함수를 8000번을 초과해서 호출할 수 없다.
- 이 함수는 p로 표현된 버튼들의 순서을 눌렸을 때 얻을 수 있는 동전의 수를 반환한다.
예를 들어, S가 "ABXYY"이고 p가 "XXYYABYABXAY"이면, "ABX"가 p의 부분문자열이면서 S의 가장 긴 접두사이기 때문에 당신은 3개의 동전을 얻는다.
press 함수를 N+2회 이하로 사용하여 S를 찾는다면 정답을 받는다.
이외의 경우, 0점을 받는다.
힌트
출처
IOI 2018 day1 1