Đường đi của Robot (THTB Đà Nẵng 2022)
Xem PDFCó một lưới ô vuông có kích thước \(N × N\) được đánh chỉ số hàng từ \(1\) đến \(N\) (theo chiều từ trên xuống dưới) và chỉ số cột từ \(1\) đến \(N\) (theo chiều từ trái sang phải). Mỗi ô trong lưới được xác định vị trí bởi một cặp số \((i; j)\) trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột.
Tại ô \((1; 1)\) người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.
Yêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô \((1; 1)\) đến ô \((N; N)\). Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.
VD: Xét lưới ô vuông kích thước \(3\times 3\) như hình vẽ sau:
Trong lưới ô vuông \(3\times 3\) này người ta đặt viên đá vào ô \((1;3)\) và ô \((2;1)\).
Với dữ kiện trên thì robot có tất cả 2 đường đi như sau:
\((1;1) → (1;2) → (2;2) → (2;3) → (3;3)\)
\((1;1) → (1;2) → (2;2) → (3;2) → (3;3)\)
Input
Đọc từ file văn bản ROBOT.INP có cấu trúc như sau:
- Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(M\) (mỗi số cách nhau 1 dấu cách; \(M < N\)).
- \(M\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương \(i\) và \(j\) (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.
Output
- Ghi ra file văn bản ROBOT.OUT một số \(k\) là số đường đi của robot từ ô \((1; 1)\) đến ô \((N; N)\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N \le 10\).
- Subtask \(2\) (\(40\%\) số điểm): \(10 < N \le 30\).
- Subtask \(3\) (\(30\%\) số điểm): \(30 < N \le 100\).
Example
Test 1
Input
3 2
1 3
2 1Output
2
Bình luận
cộng 2 số lớn bằng xử lí xâu vẫn AC được 😃
khoai v 🙂
Test 8 với test 10 Bignum phải không ạ :((
edit: Downvote chi vay mng:)
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.