시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 281 | 109 | 106 | 40.927% |
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.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
.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
".
A
, B
, X
, or Y
.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 press
.
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 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.Olympiad > International Olympiad in Informatics > IOI 2018 > Day 1 1번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)