루미 알고리즘

#1604플래티넘Crack the Password

PO 2025 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Disaster! The programming olympiad final has started, but you've forgotten the login to your computer. Luckily, you're not a sheep following the flock. You refuse to use Windows and instead use Progolymp-OS. If you forget your password in this operating system, you receive clues when you make a guess. More specifically, assume that the password is P, and you guess G. The system will respond with

LCS(G,P)

where LCS(G,P) is the length of the longest common subsequence of G and P. The longest common subsequence of two strings G and P is defined as follows: let's denote all subsequences of a string S by the set of all strings that can be obtained by removing zero or more letters from S while maintaining the relative order of the remaining letters. LCS(G,P) is the length of the longest string that appears in both the subsequences of G and P.

For example: if P=“abc”, its subsequences are {“”, “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}. If G=“ac”, its subsequences are {“”, “a”, “c”, “ac”}. The longest common subsequence is “ac”, and thus LCS(G,P)=2.

A few more examples: the longest common subsequence of “aggtab” and “gxtxayb” is “gtab”. Therefore, LCS(“aggtab”, “gxtxayb”) = 4. Two more examples are LCS(“abc”, “cba”) = 1 and LCS(“po”, “trakigt”) = 0.

You can now make up to 10,000 guesses before the system locks up. Each guess consists of giving your computer G, and it responds with LCS(G,P). Additionally, you want to use as few guesses as possible so you can get back into the competition as soon as possible.

Interaction

Your program should first read two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 26), the number of letters in the password and how many unique letters it can contain. More specifically, the password P consists of exactly N letters chosen from the first K lowercase letters of the alphabet.

To make a guess, you should print a line in the format ? G. G must satisfy 1 ≤ |G| ≤ N and only contain letters from the first K lowercase letters of the alphabet. The program will then read an integer, LCS(G,P).

When making your final guess, print a line with the character !, followed by a string of length N, your guess of the password. After this, your program should terminate and no more output should be written. This final guess does not count toward the limit of 10,000 guesses.

It is guaranteed that the string P in each test case is determined in advance and does not change adaptively in response to your measurements. There are no guarantees on P such as it being a real word or anything like that, as it is a strong password.

Make sure to flush the output after every print statement, otherwise you may get a Time Limit Exceeded verdict. In C++, this can be done for example with cout << flush; or fflush(stdout);, in Python this is done automatically when you use input(), but otherwise you need to use sys.stdout.flush(), and in Java with System.out.flush();.

Scoring

Your solution will be tested on a number of test case groups. If you fail to find the password in any test case, you will receive zero points for the group it belongs to. Otherwise, let g be the largest number of guesses you used to find the passwords in a certain test case group. If the group is worth P points, you will get

⌊P · min(1, 666/g) ⌋

points for that group. You will receive 100 points for the entire problem if you never use more than 666 guesses for a test case.

The table below shows the value of 666/g rounded down for different numbers of guesses.

666/gg
1666
0.9740
0.8832
0.7951
0.61110
0.51332
0.41665
0.32220
0.23330
0.16660

The test case groups are as follows:

GroupPointsConstraints
115N = 50, K = 2
215N = 30, K = 3
370N = 100, K ≤ 26

Explanation of Sample 1

The secret password is bbacba. Note that the interaction does not show a reasonable strategy, but only demonstrates the format.

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.