Prisoners' Challenge

There are $500$ prisoners locked in a prison. One day, a jailer gives them a chance to leave. The jailer places two bags, A and B, with coins in the room. Each bag holds at least $1$ and at most $N$ coins. The two bags hold different numbers of coins. The prisoners' goal is to find the bag with fewer coins.

The room also has a blackboard. The blackboard can hold only one integer at any time. Initially, the blackboard shows $0$.

The jailer lets the prisoners enter the room one at a time. No prisoner knows who entered before him, or how many prisoners were in the room before him. Each time a prisoner enters, he reads the integer on the blackboard. After reading it, he must choose bag A or bag B. He then inspects that bag and learns how many coins it holds. Then he must take one of the following two actions.

• Erase the integer on the blackboard, write a non-negative integer, and leave the room. The new integer may be the same as the old one or different. The challenge continues, unless all $500$ prisoners have entered and left.
• Pick the bag with fewer coins and end the challenge.

Once a prisoner leaves the room, the jailer does not let him back in.

If one prisoner picks the bag with fewer coins correctly, the prisoners win. If any prisoner picks the wrong bag, or if all $500$ prisoners enter and leave without anyone trying to pick the bag with fewer coins, the prisoners lose.

Before the challenge begins, the prisoners meet in an assembly hall and agree on a common strategy with three steps.

• Decide the maximum non-negative integer $x$ that may be written on the blackboard.
• Decide which bag to inspect when a prisoner enters and the blackboard shows an integer $i$ ($0 \le i \le x$).
• Decide what to do after learning the coin count of the inspected bag. Specifically, when the blackboard shows an integer $i$ ($0 \le i \le x$) and the inspected bag holds $j$ coins, the prisoner must do one of the following: write an integer from $0$ to $x$ on the blackboard, or pick the bag with fewer coins.

If the prisoners win, the jailer keeps them for $x$ more days and then releases them all.

Your task is to design a strategy with which the prisoners can win this challenge. (See Subtasks for details.) The score of your solution depends on the value of $x$.

• $2 \le N \le 5000$