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

Sắp Xếp Nghịch Thế

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

maytinhoc3

đã bình luận 3 weeks trước

Heiio

Nộp bài giải

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

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

Giới hạn thời gian 2.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

Đề bài

Mô tả

Giao thức tương tác

Ràng buộc

Ví dụ

Bình luận