시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB63201932.203%

문제

I forgot my password again! I am sitting at my computer punching in wrong passwords. All I remember is that my password contains only lowercase letters. Luckily, the login system responds with more than just "wrong password". It also tells me the length of the longest prefix of my input that occurs as a (not necessarily contiguous) subsequence in the password. Formally, for a password P=p1 p2 … pN and input Q=q1 q2 …qN, the login system’s answer is the largest L for which there exist indices 1≤ k1 < k2 < … < kL ≤ N such that qi = pki for all 1 ≤ i ≤ L. The system also tells me N, the length of my password, and S, meaning my password only uses the first S letters of the alphabet. For example, S = 4 means my password only contains a, b, c and d (but not necessarily all of them).

Please help me recover my password!

구현

This problem is interactive. You should implement the function

string guess(int n, int s);
  • Arguments: N and S as described above.
  • Return value: the correct password.

Your program may call the function

int query(string str);
  • Argument: a string of 1 to N letters from among the first S letters of the alphabet.
  • Return value: an integer between 0 and the length of str, representing the login system’s answer to your query.
  • To avoid compiler errors, you should declare this function using the exact text above, anywhere in the global scope before calling it.
  • You may call this function at most 50,000 times for each test case.

Your program may define additional functions.

샘플 그레이더

A sample grader.cpp is provided for you to test your code locally. The sample grader reads the input from the file password.in in the format:

  • line 1: N S
  • line 2: password

You can compile the grader together with your solution. Then you can run the resulting binary to test your guessing strategy against the given input.

서브태스크

번호배점제한
110

N ≤ S ≤ 26; all the letters in the password are distinct

220

2 ≤ N ≤ 100 and 2 ≤ S ≤ 4

320

2 ≤ N ≤ 2,000 and 2 ≤ S ≤ 20

430

2 ≤ N ≤ 3,500

520

2 ≤ N ≤ 5,000

예제

Let the password be aab. The grader calls guess(3, 2). The call log may be

Call Return value
guess("ab") 2
guess("abb") 2
guess("bab") 1
guess("aab") 3

At this point, guess(3, 2) should return "aab".

제출할 수 있는 언어

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

채점 및 기타 정보

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