Robot Instructions

题目描述

Bessie 正在学习如何控制她最近收到作为礼物的一个机器人。 机器人从坐标平面上的点 $(0, 0)$ 开始，Bessie 希望机器人最终到达点 $(x_g, y_g)$。Bessie 最初有一份包含 $N$（$1\le N\le 40$）条指令的列表，第 $i$ 条指令会使机器人向右移动 $x_i$ 个单位、向上移动 $y_i$ 个单位（当 $x_i$ 和 $y_i$ 为负数时，分别表示向左或向下移动）。 对于每个 $K$（从 $1$ 到 $N$），请帮助 Bessie 统计：她从原来的 $N$ 条指令中选出恰好 $K$ 条，使得执行完这 $K$ 条指令后机器人最终位于点 $(x_g, y_g)$ 的方案数。 注意：本题的时间与内存限制为 4s 和 512MB，是默认值的两倍。

输入格式

第一行包含 $N$。 下一行包含 $x_g$ 和 $y_g$，每个都在范围 $-10^9 \ldots 10^9$ 内。 最后的 $N$ 行描述这些指令。每行包含两个整数 $x_i$ 和 $y_i$，也在范围 $-10^9 \ldots 10^9$ 内。 保证 $(x_g,y_g)\neq (0,0)$ 且对所有 $i$，$(x_i,y_i)\neq (0,0)$。

输出格式

输出 $N$ 行：对于每个 $K$ 从 $1$ 到 $N$，输出 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\le 20$。 测试点 5-16 没有额外限制。 题目致谢：Alex Liang

标签: USACO|2022|Silver

来源

USACO|2022|Silver