Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A New Tough Game

Limits: 1s, 512 MB · Interactive

We are introducing a new game in Toph. And, by participating in IUT ICT Fest 2019, you have become one of the luckiest persons to try this awesome game for the first time 😃.

We use strings a lot while chatting or doing almost everything else on the internet. So, you will have to guess a string in this game!

You will get an integer N. This is the length of the string S that I have picked. Now, it is hard to guess a N length string, right? There are 26N such strings if we limit ourselves to the 26 letters from the lowercase English alphabet. So, I will let you query some information for N+1 times. If you can determine the string within this limit, I will declare you as the winner and thus get an “Accepted” response from Toph. Otherwise, you will lose and thus get a “Wrong Answer”. Now, the queries from your end must follow the following format:

? X

Then you will get a response which is the output of the following function:

int F(string X) {
    int response = 0;
    for(int i=0; i<N; i++) {
        response = response + abs(S[i] - X[i]);
    }
    return response;
}

You can have at most N+2 interactions with the system. After at most N+1 queries, you must give the final prediction in the format:

! X

After that your interactions will end and the system will compare your predicted string X with my string S. If these two strings match, you win.

Input

Input begins with an integer N (1 ≤ N ≤ 1000). Then, you can make at most N+1 queries. For each of the queries, you will receive an integer response as described earlier.

Output

You can make two types of interactions for this problem:

  1. ? X: Here, X is a string of length N. You can have at most N+1 queries of this type. For each of these queries, you will receive an integer as described earlier.

  2. ! X: You can have only one interaction of this type and this interaction will terminate the execution. We call this your code’s output string. Now, if X is same as S, then you will get “Accepted” as the verdict. Otherwise, you will receive “Wrong Answer” as the verdict.

Also, keep in mind any other output from your program will end up getting “Wrong Answer” as verdict.

Let’s imagine the string is “asd”. Here is what a possible interaction would look like:

> 3
< ? abc
> 18
< ? bre
> 3
< ? aqd
> 2
.
.
.
< ! asd
Author
Discussion
Submit

Login to submit

Editorial

Login to unlock editorial