Problem F
Pizzastrengur

Image from wikipedia.com

Today is game day at Tommi’s pizzas so Georg and his friends are going to order some pizzas. The game starts with the employees at Tommi’s pizzas choosing a secret passcode, consisting only of the letters {“P”, “I”, “Z”, “A”}, and telling the customer the length of the passcode. If Georg and his friends manage to guess the passcode in at most $m$ attempts they get their pizza for free! Georg and his friends may pick words shorter than the passcode as guesses, in which case they will be told whether the guess is a prefix of the passcode. Can you help Georg and his friends in guessing the passcode, so they can get their pizza for free?

A word $A$ is a prefix of a word $B$ if $B$ starts with $A$. For example, “PIZ” is a prefix of “PIZZA”, but “‘ZZA” is not a prefix of “PIZZA”.

Interactivity

This is an interactive problem. Your solution will be tested against an interactive judge which reads the output of your solution and prints the input your solution recieves. This interaction follows certain rules:

The judge starts by printing an integer $n$ ($1 \leq n \leq 10^4$), the length of the passcode $S$ which only contains the letters {“P”, “I”, “Z”, “A”}.

Next your solution must output a guess string $P$ which must contain at least $1$ letter and at most $n$ letters. After this the judge will respond as such:

• If $P$ is not a prefix of $S$ the judge will print $0$.

• If $P$ is a prefix of $S$ the judge will print $1$.

• If $P$ is equal to the passcode the judge will print $2$ and your program should stop guessing.

Make sure to flush after each guess, for example using

• print(..., flush=True) in Python,

• cout << ... << endl; in C++,

• System.out.flush(); in Java.

The problem comes with a testing tool to help test your solution.

Scoring

5

ZAP

0

PIZ

1

PIZZA

2