trang chủ / đề bài / icpc19_reg_k

Giữ cho có thứ tự

Đề bài

Mô tả

Gon có một hoán vị a=(a1,a2,…,an) của các số nguyên từ 1 đến n và muốn sắp xếp nó tăng dần. Tuy nhiên, sắp xếp thì quá dễ, ai cũng làm được!

Vì vậy, Gon quyết định chỉ dùng thao tác sau để sắp xếp:

  • Chọn hai chỉ số ℓ và r (1≤ℓ≤r≤n) sao cho đoạn con (aℓ,aℓ+1,…,ar) đã được sắp xếp, theo thứ tự tăng dần hoặc giảm dần.
  • Đảo ngược đoạn con từ ℓ đến r.

Ví dụ, với hoán vị a=(3,2,1), Gon có thể sắp xếp bằng 1 thao tác: chọn ℓ=1, r=3 và đảo ngược đoạn (a1,a2,a3) để được a=(1,2,3).

Lưu ý nếu a=(3,1,2) thì Gon không thể chọn ℓ=1, r=3, vì đoạn con từ 1 đến 3 chưa được sắp xếp.

Vì sinh nhật của Gon là ngày 19 tháng 1, Gon muốn dùng không quá 191 thao tác. Việc này hóa ra không hề đơn giản. Hãy giúp Gon!

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (1≤n≤100).

Dòng thứ hai chứa n số nguyên a1,a2,…,an. Dữ liệu đảm bảo a là một hoán vị của các số nguyên từ 1 đến n.

Dữ liệu ra

Dòng đầu tiên in ra một số nguyên k (0≤k≤191) là số thao tác bạn dùng.

Mỗi dòng trong k dòng tiếp theo in ra hai số nguyên ℓ và r (1≤ℓ≤r≤n) mô tả một thao tác. Đoạn con từ ℓ đến r phải đã được sắp xếp (tăng dần hoặc giảm dần) ngay trước thao tác đó.

Sau k thao tác, hoán vị phải được sắp xếp tăng dần, tức là ai=i với mọi i. Bạn không cần tối thiểu hóa số thao tác.

Dữ liệu đảm bảo luôn tồn tại lời giải. Nếu có nhiều lời giải, in ra một lời giải bất kỳ.

Ràng buộc

  • 1≤n≤100.
  • a là một hoán vị của 1,2,…,n.
  • Số thao tác không vượt quá 191.

Ví dụ

Input Output Giải thích
3
3 1 2
7
1 1
2 2
3 3
1 2
2 3
1 3
1 3
Đây là đáp án mẫu của đề gốc. Ba thao tác đầu đảo đoạn một phần tử (không đổi gì). Đảo đoạn (3,1) được (1,3,2); đảo đoạn (3,2) được (1,2,3); đoạn (1,2,3) tăng dần nên đảo được (3,2,1), rồi đảo lần nữa được (1,2,3). Cũng có thể chỉ dùng 2 thao tác: đảo đoạn [1,2] rồi đảo đoạn [2,3].
3
3 2 1
1
1 3
Ví dụ bổ sung (không có trong đề gốc). Cả hoán vị đang giảm dần nên đảo một lần là xong.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0