시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 50 23 22 47.826%

문제

You are playing an action video game. The game controller has buttons, A, B, X, and Y. In this game, you can get coins with combo moves. You can make a combo move by pressing buttons in sequence.

This game has a secret sequence of buttons, which can be represented as a string S of those characters. You don't know the string S, but you know its length N.

You also know that the first character of S never reappears in it. For example, S can be "ABXYY" or "XYYAA", but cannot be "AAAAA" or "BXYBX".

You can press a sequence of up to 4N buttons for a combo move. Let p be the string which represents the sequence of the buttons you pressed. The number of coins you get for this move is calculated as the length of the longest prefix of S which is also a substring of p. A substring of a string t is a contiguous (possibly empty) sequence of characters within t. A prefix of t is a substring of that is empty or contains the first character of t.

For example, if S is "ABXYY" and p is "XXYYABYABXAY", you will get 3 coins because "ABX" is the longest prefix of S that is also a substring of p.

Your task is to determine the secret string S using few combo moves.

구현

You should implement the following function:

string guess_sequence(int N)
• N: the length of string S.
• This function is called exactly once for each test case.
• This function should return the string S.

Your program can call the following function:

int press(string p)
• p: a sequence of buttons you press.
• p must be a string of length between 0 and 4N, inclusive. Each character of p must be A, B, X, or Y.
• You cannot call this function more than 8,000 times for each test case.
• This function returns the number of coins you get when you press the sequence of buttons represented by p.

예시

Let S be "ABXYY". The grader calls guess_sequence(5). An example of communication is shown below.

Call Return
press("XXYYABYABXAY") 3
press("ABXYY") 5
press("ABXYYABXYY") 5
press("") 0
press("X") 0
press("BXYY") 0
press("YYXBA") 1
press("AY") 1

For the first call to press, "ABX" appears in "XXYYABYABXAY" as a substring but "ABXY" does not, so 3 is returned.

For the third call to press, "ABXYY" itself appears in "ABXYYABXYY" as a substring, so 5 is returned.

For the sixth call to press, no prefix of "ABXYY" but the empty string appears in "BXYY" as a substring, so 0 is returned.

Finally, guess_sequence(5) should return "ABXYY".

제한

• 1 ≤ N ≤ 2 000
• Each character of the string S is A, B, X, or Y.
• The first character of S never reappears in S.

N = 3

서브태스크 2 (95점)

No additional constraints. For this subtask, your score for each test case is calculated as follows. Let be the number of calls to press.

• if qN + 2, your score is 95.
• if N + 2 < qN + 10, your score is 95 - 3(q - N - 2).
• if N + 10 < q ≤ 2N + 1, your score is 25.
• if max{N + 10, 2N + 1} < q ≤ 4N, your score is 5.
• Otherwise, your score is 0.

노트

Note that your score for each subtask is the minimum of the scores for the test cases in the subtask.

샘플 그레이더

• line 1: S

If your program is judged as Accepted, the sample grader prints Accepted: q with q being the number of calls to the function press.

If your program is judged as Wrong Answer, it prints Wrong Answer: MSG. The meaning of MSG is as follows:

• invalid press: A value of p given to press is invalid. Namely, the length of p is not between 0 and 4N, inclusive, or some character of p is not A, B, X, or Y.
• too many moves: The function press is called more than 8,000 times.
• wrong guess: The return value of guess_sequence is not S.

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

• 예제는 채점하지 않는다.