TLEoj Contest #07 - Thoát khỏi kim tự tháp

Điểm: 1100 (thành phần)

Thời gian: 1.0s

Python 3 3.0s

Bộ nhớ: 256M

Python 3 512M

Input: bàn phím

Output: màn hình

Tác giả:

Noobcoder

Dạng bài

Một trò chơi mới được khai trương tại khu vui chơi, nó có tên là: “Thoát khỏi kim tự tháp”.
Mặt trước của khu vực chơi có thể được miêu tả bằng một ma trận $A$ có $n$ hàng (các hàng được đánh số từ $1→n$ từ trên xuống dưới) và $m$ cột (các cột được đánh số từ $1→m$ từ trái sang phải). Trong số các phòng có thể di chuyển qua lại, thời gian di chuyển có thể được xem là $1s$ . Bạn sẽ xuất phát ở tầng n, và cố gắng lên đến tầng cao nhất (trong số những tầng có thể lên) trong một khoảng thời gian không quá $t$ giây. Nếu thành công sẽ có thưởng. Có 2 ràng buộc cho trò chơi này là:

Ràng buộc 1: Bạn bắt buộc phải xuất phát từ hai phòng ở tận cùng bên trái hoặc tận cùng bên phải (trong số những phòng có thể vào được) ở tầng $n$ .
Ràng buộc 2: Bạn bắt buộc không được phép vào một phòng bất kì nếu hoặc nó không thể vào hoặc bạn đã vào phòng đó trước đó.
Ràng buộc 3: Nếu bạn ở tầng cao nhất và quyết định lên thêm thì đồng nghĩa rằng bạn chọn kết thúc trò chơi, và thời gian bạn lên sẽ không tính và trò chơi sẽ kết thúc.

Explanation

Mô tả	Minh họa
Đây là một ví dụ cho kim tự tháp có thể được cho (các ô vàng là các phòng có thể đi qua, và các ô cam là các phòng không thể đi qua).
Đây là một trường hợp hợp lệ vì thỏa mãn cả 2 ràng buộc đưa ra.
Đây là một trường hợp không hợp lệ vì không thỏa mãn ràng buộc số 1 (không xuất phát tại hai phòng ở tận cùng bên trái hoặc tận cùng bên phải ở tầng n).
Đây là một trường hợp không hợp lệ cũng vì không thỏa mãn ràng buộc số 1 (không xuất phát tại tầng n).
Đây là một trường hợp không hợp lệ vì không thỏa mãn ràng buộc số 2 (đi qua một ô 2 lần).

Để cho trò chơi mang tính thử thách hơn thì ban tổ chức quyết định sẽ giao cho một người chơi bất kì một giá trị t bất kì, và họ sẽ sử dụng một phương pháp sinh số ngẫu nhiên nào đó. Tuy nhiên, họ muốn bất kì giá trị nào cho ra đều sẽ có một cách chơi giúp người chơi giành giải thưởng (không khiến trò chơi trở nên impossible), tuy nhiên vẫn đủ để thử thách người chơi (họ không thể tùy tiện di chuyển mà vẫn thắng). Vì vậy, họ cần tìm ra hai giá trị $L$ và $R$ $(1≤L≤R)$ lần lượt là thời gian nhanh nhất và lâu nhất có thể để một người chơi hoàn thành trò chơi.
Họ quá bận trong việc điều hành các trò chơi khác trong khu vui chơi. Vì vậy, bạn hãy giúp họ tìm ra giá trị $L$ và $R$ thỏa mãn.

Input, Output và Subtask

Input

Dòng một gồm một giá trị $q$ là số lượng testcase cần được xử lí $(1 ≤ q ≤ 100)$ ;
Mỗi bộ testcase có cấu trúc như sau:
Dòng hai gồm hai giá trị $n$ , $m$ là số hàng và số cột của ma trận $A$ $(1 ≤ n, m ≤ 10^4, 1 ≤ n \times m ≤ 10^6)$ ;
$n$ dòng sau, mỗi dòng gồm hai số nguyên dương $u_i, v_i$ $(1 \le u_i \le v_i \le m + 1)$ , với $u_i$ là ô đầu tiên có thể đi qua được trên hàng thứ $i$ , và $v_i$ là ô đầu tiên sau $u_i$ không thể đi qua được trên hàng thứ $i$ . Nếu $u_i = v_i$ nghĩa là hàng đó không có ô nào đi qua được.
*Ràng buộc: Các ô có thể đi qua tạo thành một kim tự tháp có độ cao $h$ $(1 ≤ h ≤ n)$ . Hay nói cách khác, $l_n \le l_{n - 1} \le l_{n - 2} \le ... \le l_1 \le r_1 \le r_2 \le ... \le r_n$ .
Hệ thống hóa lại ràng buộc số 1, ta có được 2 điểm xuất phát bắt buộc là hai ô có tọa độ $(l_n, n)$ và $(r_n - 1, n)$ .
Dữ liệu đầu vào đảm bảo $l_n < r_n$ .

Output

Với mỗi testcase, in ra độ dài đường đi nhanh nhất và lâu nhất tìm được.

Sample

Input

Output

8 16
2 2

Explanation

Giải thích test 1: Đường đi nhanh nhất và lâu nhất có thể được thực hiện như bên dưới.

Đường đi nhanh nhất (8)	Đường đi lâu nhất (16)

Bình luận

Không có bình luận nào.