Lệnh Robot

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một robot bắt đầu tại tọa độ $(0, 0)$ và cần đến đích $(x_{g}, y_{g})$ . Bessie có $N$ lệnh di chuyển, lệnh thứ $i$ sẽ di chuyển robot $x_{i}$ đơn vị sang phải và $y_{i}$ đơn vị lên trên (giá trị âm nghĩa là di chuyển sang trái hoặc xuống dưới).

Với mỗi $K$ từ $1$ đến $N$ , đếm số cách chọn đúng $K$ lệnh trong $N$ lệnh sao cho khi thực hiện tất cả các lệnh được chọn (theo thứ tự bất kỳ), robot đến đúng đích.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: Hai số nguyên $x_{g}, y_{g}$ — tọa độ đích
$N$ dòng tiếp theo: Hai số nguyên $x_{i}, y_{i}$ — lệnh thứ $i$

Dữ liệu ra

$N$ dòng, dòng thứ $K$ chứa số cách chọn đúng $K$ lệnh để robot đến đích.

Ràng buộc

$1 \leq N \leq 40$
$- 10^{9} \leq x_{g}, y_{g} \leq 10^{9}$ , $(x_{g}, y_{g}) \neq (0, 0)$
$- 10^{9} \leq x_{i}, y_{i} \leq 10^{9}$ , $(x_{i}, y_{i}) \neq (0, 0)$
Giới hạn thời gian: 4 giây, bộ nhớ: 512MB

Ví dụ

Input	Output	Giải thích
7 5 10 -2 0 3 0 4 0 5 0 0 10 0 -10 0 10	0 2 0 3 0 1 0	Với $K = 2$ : có 2 cách chọn 2 lệnh để đến $(5, 10)$ : lệnh {4,5} hoặc lệnh {4,7}.

Bình luận

Không có bình luận tại thời điểm này.