Problem F
Ask Marilyn
Marilyn is by far your favourite bartender, because she turns every order into a game.
At the bar, there are three small boxes with doors labelled A, B, and C. When you buy a drink, Marilyn places the bottle in one of the boxes; you don’t know which. Then the following ritual unfolds. You point to one of the three doors. Marilyn will then smile enigmatically and open one of the other doors, showing its contents. You then get to change your original decision: maybe you now pick the door Marilyn just opened (in particular if you can see the bottle there!), or you stick with your first choice, or you pick the remaining door. Whatever you finally choose is what you get.
This entire ritual -– you choose, Marilyn opens, you make your final decision – is called a round. It’s been a long week, so you’ll play $1\, 000$ rounds. You need to get as many drinks as you can.
Interaction
Your program interacts with Marilyn using standard input and output. You start each round by printing your initial choice of door, as a single letter on a line:
you$\rangle $ A – meaning “My initial choice is door A”
Now Marilyn will pick one of the other two doors – she may be in a good mood and pick the door with a drink behind it, or she may pick a door with no drink behind it; she may choose randomly, or helpfully, or she may want to deliberately confuse you. Being a good bartender, Marilyn knows where the drink is, and she knows you well enough to know your strategy, both of which she may take into account or not. She’ll print her door name, followed by the number of bottles ($0$ or $1$) behind that door. For instance, if she chose to open door C, she will truthfully respond with either of:
-
marilyn$\rangle $ C 0 – meaning “Well, wouldn’t you know it? There is nothing behind door C.”
-
marilyn$\rangle $ C 1 – meaning “Huh. Looks like the bottle is behind door C.”
We let her output just those two symbols—instead of her actual charming, varied, and loquacious banter—to make it easy to parse. You’d have to meet her in person for the real experience.
After that you print another letter, namely your final choice of door. Let’s say you pick door A:
you$\rangle $ A – meaning “I’ll take whatever is behind door A now.”
Marilyn will respond with one of two lines, depending on whether there was a drink behind your final choice of door or not. The format is the number of bottles you receive ($0$ or $1$) followed by the door that actually concealed the bottle.
-
marilyn$\rangle $ 1 A – meaning “Door A was a great choice. You’re always so clever. Enjoy your drink.”
-
marilyn$\rangle $ 0 B – meaning “Oh, what a shame. The bottle was actually behind door B.”
After $1\, 000$ rounds, your program must exit. If you end up with at least $600$ drinks, no matter which strategy Marilyn uses, your program is accepted. Otherwise it is judged as wrong answer.
Below is an example of the first three rounds of interaction. In each of the rounds, the drink is behind door A. You got $2$ of the $3$ drinks.
| Read | Sample Interaction 1 | Write |
|---|
A
B 0
A
1 A
A
B 0
C
0 A
B
A 1
A
1 A
