[HSG3_HP_24] Robot
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python
Cho một ma trận kích thước ~n \times n~, ô giao dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Một robot đang ở ô ~(u, v)~ muốn di chuyển về ô góc dưới phải ~(n, n)~ của ma trận.
Yêu cầu
Hãy trả lời ~q~ truy vấn, mỗi truy vấn cho biết số cách di chuyển của robot về ô ~(n, n)~ biết rằng robot chỉ đi được xuống dưới hoặc sang phải. Vì số cách đi là rất lớn nên kết quả được lấy dư cho ~10^9 + 7~.
Dữ liệu đầu vào
Gồm ~q + 1~ dòng:
- Dòng đầu chứa hai số nguyên ~n~ ~(2 \le n \le 10^3)~ và ~q~ ~(1 \le q \le 10^3)~, trong đó ~q~ là số truy vấn;
- ~q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le q)~ chứa hai số ~u,\ v~ ~(1 \le u, v \le n)~ là vị trí của robot (dòng ~u~, cột ~v~) ở truy vấn ~i~.
Dữ liệu đầu ra
Gồm ~q~ dòng, dòng thứ ~i~ ~(1 \le i \le q)~ là kết quả của truy vấn ~i~.
Ràng buộc dữ liệu
- 10% số điểm có ~n = 2~;
- 20% số điểm có ~n = 3~;
- 20% số điểm có ~q = 1~;
- 20% số điểm có ~2 \le n, q \le 10^2~.
Ví dụ
Ví dụ 1
INPUT
5 3
4 4
4 2
5 5
OUTPUT
2
4
1
Giải thích:
Hình trên mô tả ~2~ cách di chuyển của robot từ ô ~(4, 4)~ về ô ~(5, 5)~.
Bình luận
https://anotepad.com/note/download/hnxwm87b?format=Text