Prisoner Challenge

문제

In a prison, there are $500500$ prisoners. One day, the warden offers them a chance to free themselves. He places two bags with money, bag A and bag B, in a room. Each bag contains between $11$ and $NN$ coins, inclusive. The number of coins in bag A is different from the number of coins in bag B. The warden presents the prisoners with a challenge. The goal of the prisoners is to identify the bag with fewer coins.

The room, in addition to the money bags, also contains a whiteboard. A single number must be written on the whiteboard at any time. Initially, the number on the whiteboard is $00$.

Then, the warden asks the prisoners to enter the room, one by one. The prisoner who enters the room does not know which or how many other prisoners have entered the room before them. Every time a prisoner enters the room, they read the number currently written on the whiteboard. After reading the number, they must choose either bag A or bag B. The prisoner then inspects the chosen bag, thus getting to know the number of coins inside it. Then, the prisoner must perform either of the following two actions:

• Overwrite the number on the whiteboard with a non-negative integer and leave the room. Note that they can either change or keep the current number. The challenge continues after that (unless all $500500$ prisoners have already entered the room).
• Identify one bag as the one that has fewer coins. This immediately ends the challenge.

The warden will not ask a prisoner who has left the room to enter the room again.

The prisoners win the challenge if one of them correctly identifies the bag with fewer coins. They lose if any of them identifies the bag incorrectly, or all $500500$ of them have entered the room and not attempted to identify the bag with fewer coins.

Before the challenge starts, the prisoners gather in the prison hall and decide on a common strategy for the challenge in three steps.

• They pick a non-negative integer $xx$, which is the largest number they may ever want to write on the whiteboard.
• They decide, for any number $ii$ written on the whiteboard ($0\le i\le x0\; \backslash le\; i\; \backslash le\; x$), which bag should be inspected by a prisoner who reads number $ii$ from the whiteboard upon entering the room.
• They decide what action a prisoner in the room should perform after getting to know the number of coins in the chosen bag. Specifically, for any number $ii$ written on the whiteboard ($0\le i\le x0\; \backslash le\; i\; \backslash le\; x$) and any number of coins $jj$ seen in the inspected bag ($1\le j\le N1\; \backslash le\; j\; \backslash le\; N$), they either decide
  • what number between $00$ and $xx$ (inclusive) should be written on the whiteboard, or
  • which bag should be identified as the one with fewer coins.

Upon winning the challenge, the warden will release the prisoners after serving $xx$ more days.

Your task is to devise a strategy for the prisoners that would ensure they win the challenge (regardless of the number of coins in bag A and bag B). The score of your solution depends on the value of $xx$ (see Subtasks section for details).