Mê cung được cho dưới dạng một lưới ô vuông gồm M dòng, N cột. Ô ở dòng i, cột j ghi số nguyên dương Ai,j, toàn bộ các số trên lưới khác nhau đôi một. Một Robot thực hiện một chuyến thám hiểm có thể xuất phát tại một ô bất kì trên lưới, mỗi bước, nó chỉ được phép di chuyển sang một ô khác kề cạnh với ô đang đứng (cũng phải ở trong lưới) và số ghi trên đó nhỏ hơn số ghi trên ô hiện tại. Robot có thể kết thúc chuyến thám hiểm bất kì khi nào nó muốn (kể cả khi dừng lại ngay ở ô xuất phát). Yêu cầu: Đếm xem có tất cả bao nhiêu chuyến thám hiểm mà những ô Robot đi qua tạo thành một miền là hình chữ nhật (tính cả các ô bên trong biên của hình chữ nhật) có các cạnh song song với các cạnh của lưới ban đầu. Hai chuyến thám hiểm coi là khác nhau nếu tập tất cả các ô Robot đi qua là khác nhau.

Dữ liệu: Vào từ tệp văn bản REC.INP gồm:

• Dòng đầu chứa hai số nguyên dương M và N (M * N ≤ 50000).
• M dòng tiếp theo, mỗi dòng chứa N số nguyên dương thể hiện các số trên lưới ô vuông. Các số này là khác nhau đôi một và không quá 107.

  Kết quả: Ghi ra tệp văn bản REC.OUT gồm một số duy nhất là kết quả tìm được.

Ví dụ:

    REC.INP         REC.OUT
    3 2             15
    18 10
    19 12
    17 13   

    3 3             29
    8 1 2
    7 9 3
    6 5 4

Ràng buộc:

• Có 3 điểm có M = 1;
• Có 3 điểm tiếp theo có M * N ≤ 100;
• Có 1 điểm còn lại có M * N ≤ 7000.

Trang trại của Tèo có n con bò tót đánh số từ 1 đến n và m chuồng bò đánh số từ 1 đến m. Các chuồng bò được thiết kế theo hàng ngang từ trái sang phải, chuồng bên trái nhất là chuồng 1, tiếp theo là chuồng 2,..., cuối cùng là chuồng m. Mỗi chuồng có chiều rộng đúng 1 mét, các chuồng kề nhau được ngăn cách bằng một tấm tôn có bề dày không đáng kể. Khoảng cách từ chuồng thứ i đến chuồng thứ j (với mọi 1 ≤ i,j ≤ m) được tính là |j-i| mét. Con bò thứ i (i=1..n) có độ hung hãn là ai, tức là con bò này sẽ rất bực bội nếu nó được xếp vào một chuồng X mà tồn tại một chuồng Y, Y khác X và khoảng cách từ chuồng X đến chuồng Y bé hơn ai và trong chuồng Y có bò.

Yêu cầu: Giúp Tèo đếm số cách xếp n con bò vào n chuồng trong m chuồng, mỗi chuồng không quá một con bò, sao cho không có con bò nào bị bực bội. Hai cách xếp được coi là khác nhau nếu trong hai cách xếp tồn tại một con bò i (với i=1..n) được xếp ở hai chuồng khác nhau.

Dữ liệu: Vào từ tệp văn bản XEPBO.INP theo khuôn dạng:

• Dòng đầu ghi hai số nguyên dương n, m (n ≤ 50; n ≤ m ≤ 104);
• Dòng thứ hai chứa n số nguyên dương a1, a2,..an (ai ≤ m với mọi i =1..n);

  Kết quả: Ghi ra tệp văn bản XEPBO.OUT một số nguyên duy nhất là số cách xếp bò theo yêu cầu chia lấy dư cho 109+7.

Ví dụ:

    XEPBO.INP   XEPBO.OUT
    3 4         4
    1 2 1       
    1 3 – 2
    3 1 – 2
    2 – 1 3
    2 – 3 1
    Giải thích ví dụ
Có 3 con bò và 4 chuồng thì có 4 cách xếp là:
Dấu – biểu thị chuồng bỏ trống; 1, 2, 3 là số hiệu các con bò.

Ràng buộc:

• Có 2 điểm có a1 = a2 =...= an;
• Có 2 điểm tiếp theo có n ≤ 10;
• Có 3 điểm còn lại không còn ràng buộc gì thêm.

Chuyến xe cứu trợ đồng bào Miền Bắc sau cơn bão Yagi được xuất phát tại Thanh Hoá đi qua các thành phố như Ninh Bình, Hà Nam,… một cách rất nhanh chóng. Nhưng khi xe đi vào thủ đô Hà Nội thì trời mưa to, một số tuyến phố bị ngập sâu. Thủ đô Hà Nội có hệ thống giao thông gồm n nút giao thông và m con đường hai chiều. Con đường thứ i (i=1..m) nối trực tiếp giữa hai nút giao thông ui, vi có độ ngập sâu là hi và thời gian đi qua là ti (ti không phụ thuộc vào hi), tất nhiên nếu tuyến đường ngập quá sâu thì xe sẽ gặp khó khăn khi đi qua.

Yêu cầu: Tìm hành trình để xe di chuyển từ nút giao thông X đến nút giao thông Y sao cho độ ngập sâu nhất trong tất cả các con đường đi qua là nhỏ nhất. Nếu có nhiều hành trình như vậy thì tìm hành trình có tổng thời gian di chuyển bé nhất. Biết rằng các con đường được thiết kế để luôn tồn tại hành trình từ X đến Y.

Dữ liệu: Vào từ tệp văn bản YAGI.INP gồm:

• Dòng đầu tiên ghi 3 số nguyên dương n, X, Y (X, Y ≤ n ≤ 105);
• Dòng tiếp theo là số nguyên dương m (m ≤ 106);

• Dòng thứ i trong m dòng tiếp theo (i=1..m) ghi bốn số nguyên dương ui, vi, hi, ti (ui, vi ≤ n; hi, ti ≤ 109).

  Dữ liệu: Ghi ra file văn bản YAGI.OUT gồm:

• Dòng thứ nhất ghi một số nguyên dương là độ sâu thoả mãn yêu cầu bài toán;

• Dòng thứ hai ghi tổng thời gian di chuyển của hành trình tìm được.

  Ví dụ:

  YAGI.INP            YAGI.OUT
  6 2 4               300
  10                  800
  2 1 900 100
  5 2 400 700
  1 5 200 600
  6 3 200 200
  4 5 100 100
  2 6 300 400
  1 6 500 200
  6 5 200 300
  3 4 200 300
  3 5 300 100
  

  Giải thích: Không có hành trình nào mà tất cả con đường đi qua có độ ngập sâu bé hơn 300 và trong số các hành trình đi qua con đường ngập sâu 300 thì hành trình có thời gian ngắn nhất là 2  6  5  4 với thời gian là 800.

Ràng buộc:

• Có 3 điểm có: hi=1 với mọi i =1..m;
• Có 3 điểm còn lại không có ràng buộc gì thêm.