CSES - Aalto Competitive Programming 2024 - wk2 - Wed - LibBot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

In the brand new Hypercube Library there are n buildings, each with n floors, each with n aisles. Along each aisle there are n bookshelves and each of them contains n books. All books are kept nicely in alphabetical order. The first book is in building 1, floor 1, aisle 1, shelf 1, and position 1. The next one in alphabetical order is in building 1, floor 1, aisle 1, shelf 1, position 2, and so on. You can use coordinates like 1.1.1.1.1, 1.1.1.1.2, etc., all the way up to n.n.n.n.n to refer to the books.

Now your task is to program the library maintenance robots that can be used to check the availability of any book. When the system starts, it will let you know the current value of n, with a message like "SIZE n". Then the system will give you a request for a book, of the form "COUNT title", where "title" is the name of the book, a string of characters a-z. You will eventually need to give an answer like "GOT c", where c is the number of books with this exact title in the library. Here c might be 0, or 1, or something much larger; it might even happen that the whole library is filled with copies of the same book.

Now to figure out the answer, you will need to get some assistance from the robots. So you can post requests like "FETCH a.b.c.d.e", and the friendly robots will go and scan what is the title of the book in location a.b.c.d.e; the system will then answer with e.g. "FOUND title", where "title" is the title of the book in this location.

So your interaction might go e.g. like this, with > denoting input that you got, and < denoting the messages your program wrote.

> SIZE 10
> COUNT abc
< FETCH 1.2.3.4.5
> FOUND abb
< FETCH 1.2.3.4.6
> FOUND abc
< FETCH 1.2.3.5.6
> FOUND abc
< FETCH 1.2.3.5.7
> FOUND abd
< GOT 11

Here you figured out that 1.2.3.4.6 is the first location with the book titled "abc" and 1.2.3.5.6 is the final location with the book titled "abc", so there are in total 11 such books in the library. This specific interaction of course required plenty of luck.

Please note that this is an interactive task, and appropriate care is needed. After each line you print, please remember to add a line feed and flush the output.

Limits

1 \leq n \leq 10
You can make at most 40 FETCH requests in total.