National Olympiad in Informatics, China, 1998

Day 1, Problem 2 - Free Pizza

SERKOI has recently released a new game called "Free Pizza."(*) The game takes place on a stage that is W units wide and H units tall, where the player takes up 1 square unit. When the game begins, the player stands directly on the middle of the stage holding a plate. The figure below depicts an in-progress game with a 4-unit tall stage.

After the game has begun, pizza begins to continuously appear and fall (straight down) from the top of the grid at various locations. Each pizza's initial height is H, while the player's height is 1. The player must move left and right to catch the pizzas. Every second, the player may move their character left or right by one or two units. They may also choose to stay at the same spot and not move.

There are many types of pizzas. The player has already assigned scores to each type according to his or her own taste. At the same time, the 8-308 computer will make pizzas fall at various speeds, measured in unit/seconds.

At any given time, if a pizza and the player both happen to occupy the same cell, then the player will acquire that pizza - however, a pizza may only be collected if it enters the player's cell (at height 1) at an integral point in time. Write a program that helps our player collect pizzas, while maximizing the total score of all the pizzas collected.

Input Format

The first line of input contains two integers W and H, the dimensions of the stage. W will be an odd number between 1 to 99 (inclusive), while H will be an integer between 1 to 100 (inclusive).

The remaining lines will contain information about the pizzas that fall. Specifically, a line will consist of four integers representing the initial time when the pizza begins to fall (in seconds, from 0 to 1000), its horizontal position (in units, where 1 is the leftmost cell of the grid and W is the rightmost), its falling speed (from 1 to 100), and its score value (between 1 and 100). There will be no more than 200 pizzas in the input.

Output Format

The first line of output should contain one integer, the largest total score obtainable from collecting pizzas. Each line after that should describe the move that the player makes at each second to obtain the score. Output 0 to indicate no movement at that second, 1 or 2 to indicate one or two steps to the right, and -1 or -2 to indicate one or two steps to the left. You should keep outputting moves until the player has recieved their last pizza.

It's guaranteed that only one sequence of pizzas collected will produce the maximal score. Furthermore, the player should move such that he is always as close as possible to the next pizza that he will collect. As such, only one sequence of moves will be considered correct.

Sample Input

3 3
0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4

Sample Output

12
-1
1
1

(*) Translator's note: Instead of free pizza, the original problem concerns free "馅饼" (xiàn'r bĭng), which is a traditional Chinese delicacy that is best translated as a filled-pastry or pie. It is commonly used in the expression "天上掉馅饼" (tiān shàng diào xiàn'r bĭng), or "pie falling from from the sky" in a similar way to the English adage "there ain't no such thing as a free lunch", referring to how one must not depend on miracles to happen.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: May 01, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)