24438번 - Password 서브태스크다국어언어 제한함수 구현

문제

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=p₁ p₂ … p_N and input Q=q₁ q₂ …q_N, the login system’s answer is the largest L for which there exist indices 1≤ k₁ < k₂ < … < k_L ≤ N such that q_i = p_ki 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.

입력

출력

제한

서브태스크

힌트

예제

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

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