trang chủ / bài tập / lowerbnd

Tìm cận dưới trong danh sách liên kết (tương tác)

Đây là bài toán tương tác.

Có một danh sách liên kết đơn được sắp xếp tăng dần, xây dựng trên một mảng gồm $n$ phần tử. Phần tử ở vị trí $i$ chứa hai số nguyên: $v a l u e_{i}$ là giá trị lưu tại phần tử đó, và $n e x t_{i}$ là chỉ số của phần tử kế tiếp trong danh sách (hoặc $- 1$ nếu đây là phần tử cuối). Danh sách được sắp xếp tăng dần, tức là nếu $n e x t_{i} \neq - 1$ thì $v a l u e_{n e x t_{i}} > v a l u e_{i}$ .

Bạn được cho số phần tử $n$ , chỉ số của phần tử đầu tiên $s t a r t$ , và một số nguyên $x$ . Hãy tìm số nguyên nhỏ nhất trong danh sách mà lớn hơn hoặc bằng $x$ , hoặc kết luận rằng không tồn tại số như vậy.

Bạn được phép thực hiện tối đa $1999$ truy vấn dạng ? i (với $1 \leq i \leq n$ ): hệ thống trả về hai số $v a l u e_{i}$ và $n e x t_{i}$ .

Khi tìm được đáp án, in ra ! ans, trong đó $a n s$ là số nhỏ nhất trong danh sách lớn hơn hoặc bằng $x$ , hoặc ! -1 nếu không tồn tại. Sau lệnh này chương trình phải kết thúc.

Dữ liệu vào

Ban đầu bạn đọc một dòng gồm ba số nguyên $n$ , $s t a r t$ , $x$ — số phần tử của danh sách, chỉ số phần tử đầu tiên và số nguyên $x$ .

Sau mỗi truy vấn ? i, bạn đọc hai số nguyên $v a l u e_{i}$ và $n e x t_{i}$ .

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng dạng ? i. Khi kết thúc, in ra ! ans.

Quan trọng: Sau mỗi lần in phải flush output:

C++: cout << endl; hoặc cout.flush();
Python: print(..., flush=True)

Ràng buộc

$1 \leq n \leq 50000$
$1 \leq s t a r t \leq n$
$0 \leq x \leq 10^{9}$
$0 \leq v a l u e_{i} \leq 10^{9}$
Số truy vấn dạng ? không vượt quá $1999$ .

Ví dụ

Chương trình	Hệ thống	Giải thích
	5 3 80	$n = 5$ , $s t a r t = 3$ , $x = 80$ . Danh sách (theo thứ tự): $16, 58, 79, 81, 97$ .
? 3		Hỏi phần tử $3$ .
	16 2	$v a l u e_{3} = 16$ , $n e x t_{3} = 2$ .
? 2		Hỏi phần tử $2$ .
	58 5	$v a l u e_{2} = 58$ , $n e x t_{2} = 5$ .
? 5		$v a l u e_{5} = 79$ , $n e x t_{5} = 4$ .
? 4		$v a l u e_{4} = 81 \geq 80$ — dừng lại.
! 81		Số nhỏ nhất $\geq 80$ là $81$ .

Chương trình	Hệ thống	Giải thích
	5 1 6	Danh sách $1, 2, 3, 4, 5$ , $x = 6$ .
? 1		Duyệt tới cuối danh sách vẫn không có giá trị $\geq 6$ .
! -1		Không tồn tại số $\geq 6$ .

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

Giới hạn thời gian 1.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig