New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1824: [NewOJ Week 7] 机器人与指令

内存限制：512 MB 时间限制：4 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：9 通过：3
提交提交记录统计

题目描述

机器人在(0,0)位置，需要移动到终点(sx,sy)位置。
现在有N条指令，每条指令有两个数字(x,y)，表示将机器人的横坐标加上x，纵坐标加上y。x和y可以为负数。
现在对于1到N中的每一个K，请求出从N条指令中选择K条的方案数，使得执行这K条指令后，机器人恰好到达终点。
注意本题的时间为4s，空间为512MB。

输入格式

输入第一行为正整数N，1≤N≤40。
第一行为sx和sy。接下来N行，每行两个正整数xi,yi。
所有坐标点的范围均为[-10^9,10^9]，保证输入的所有点坐标≠(0,0)。

输出格式

输出N行，对1到N的每一个K，输出选择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

数据范围与提示

在这个例子中，有六种选择指令的方法： 

(-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)