Robot Instructions
플래티넘 IV의견: 0
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.*
Problem credits: Alex Liang
SCORING
- Test cases 2-4 satisfy \(N\le 20\).
- Test cases 5-16 satisfy no additional constraints.
Problem credits: Alex Liang
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\).
Print \(N\) lines, the number of ways Bessie can select \(K\) instructions from the
original \(N\) for each \(K\) from \(1\) to \(N\).
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 100
2
0
3
0
1
0In 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)
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Silver
평가 및 의견
Robot Instructions
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Robot Instructions