from itertools import count, pairwise, product from random import choices, randint from string import ascii_lowercase import sys def printe(*args, end="\n", **kwargs): print(*args, end=end, file=sys.stderr, **kwargs) class Judge: def __init__( self, N: int = -1, is_submit: bool = True, ans: str = "", ) -> None: assert N != -1 or (not is_submit) self.__is_submit = is_submit if is_submit or ans: self.__ans = ans self.N = N else: if N == -1: N = randint(1, 100) self.__ans = "".join(choices(ascii_lowercase, k=N)) # printe(f"{N=}", flush=True) # printe(f"{self.__ans}", flush=True) self.N = len(self.__ans) def question(self, password: str) -> int: print("?", password, flush=True) if self.__is_submit: return int(input()) else: ctr = sum(p == a for p, a in zip(password, self.__ans)) return ctr def answer(self, password: str): print("!", password, flush=True) if self.__is_submit: return # if self.__ans == password: # printe("Correct", flush=True) # else: # printe("Incorrect", flush=True) class Controler: def __init__(self, judge: Judge, max_n: int) -> None: self.__judge = judge self.__max_n = max_n self.__ctr = 0 self.__is_answered = False self.__question_cache: dict[str, int] = {} def question(self, password: str | list[str]) -> tuple[bool, int]: _password = "" if isinstance(password, list): _password = "".join(password) else: _password = password if _password in self.__question_cache: return True, self.__question_cache[_password] if self.__is_answered: return False, -1 if self.__ctr >= self.__max_n: self.answer(_password) return False, -1 res = self.__judge.question(_password) self.__question_cache[_password] = res self.__ctr += 1 if res == self.__judge.N: self.answer(_password) return False, -1 return True, res def answer(self, password: str | list[str]): if self.__is_answered: return if isinstance(password, list): self.__judge.answer("".join(password)) else: self.__judge.answer(password) self.__is_answered = True search_letters = "abcdefghijklmnopqrstuvwxy" def main(): N = int(input()) # judge = Judge(N, False, "z" * N) judge = Judge(N) password_cand = ["a"] * N controler = Controler(judge, 2500) cur_digit = 0 while True: if cur_digit >= N: break is_valid, prev_correct_n = controler.question(password_cand) printe(is_valid, prev_correct_n) if not is_valid: return is_found = False for l1, l2 in pairwise(search_letters): assert password_cand[cur_digit] == l1 password_cand[cur_digit] = l2 is_valid, next_correct_n = controler.question(password_cand) if prev_correct_n > next_correct_n: password_cand[cur_digit] = l1 is_found = True break if prev_correct_n < next_correct_n: is_found = True break if not is_found: password_cand[cur_digit] = "z" cur_digit += 1 controler.answer(password_cand) if __name__ == "__main__": main()