#PU1207. USACO 2022 February Contest, Silver — Problem 2. Robot Instructions

    ID: 1332 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb22来源:usaco.orgscoring:equal_test_cases组合数学

USACO 2022 February Contest, Silver — Problem 2. Robot Instructions

USACO 2022 February Contest, Silver — Problem 2. Robot Instructions

题目描述

Bessie is learning how to control a robot she has recently received as a gift. The robot begins at point (0,0)(0, 0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg)(x_g, y_g). Bessie initially has a list of NN (1≤N≤401\le N\le 40) instructions to give to the robot, the ii-th of which will move the robot xix_i units right and yiy_i units up (or left or down when xix_i and yiy_i are negative, respectively). For each KK from 11 to NN, help Bessie count the number of ways she can select KK instructions from the original NN such that after the KK instructions are executed, the robot will end at point (xg,yg)(x_g, y_g). Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.

输入格式

The first line contains NN. The next line contains xgx_g and ygy_g, each in the range −109…109-10^9 \ldots 10^9. The final NN lines describe the instructions. Each line has two integers xix_i and yiy_i, also in the range −109…109-10^9 \ldots 10^9. It is guaranteed that (xg,yg)≠(0,0)(x_g,y_g)\neq (0,0) and (xi,yi)≠(0,0)(x_i,y_i)\neq (0,0) for all ii.

输出格式

Print NN lines, the number of ways Bessie can select KK instructions from the original NN for each KK from 11 to NN.

数据范围

Test cases 2-4 satisfy N≤20N\le 20. Test cases 5-16 satisfy no additional constraints. Problem credits: Alex Liang

样例

样例 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
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)