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

Nhỏ nhất và lớn nhất

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

Hệ thống giữ bí mật một mảng $a_{1}, a_{2}, \dots, a_{n}$ . Bạn chỉ biết độ dài $n$ của mảng, và cần tìm vị trí của một phần tử nhỏ nhất cùng vị trí của một phần tử lớn nhất.

Cách duy nhất để thu thập thông tin là so sánh hai phần tử qua chỉ số của chúng. Với truy vấn ? i j (với $1 \leq i, j \leq n$ ), hệ thống trả lời một ký tự:

< nếu $a_{i} < a_{j}$ ,
= nếu $a_{i} = a_{j}$ ,
> nếu $a_{i} > a_{j}$ .

Khi đã xác định được đáp án, in ra ! i j, trong đó $i$ là chỉ số của một phần tử nhỏ nhất và $j$ là chỉ số của một phần tử lớn nhất. Nếu có nhiều đáp án hợp lệ, in ra đáp án bất kỳ.

Với mảng độ dài $n$ , chương trình của bạn được phép dùng nhiều nhất $f (n) = ⌈ \frac{3 n}{2} ⌉ - 2$ truy vấn so sánh. Lệnh báo đáp án ! i j không được tính vào số này.

Mỗi test gồm nhiều mảng liên tiếp. Bạn phải giải xong mảng hiện tại (in lệnh !) rồi mới được chuyển sang mảng kế tiếp; giới hạn $f (n)$ được áp dụng riêng cho từng mảng.

Giao thức tương tác

Đầu tiên đọc số nguyên $T$ : số lượng mảng cần xử lý.
Với mỗi mảng: đọc số nguyên $n$ là độ dài mảng. Sau đó lặp lại việc in ? i j và đọc một ký tự trả lời, cho tới khi in ! i j để chốt đáp án.
Sau khi chốt đáp án của mảng cuối cùng, chương trình phải kết thúc.

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

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

Dữ liệu vào

Dòng đầu: số nguyên $T$ .
Với mỗi mảng, hệ thống gửi một dòng chứa số nguyên $n$ , tiếp theo là các ký tự trả lời cho từng truy vấn của bạn.

Dữ liệu ra

Với mỗi mảng, in các truy vấn ? i j và kết thúc bằng ! i j.

Ràng buộc

$1 \leq T \leq 1000$
$1 \leq n \leq 50$
$1 \leq a_{i} \leq 10^{9}$
Số truy vấn cho mỗi mảng không vượt quá $⌈ 3 n / 2 ⌉ - 2$

Ví dụ

Ví dụ 1 ( $T = 2$ ): mảng ẩn thứ nhất là $(2, 1)$ , mảng ẩn thứ hai là $(1, 1, 1)$ .

Chương trình	Hệ thống	Giải thích
	2	Có $T = 2$ mảng.
	2	Mảng thứ nhất có $n = 2$ , được phép $⌈ 3 ⌉ - 2 = 1$ truy vấn.
? 1 2	>	$a_{1} > a_{2}$ .
! 2 1		Nhỏ nhất ở vị trí $2$ , lớn nhất ở vị trí $1$ .
	3	Mảng thứ hai có $n = 3$ , được phép $⌈ 4.5 ⌉ - 2 = 3$ truy vấn.
? 3 1	=	$a_{3} = a_{1}$ .
? 2 1	=	$a_{2} = a_{1}$ .
! 2 3		Mọi phần tử bằng nhau nên mọi cặp chỉ số đều là đáp án hợp lệ.

Ví dụ 2 ( $T = 1$ ): mảng ẩn là $(4, 7, 9)$ .

Chương trình	Hệ thống	Giải thích
	1	Có $T = 1$ mảng.
	3	$n = 3$ , được phép $3$ truy vấn.
? 1 2	<	$a_{1} < a_{2}$ .
? 2 3	<	$a_{2} < a_{3}$ .
? 1 3	<	$a_{1} < a_{3}$ .
! 1 3		Nhỏ nhất ở vị trí $1$ , lớn nhất ở vị trí $3$ .

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 6,00một phần

Giới hạn thời gian 4.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, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả