Robot Instructions
Bessie is learning how to control a robot she has recently received as a gift.
The robot begins at point (0,0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg). Bessie initially has a list of N (1≤N≤40) instructions to give to the robot, the i-th of which will move the robot xi units right and yi units up (or left or down when xi and yi are negative, respectively).
For each K from 1 to N, help Bessie count the number of ways she can select K instructions from the original N such that after the K instructions are executed, the robot will end at point (xg,yg).
**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**
In this example, there are six ways Bessie can select the instructions:
(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7) (-2,0) (3,0) (4,0) (0,10) (1 2 3 5) (-2,0) (3,0) (4,0) (0,10) (1 2 3 7) (5,0) (0,10) (0,-10) (0,10) (4 5 6 7) (5,0) (0,10) (4 5) (5,0) (0,10) (4 7)
For the first way, the robot's path looks as follows:
(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)
SCORING:
- Test cases 2-4 satisfy N≤20.
- Test cases 5-16 satisfy no additional constraints.
Problem credits: Alex Liang
Source: USA Computing Olympiad.
Input Format
The first line contains N. The next line contains xg and yg, each in the range −109…109. The final N lines describe the instructions. Each line has two integers xi and yi, also in the range −109…109.
It is guaranteed that (xg,yg)=(0,0) and (xi,yi)=(0,0) for all i.
Output Format
Print N lines, the number of ways Bessie can select K instructions from the original N for each K from 1 to N.