레이팅 미적용베시는 최근 선물로 받은 로봇을 조종하는 법을 배우고 있다.
로봇은 좌표평면의 점 \((0, 0)\)에서 출발하며, 베시는 로봇이 점 \((x_g, y_g)\)에서 끝나기를 원한다. 베시는 처음에 로봇에게 내릴 \(N\) (\(1\le N\le 40\))개의 명령 목록을 가지고 있으며, 그중 \(i\)번째 명령은 로봇을 오른쪽으로 \(x_i\)칸, 위로 \(y_i\)칸 이동시킨다(\(x_i\)와 \(y_i\)가 음수이면 각각 왼쪽, 아래로 이동한다).
\(1\)부터 \(N\)까지의 각 \(K\)에 대해, 원래의 \(N\)개 명령 중 \(K\)개를 선택하여 그 \(K\)개의 명령을 실행한 후 로봇이 점 \((x_g, y_g)\)에서 끝나도록 하는 방법의 수를 세는 것을 도와주자.
*참고: 이 문제의 시간 제한과 메모리 제한은 4초와 512MB로, 기본값의 두 배이다.*
출제자: Alex Liang
배점
- 테스트 케이스 2-4는 \(N\le 20\)을 만족한다.
- 테스트 케이스 5-16에는 추가 제약이 없다.
출제자: Alex Liang
첫째 줄에 \(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\)개의 줄에 걸쳐, \(1\)부터 \(N\)까지의 각 \(K\)에 대해 베시가 원래의 \(N\)개 명령 중 \(K\)개를 선택하는 방법의 수를 출력한다.
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