|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||69||32||31||47.692%|
You are playing an action video game. The game controller has buttons,
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 "
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.
Your program can call the following function:
int press(string p)
p: a sequence of buttons you press.
pmust be a string of length between 0 and 4N, inclusive. Each character of
Let S be "
ABXYY". The grader calls
guess_sequence(5). An example of communication is shown below.
For the first call to
ABX" appears in "
XXYYABYABXAY" as a substring but "
ABXY" does not, so 3 is returned.
For the third call to
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.
guess_sequence(5) should return "
N = 3
No additional constraints. For this subtask, your score for each test case is calculated as follows. Let be the number of calls to
Note that your score for each subtask is the minimum of the scores for the test cases in the subtask.
The sample grader reads the input in the following format:
If your program is judged as Accepted, the sample grader prints
Accepted: q with
q being the number of calls to the function
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
pis not between 0 and 4N, inclusive, or some character of
too many moves: The function press is called more than 8,000 times.
wrong guess: The return value of
guess_sequenceis not S.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)