Đường đi của Robot (THTB Đà Nẵng 2022)

Xem PDF



Tác giả:
Dạng bài
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: robot.inp Output: robot.out

Có 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\)\(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\)\(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 1
Output
2

Bình luận


  • 0
    Habaxl 5:12 p.m. 20 Tháng 8, 2023

    cộng 2 số lớn bằng xử lí xâu vẫn AC được 😃


    • 0
      sync9w_mk 11:34 a.m. 23 Tháng 5, 2023 đã chỉnh sửa

      khoai v 🙂


      • 3
        obamagaming 11:32 a.m. 28 Tháng 5, 2022 đã chỉnh sửa

        Test 8 với test 10 Bignum phải không ạ :((
        edit: Downvote chi vay mng:)

        1 phản hồi

        • -5
          dang7rickroll 10:29 p.m. 20 Tháng 5, 2022

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.