Dò Tìm Trên Ma Trận Tăng Dần

Binary-search Buổi 63 — Interactive & Constructive
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved