trang chủ / đề bài / icpc23_mn_e

Ánh xạ hoán vị

Đề bài

Mô tả

Trong một vũ trụ được nối với nhau bằng các đường hầm vũ trụ, hệ thống Ống Liên Sao Tương Lai (FIT) chào đón các nhà thám hiểm du hành giữa các hành tinh. Để lên đường, mỗi người phải giải các thử thách về hoán vị của các số nguyên dương.

Xét tập các hoán vị a1,a2,…,an,an+1,…,a2n của 2n số nguyên dương 1,2,…,2n có các tính chất sau:

  • Dãy a1,a2,…,an tăng dần.
  • Dãy an+1,…,a2n tăng dần.
  • Với mọi i (1≤i≤n): ai<an+i.

Tất cả các hoán vị này được sắp xếp theo thứ tự từ điển và đánh số liên tiếp bắt đầu từ 1. Như vậy mỗi hoán vị có một số thứ tự, gọi là chỉ số của hoán vị.

Ví dụ, với n=3 có tất cả 5 hoán vị, sau khi sắp xếp chúng được đánh số như sau:

Chỉ số Hoán vị
1 1 2 3 4 5 6
2 1 2 4 3 5 6
3 1 2 5 3 4 6
4 1 3 4 2 5 6
5 1 3 5 2 4 6

Cho số n, bạn cần giải hai bài toán sau:

  1. Cho chỉ số k, tìm hoán vị có chỉ số k.
  2. Cho hoán vị a1,a2,…,a2n, tìm chỉ số của hoán vị này.

Dữ liệu vào

Dữ liệu vào gồm không quá 2000 bộ test, mỗi bộ test nằm trên một dòng, bắt đầu bằng số 1 hoặc 2 cho biết bài toán cần giải:

  • Nếu số đầu tiên là 1, tiếp theo là hai số nguyên n và k.
  • Nếu số đầu tiên là 2, tiếp theo là số nguyên n và 2n số nguyên a1,a2,…,a2n.

Dữ liệu vào đảm bảo đúng và lời giải luôn tồn tại: k không vượt quá số hoán vị có tính chất trên, và hoán vị cho trong bài toán 2 có đủ các tính chất trên.

Dữ liệu ra

In ra kết quả của từng bộ test theo thứ tự trong dữ liệu vào, mỗi kết quả trên một dòng: với bài toán 1 in ra 2n số của hoán vị, với bài toán 2 in ra chỉ số của hoán vị. Lưu ý chỉ số có thể rất lớn và phải được in ra chính xác.

Ràng buộc

  • Không quá 2000 bộ test.
  • 1≤n≤1000.
  • 1≤k≤109.

Ví dụ

Input Output Giải thích
1 3 4
2 3 1 3 5 2 4 6
1 4 2
2 4 1 2 3 6 4 5 7 8
1 3 4 2 5 6
5
1 2 3 5 4 6 7 8
3
Hai bộ test đầu ứng với bảng n=3 ở trên. Với n=4, ba hoán vị đầu tiên là 1 2 3 4 5 6 7 8, 1 2 3 5 4 6 7 8 và 1 2 3 6 4 5 7 8.
1 1 1
2 1 1 2
1 2
1
Với n=1 chỉ có một hoán vị là 1 2.

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