In an attempt to “liberate” their fellow birds, a group of highly intelligent hens are attempting to compromise the zoo’s security system. To get access to the zoo’s mainframe, the hens first need to guess the administrative password. The hens know that the password is a string built from up to 62 possible characters: a, b, c, ..., z, A, B, C, ..., Z, 0, 1, ... 9. They also know that no character appears more than once in the password, which means that it has a maximum length of 62 (and a minimum length of 1). The password is case-sensitive.
We define a guess be close if and only if the real password can be obtained by inserting additional characters among the letters and numbers of the original guess. In other words, a guess is close if it is a (not necessarily contiguous) subsequence of the password. Every time the hens guess a password, the zoo’s security system will do one of three things:
- If the guess is exactly equal to the password, it will print ‘C’ and grant the hens access to the mainframe.
- If the guess close but not exactly equal to the password, it will print ‘Y’.
- If the guess is neither close nor exactly equal to the password, it will print ‘N’.
The mainframe permits at most 750 guesses before it locks further attempts and alerts the zoo officials of suspicious activity. The hens have hired you to guess the password before you use all of your allotted attempts.
There will be no initial input. Every time your program makes a guess, the grader will output ‘C’, ‘Y’, or ‘N’, which your program can then read via the usual input channel. The grader will only respond to the first 750 guesses. Make sure that you end each guess with a new line.
This question was adapted from the 2020 mBIT Computing Olympiad.
Test Program made by me in Python 3 (works):
from functools import cmp_to_key
def ask(s):
print(s)
c = input()
if c == 'C':
exit()
return c == 'Y'
def cmp(a, b):
return -1 if ask(a + b) else 1
ret = []
for i in range(48, 58):
if ask(chr(i)):
ret.append(chr(i))
for i in range(65, 91):
if ask(chr(i)):
ret.append(chr(i))
for i in range(97, 123):
if ask(chr(i)):
ret.append(chr(i))
ret = "".join(sorted(ret, key=cmp_to_key(cmp)))
print(ret)
I think it can be condensed even further, but that sample is just to show what the program is trying to ask. I do not own this question and all rights are to 2020 mBIT. The rules are simple. Do not just print answers and shortest one wins in any language.