USACO

USACO 2022 February Contest, Silver

Problem 2. Robot Instructions

Contest has ended.

Log in to allow submissions in analysis mode

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.**

INPUT FORMAT (input arrives from the terminal / stdin):

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$ .

OUTPUT FORMAT (print output to the terminal / stdout):

$N$ lines, the number of ways Bessie can select

$K$ instructions from the original

$N$ for each

$K$ from

$1$ to

$N$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

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)

SCORING:

Test cases 2-4 satisfy $N\le 20$ .
Test cases 5-16 satisfy no additional constraints.

Problem credits: Alex Liang

Contest has ended. No further submissions allowed.