Hướng dẫn giải của Số Nguyên Ẩn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Hướng tiếp cận

Bài toán yêu cầu tìm một số trong đoạn $[1, 10^{9}]$ với tối đa $30$ câu hỏi dạng "số $y$ có nhỏ hơn $x$ không?". Đây là bài toán tìm kiếm nhị phân cổ điển.

Nhận xét quan trọng

Mỗi câu hỏi chia đôi không gian tìm kiếm: nếu $y < x$ thì $x \in [y + 1, h i]$ , ngược lại $x \in [l o, y]$ .
Với $30$ câu hỏi, ta có thể tìm trong đoạn có kích thước tối đa $2^{30} = 1, 073, 741, 824 > 10^{9}$ .

Thuật toán

Khởi tạo $l o = 1$ , $h i = 10^{9}$ .
Trong khi lo<hi:
- Tính $m i d = ⌊ (l o + h i) / 2 ⌋$ .
- Hỏi ? mid.
- Nếu câu trả lời là YES ( $m i d < x$ ): gán $l o = m i d + 1$ .
- Nếu câu trả lời là NO ( $m i d \geq x$ ): gán $h i = m i d$ .
Khai báo ! lo.

Độ phức tạp

Số câu hỏi: $O (\log_{2} 10^{9}) = 30$
Thời gian: $O (\log n)$
Bộ nhớ: $O (1)$

Bình luận

Không có bình luận tại thời điểm này.