Sắp Xếp Nghịch Thế

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có một hoán vị ẩn $a_{1}, a_{2}, \dots, a_{n}$ của các số nguyên từ $1$ đến $n$ . Nhiệm vụ của bạn là sắp xếp hoán vị bằng cách đảo ngược các đoạn con. Sau mỗi thao tác đảo ngược, hệ thống sẽ cho biết số nghịch thế hiện tại.

Giao thức tương tác

Đây là bài toán tương tác. Chương trình của bạn giao tiếp với hệ thống đánh giá thông qua đầu vào/ra chuẩn.

Đầu tiên, chương trình đọc số nguyên $n$ .

Mỗi bước, bạn thực hiện thao tác:

In hai số nguyên $i$ $j$ ( $1 \leq i \leq j \leq n$ ): Đảo ngược đoạn con $a_{i}, a_{i + 1}, \dots, a_{j}$ . Hệ thống trả về số nghịch thế của hoán vị sau khi đảo.

Chương trình kết thúc khi số nghịch thế trả về bằng $0$ (hoán vị đã sắp xếp).

Bạn được phép thực hiện tối đa $4 n$ thao tác.

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

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

Ràng buộc

$1 \leq n \leq 1000$
Số thao tác tối đa: $4 n$

Ví dụ

Chương trình	Hệ thống	Giải thích
	3	$n = 3$ . Hoán vị ẩn: $[3, 1, 2]$
1 2	1	Đảo $[1, 2]$ : $[1, 3, 2]$ . Nghịch thế: 1
2 3	0	Đảo $[2, 3]$ : $[1, 2, 3]$ . Nghịch thế: 0. Xong!

Bình luận

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