Tìm Đỉnh Cực Đại Trên Dãy Đơn Điệu

Binary-search Buổi 63 — Interactive & Constructive
Points
26
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ộ dãy số được cho trước).

Cho dãy số nguyên $A_1, A_2, \dots, A_N$ có tính chất bitonic chặt: tồn tại một chỉ số $P$ ($1 \le P \le N$) sao cho $A_1 < A_2 < \dots < A_P$ và $A_P > A_{P+1} > \dots > A_N$. Để tìm vị trí đỉnh $P$ trong bài toán tương tác, ta dùng chiến lược tìm kiếm nhị phân trên $[L, R]$ (ban đầu $L = 1, R = N$):

  • Khi $L < R$, đặt $mid = \lfloor (L + R) / 2 \rfloor$ và hỏi hai giá trị $A_{mid}$ và $A_{mid+1}$ (chỉ tốn truy vấn cho những chỉ số chưa từng được hỏi trước đó).
  • Nếu $A_{mid} < A_{mid+1}$, cập nhật $L = mid + 1$; ngược lại cập nhật $R = mid$.
  • Khi $L = R$, kết thúc và kết luận đỉnh là $L$.

Hãy mô phỏng chiến lược này để tìm đỉnh $P$ và đếm số chỉ số phân biệt đã phải truy vấn.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($2 \le N \le 10^5$).
  • Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$).
Dữ liệu ra
  • Hai số nguyên: chỉ số đỉnh $P$ và số chỉ số phân biệt đã truy vấn.
Ví dụ
Input Output
6
1 3 8 12 7 4
4 4
Giới hạn
  • $2 \le N \le 10^5$
Draft saved