Internet Problem Solving Contest

IPSC 2018

Problem M – McDroid's

The trend is clear: the number of robots in the world is growing and growing. You decided to become an entrepreneur and open the first robot restaurant in the world. Not a restaurant staffed by robots – a restaurant for robots. After a long preparation, everything is finally ready for the grand opening.

You have a long menu with many different kinds of delicious robot food. Most humans would probably just be confused because robot recipes don’t have names, only numbers. And of course, robots only use binary. You’re sure the restaurant will become very popular and it will attract a big crowd. As the owner, your biggest challenge is managing your time and making sure you don’t leave anybody (anyboty?) waiting. Your second biggest challenge is that it’s not always easy to understand what food the robots want.

Problem specification

In this problem, you will interact with an online dashboard page.

The page has a button to open the restaurant. When you press the button, your restaurant will open and it will start getting robot customers. Your team has just one restaurant. You will see the same restaurant if you access the dashboard from multiple browsers. Note that time continues to run even if you close the page.

Every customer will tell you what they want, and you must choose what food to give them. Some robots might just tell you “HELLO I WOULD LIKE TO ORDER FOOD ITEM 1101.”, in which case you’d obviously give them 1101. For other customers figuring out what they want may be more complicated. You’ll see.

Robots will arrive in real time. Each robot is only willing to wait for some predetermined period of time (at least a minute, sometimes more). You may have multiple robots waiting in your restaurant at the same time. For each of them you will see the time left to serve them.

When you first open your restaurant, you’ll have 10 reputation points.

There are two things that can go wrong at your restaurant:

Initially, the rules for solving subproblems M1 and M2 are as follows:

Whenever your reputation reaches zero, you go bankrupt. You can then reopen the restaurant and continue trying to solve this problem. Whenever you reopen your restaurant, the following things will happen:


Input and output specification

There is no input and no output. You will automatically get an OK verdict for a subproblem the moment the total time your restaurant was open reaches the corresponding threshold.