문제
로봇을 제어하는 데 사용할 수 있는 N개의 명령을 포함하는 명령 목록이 있을 때, 로봇의 주인은 로봇이 좌표평면 상의 (0,0) 위치에서 시작하여 (xg, yg) 위치로 이동하려 한다.
이 중 i 번째 명령은 로봇이 오른쪽으로 xi만큼, 위로 yi만큼 이동시킨다. (음수일 때는 반대로 이동시킨다)
로봇이 최종 위치 (xg, yg)에 도착하기까지 각 명령어는 한 번씩밖에 못쓴다.
K개의 명령어를 사용하여 도착한다고 할 때, 1부터 N까지의 K에 대하여 각각 몇 가지 방법의 수가 있는지 출력하시오.
입력
첫 번째 줄에는 N이 입력된다. (1≤N≤40)
두 번째 줄에는 −109…109 범위에 있는 xg와 yg가 입력된다.
세 번째 줄부터 N줄에 걸쳐 −109…109 범위의 두 정수 xi와 yi가 입력된다.
입력은 모든 i에 대해 (xg,yg)≠(0,0)이며 (xi,yi)≠(0,0)임을 보장한다.
출력
K개의 명령어를 사용하여 도착한다고 할 때, 1부터 N까지의 K에 대하여 각각 몇 가지 방법의 수가 있는지 출력하시오.
예제1
입력
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10
출력
0
2
0
3
0
1
0
힌트
출처
USACO 2022 February Silver