P6890: 机器人说明
传统题
4.000s
时间限制
512MB
内存限制
2 提交
2 解决
【题目描述】
【题目描述】
Bessie
正在学习如何控制她最近作为礼物收到的机器人。
机器人从坐标平面上的点 (0,0)
开始移动，而 Bessie 希望机器人移动到点 (xg,yg)。Bessie
初始时有一个包含 N（1≤N≤40
）条指令的指令列表可以用于控制机器人，其中第 i
条指令可以令机器人向右移动 xi 个单位，向上移动 yi 个单位（或向左、向下，当 xi 和 yi 分别为负数时）。
对于从 1
到 N 中的每一个 K，帮助 Bessie
计算她可以从原来的 N 条指令中选择 K 条的方法数，使得在执行这 K 条指令后，机器人将移动到点 (xg,yg)。
**注意：本题的时间和内存限制分别为 4 秒和 512MB，是通常限制的两倍。**
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。第二行包含 xg
和 yg，均在 −10
^9…10
^9
范围内。最后 N 行表示指令。每行包含两个整数 xi 和 yi，同样在 −10
^9…10
^9
范围内。
输入保证 (xg,yg)≠(0,0)
以及对于所有的 ii
有 (xi,yi)≠(0,0)。
【
输出格式】
（输出至终端 /
标准输出）：
输出 N
行，对 1 到 N 中的每一个 K 输出 Bessie 可以从原来的 N 条指令中选择 K 条的方法数。
【
输入样例】
：
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10
【
输出样例】
：
0
2
0
3
0
1
0
【样例说明】
在这个例子中，Bessie
有六种选择指令的方法：
(-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)
对于第一种方法，机器人的移动路径如下：
(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)
【
测试点性质】
：
测试点 2-4
满足 N≤20。
测试点 5-16
没有额外限制。