또 비밀번호를 잊어버렸습니다! 저는 컴퓨터 앞에 앉아 틀린 비밀번호를 계속 입력하고 있습니다. 기억나는 것이라고는 비밀번호가 영어 소문자로만 이루어져 있다는 것뿐입니다. 다행히도 로그인 시스템은 단순히 "잘못된 비밀번호"라고만 응답하지 않습니다. 시스템은 제 입력의 접두사 중 비밀번호의 (반드시 연속할 필요는 없는) 부분 수열로 나타나는 가장 긴 접두사의 길이도 알려줍니다. 엄밀하게 말하면, 비밀번호 $P = p_1 p_2 \dots p_N$과 입력 $Q = q_1 q_2 \dots q_N$에 대해 로그인 시스템의 응답은 모든 $1 \le i \le L$에 대해 $q_i = p_{k_i}$를 만족하는 인덱스 $1 \le k_1 < k_2 < \dots < k_L \le N$이 존재하는 가장 큰 $L$입니다. 또한 시스템은 비밀번호의 길이 $N$과, 비밀번호가 알파벳의 처음 $S$개의 문자만 사용함을 뜻하는 $S$도 알려줍니다. 예를 들어, $S = 4$는 비밀번호가 $\text{a}$, $\text{b}$, $\text{c}$, $\text{d}$만 포함함(단, 모두 포함할 필요는 없음)을 의미합니다.
제 비밀번호를 복구할 수 있도록 도와주세요!
구현 세부사항
이 문제는 인터랙티브 문제입니다. 다음 함수를 구현해야 합니다.
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- 인자: 위에서 설명한 $N$과 $S$.
- 반환값: 올바른 비밀번호.
프로그램은 다음 함수를 호출할 수 있습니다.
C: int query(char* str);
C++: int query(string str);
- 인자: 알파벳의 처음 $S$개의 문자 중에서 고른 $1$개 이상 $N$개 이하의 문자로 이루어진 문자열.
- 반환값: $0$ 이상
str의 길이 이하인 정수로, 질의에 대한 로그인 시스템의 응답을 나타냅니다. - 컴파일 에러를 피하기 위해, 이 함수를 호출하기 전에 전역 범위의 아무 곳에서나 위의 텍스트를 정확히 그대로 사용하여 함수를 선언해야 합니다.
- 각 테스트 케이스마다 이 함수를 최대 $50\,000$번 호출할 수 있습니다.
프로그램에서 추가 함수를 정의해도 됩니다.
샘플 그레이더
로컬에서 코드를 테스트할 수 있도록 샘플 grader.{c,cpp}가 제공됩니다. 샘플 그레이더는 password.in 파일에서 다음 형식으로 입력을 읽습니다.
- $1$번째 줄: $N$ $S$
- $2$번째 줄: 비밀번호
그레이더를 여러분의 풀이와 함께 컴파일한 뒤, 생성된 실행 파일을 실행하여 주어진 입력에 대해 추측 전략을 테스트할 수 있습니다.
서브태스크
테스트 케이스는 그룹 단위로 채점될 수 있습니다. 서브태스크는 순서대로 다음과 같습니다.
| 서브태스크 | 배점 비율 | 입력 제한 |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; 비밀번호의 모든 문자가 서로 다름 |
| 2 | 20% | $2 \le N \le 100$ 및 $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ 및 $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
예제
비밀번호를 $\text{aab}$라고 합시다. 그레이더는 guess(3, 2)를 호출합니다. 호출 기록은 다음과 같을 수 있습니다.
| 호출 | 반환값 |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
이 시점에서 guess(3, 2)는 "aab"를 반환해야 합니다.