QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 512 MB 満点: 100 難易度: [表示] インタラクティブ

#194. 비밀번호

統計

또 비밀번호를 잊어버렸습니다! 저는 컴퓨터 앞에 앉아 틀린 비밀번호를 계속 입력하고 있습니다. 기억나는 것이라고는 비밀번호가 영어 소문자로만 이루어져 있다는 것뿐입니다. 다행히도 로그인 시스템은 단순히 "잘못된 비밀번호"라고만 응답하지 않습니다. 시스템은 제 입력의 접두사 중 비밀번호의 (반드시 연속할 필요는 없는) 부분 수열로 나타나는 가장 긴 접두사의 길이도 알려줍니다. 엄밀하게 말하면, 비밀번호 $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"를 반환해야 합니다.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.