trang chủ / đề bài / icpcwf14_a

Hành lý

Đề bài

Mô tả

Một hãng hàng không có hai chuyến bay cất cánh gần như cùng lúc từ ICPCity, một chuyến tới thành phố B và một chuyến tới thành phố A. Hãng có n quầy để hành khách gửi hành lý. Ở mỗi quầy có một cặp thùng hành lý giống hệt nhau, một thùng cho thành phố B và một thùng cho thành phố A.

Ngay trước khi các chuyến bay khởi hành, từng cặp thùng hành lý được một xe đẩy có động cơ chở tới khu vực phân loại. Xe luôn chở hai thùng một lúc, một thùng cho thành phố B và một thùng cho thành phố A. Sau khi chở hết, các thùng xếp thành một hàng trong khu phân loại như sau:

B A B A B A…B A

Tức là có 2n thùng hành lý thành một hàng, bắt đầu bằng một thùng cho thành phố B, rồi một thùng cho thành phố A, và cứ thế tiếp tục. Nhiệm vụ bây giờ là sắp xếp lại để mọi thùng cho thành phố A đứng trước mọi thùng cho thành phố B. Khi đó các thùng có thể được chất lên đúng máy bay.

Việc sắp xếp lại được thực hiện bằng cách di chuyển các cặp thùng kề nhau (không nhất thiết là B rồi A), cũng bằng xe đẩy có động cơ. Để giữ thăng bằng, xe luôn phải chở hai thùng, không bao giờ chỉ chở một thùng. Một cặp thùng luôn phải được chuyển tới một khoảng trống rộng ít nhất hai thùng. Bên trái thùng đầu tiên có một số chỗ trống có thể dùng khi cần trong quá trình sắp xếp.

Khi bắt đầu sắp xếp, các vị trí đặt thùng được đánh số từ 1 (ban đầu chứa thùng B ngoài cùng bên trái) tới 2n (ban đầu chứa thùng A ngoài cùng bên phải). Bên trái các thùng có 2n chỗ trống, đánh số từ 0 tới −2n+1. Hình dưới đây là cấu hình ban đầu với n=4 (số ghi phía trên mỗi ô là số hiệu vị trí, ô . là chỗ trống):

array noindex
. . . . . . . . B A B A B A B A
label 1 -7
label 2 -6
label 3 -5
label 4 -4
label 5 -3
label 6 -2
label 7 -1
label 8 0
label 9 1
label 10 2
label 11 3
label 12 4
label 13 5
label 14 6
label 15 7
label 16 8
highlight gray 1..8

Cho n, hãy tìm một dãy thao tác di chuyển ngắn nhất để sắp xếp lại các thùng sao cho mọi thùng A nằm bên trái mọi thùng B. Khi kết thúc, thùng A ngoài cùng bên trái có thể nằm ở vị trí khác 1, nhưng các thùng phải nằm liền nhau trên một đoạn 2n vị trí liên tiếp.

Dữ liệu vào

Gồm một số nguyên n.

Dữ liệu ra

In ra một dãy thao tác ngắn nhất sắp xếp lại đúng các thùng. Mỗi thao tác in trên một dòng dạng f to t, trong đó f và t là các số nguyên, nghĩa là chuyển hai thùng ở vị trí f và f+1 tới vị trí t và t+1. Hai vị trí f, f+1 phải đang có thùng, hai vị trí t, t+1 phải đang trống, và mọi vị trí phải nằm trong đoạn từ −2n+1 tới 2n. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 3≤n≤100.

Ví dụ

Input Output Giải thích
5 8 to -1
3 to 8
6 to 3
0 to 6
9 to 0
Hàng ban đầu ở vị trí 1..10 là BABABABABA. Sau năm thao tác các thùng ở vị trí −1..8 là AAAAABBBBB. Có nhiều đáp án đúng khác.
8 10 to -1
3 to 10
14 to 3
7 to 14
0 to 7
11 to 0
4 to 11
15 to 4
Tám thao tác, kết quả là AAAAAAAABBBBBBBB ở vị trí −1..14.

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