This page is still under construction.

Parts of this page are still being built. What you see may change.

No Tipping

Interview

Time limit1sMemory limit128 MB

Summary
Count the orders in which n packages can be removed from a lever on two fulcrums so the board never tips.
Level

Medium6 of 10

Topics
Backtracking, Bit manipulation, Dynamic programming
Solved
No attempts yet

Problem

If you place an object on a lever arm, it exerts a twisting force around the lever's fulcrum. This twist is called torque, and its magnitude equals the object's weight multiplied by its distance from the fulcrum. If the object is to the left of the fulcrum the torque is counterclockwise; if it is to the right the torque is clockwise. The total torque around a support is the sum of the torques of every object on the lever (the board itself also counts as an object whose weight acts at its center).

There is a straight board of uniform thickness and evenly distributed weight. Its middle is the center of mass, which we call position 0, so the two ends of a board of length LL are at positions −L/2-L/2 and +L/2+L/2. The board rests on two identical fulcrums at positions −1.5-1.5 and +1.5+1.5. Several packages sit on the board; each package is given by an integer position (measured from the center, negative meaning to the left) and an integer weight.

You remove the packages one at a time. The board must never tip: it tips if the net torque around the left fulcrum (from the packages and the board's own weight) is counterclockwise, or if the net torque around the right fulcrum is clockwise. If the net torque at a fulcrum is exactly balanced (zero), the board does not tip. The board must stay balanced in the initial configuration and after every single removal (a board with no packages is always balanced).

For example, a board weighing 3kg and 20m long rests on the two fulcrums with six packages at positions −8,−4,−3,2,5,8-8, -4, -3, 2, 5, 8 having weights 4,10,10,4,7,84, 10, 10, 4, 7, 8kg respectively.

For this configuration there are several removal orders that keep the board from tipping.

Input

The input consists of several test cases. Each test case begins with three integers: the length of the board (in meters, at least 3), the weight of the board (in kilograms), and the number of packages nn (n≤20n \le 20). The board is always supported at positions −1.5-1.5 and +1.5+1.5 by two identical fulcrums. The following nn lines each contain two integers: the position of a package (measured from the center, negative meaning to the left) and its weight (in kilograms). The input ends with a line containing three zeros, which is not a test case.

Output

For each test case, output one line of the form Case X: C, where X is the test-case number starting from 1 and C is the number of distinct orders in which the packages can be removed one at a time so that the board never tips after any removal. Packages listed on different input lines are distinct even when they share the same position and weight. If the packages cannot all be removed without the board tipping — in particular, if the initial configuration already tips — output C as 0.

Examples3

  1. Example 1

    Input
    20 3 6
-8 4
-4 10
-3 10
2 4
5 7
8 8
20 3 15
1 10
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
30 10 2
-8 100
9 91
0 0 0
    Expected output
    Case 1: 2
Case 2: 37194897996
Case 3: 0

  2. Example 2

    Input
    20 3 1
0 1
0 0 0
    Expected output
    Case 1: 1

  3. Example 3

    Input
    20 3 1
10 1000
0 0 0
    Expected output
    Case 1: 0