A863. Robot Instructions--Silver
编程题
提高+/省选-
知识点
题目描述
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 $(x_g, y_g)$. Bessie initially has a list of $N$
($1\le N\le 40$) instructions to give to the robot, the $i$-th of which will
move the robot $x_i$ units right and $y_i$ units up (or left or down when
$x_i$ and $y_i$ 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 $(x_g, y_g)$.
****Note: the time and memory limits for this problem are 4s and 512MB, twice
the defaults.****
The robot begins at point $(0, 0)$ on the coordinate plane and Bessie wants
the robot to end at point $(x_g, y_g)$. Bessie initially has a list of $N$
($1\le N\le 40$) instructions to give to the robot, the $i$-th of which will
move the robot $x_i$ units right and $y_i$ units up (or left or down when
$x_i$ and $y_i$ 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 $(x_g, y_g)$.
****Note: the time and memory limits for this problem are 4s and 512MB, twice
the defaults.****
输入格式
The first line contains $N$. The next line contains $x_g$ and $y_g$, each in
the range $-10^9 \ldots 10^9$. The final $N$ lines describe the instructions.
Each line has two integers $x_i$ and $y_i$, also in the range $-10^9 \ldots
10^9$.
It is guaranteed that $(x_g,y_g)\neq (0,0)$ and $(x_i,y_i)\neq (0,0)$ for all
$i$.
the range $-10^9 \ldots 10^9$. The final $N$ lines describe the instructions.
Each line has two integers $x_i$ and $y_i$, also in the range $-10^9 \ldots
10^9$.
It is guaranteed that $(x_g,y_g)\neq (0,0)$ and $(x_i,y_i)\neq (0,0)$ for all
$i$.
输出格式
Print $N$ lines, the number of ways Bessie can select $K$ instructions from
the original $N$ for each $K$ from $1$ to $N$.
the original $N$ for each $K$ from $1$ to $N$.
输入输出样例
输入 #1
7 5 10 -2 0 3 0 4 0 5 0 0 10 0 -10 0 10
输出 #1
0 2 0 3 0 1 0
说明/提示
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)
(-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)