Dò Tìm Trên Ma Trận Tăng Dần
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ ma trận và các giá trị cần tìm được cho trước).
Cho ma trận $A$ kích thước $R \times C$ có các phần tử trên mỗi hàng tăng dần từ trái sang phải, và trên mỗi cột tăng dần từ trên xuống dưới. Với mỗi số $X$ cần tìm, thuật toán tìm kiếm Saddleback bắt đầu từ góc trên bên phải $(r = 1, c = C)$:
- Hỏi giá trị $A_{r, c}$ (tính 1 bước).
- Nếu $A_{r, c} = X$, dừng lại và trả về tọa độ $(r, c)$.
- Nếu $A_{r, c} > X$, giảm $c \leftarrow c - 1$; ngược lại tăng $r \leftarrow r + 1$.
- Nếu ra ngoài ma trận ($r > R$ hoặc $c < 1$), dừng lại và trả về
(-1, -1).
Cho $Q$ truy vấn tìm các giá trị $X_1, \dots, X_Q$. Với mỗi truy vấn, hãy in ra tọa độ tìm được (hoặc -1 -1) và số bước hỏi đã thực hiện.
Dữ liệu vào
- Dòng đầu ghi ba số nguyên $R, C, Q$ ($1 \le R, C \le 500$, $1 \le Q \le 1000$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ số nguyên ($|A_{i,j}| \le 10^9$).
- Dòng cuối ghi $Q$ số nguyên $X_1, \dots, X_Q$ ($|X_k| \le 10^9$).
Dữ liệu ra
- $Q$ dòng, mỗi dòng ghi
r c steps(nếu không tìm thấy thì ghi-1 -1 steps).
Ví dụ
| Input | Output |
|---|---|
| 3 3 2 1 4 7 2 5 8 3 6 9 5 10 |
2 2 3 -1 -1 3 |
Giới hạn
- $1 \le R, C \le 500$
- $1 \le Q \le 1000$
Community Discussion