trang chủ / đề bài / mergecalls

Số lần gọi sắp xếp trộn

Đề bài

Mô tả

Xét hàm sắp xếp trộn sau, dùng để sắp xếp đoạn [l,r) (gồm các chỉ số l,l+1,…,r−1) của mảng a đánh số từ 0:

  1. Nếu đoạn [l,r) đã được sắp xếp không giảm (tức là a[i]≤a[i+1] với mọi l≤i<r−1) thì kết thúc lời gọi hàm.
  2. Đặt mid=⌊l+r2⌋.
  3. Gọi mergesort(a,l,mid).
  4. Gọi mergesort(a,mid,r).
  5. Trộn hai đoạn [l,mid) và [mid,r) để đoạn [l,r) trở thành không giảm. Bước trộn không gọi thêm hàm nào.

Để sắp xếp cả mảng, ta gọi mergesort(a,0,n). Mỗi lần hàm mergesort được gọi (kể cả lời gọi đầu tiên) tính là một lần gọi. Ví dụ, với a={1,2,3,4} chỉ có 1 lần gọi, vì đoạn [0,4) đã được sắp xếp. Với a={2,1,3} có 3 lần gọi: mergesort(0,3) chia thành mergesort(0,1) và mergesort(1,3), hai lời gọi này kết thúc ngay vì đoạn tương ứng đã được sắp xếp.

Cho n và k, hãy tìm một hoán vị a của các số 1,2,…,n sao cho khi sắp xếp a bằng hàm trên thì số lần gọi mergesort đúng bằng k.

Dữ liệu vào

Một dòng gồm hai số nguyên n và k.

Dữ liệu ra

Nếu không tồn tại hoán vị thỏa mãn, in ra −1. Ngược lại, in ra n số nguyên a[0],a[1],…,a[n−1] là hoán vị tìm được. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤n≤105
  • 1≤k≤2·105

Ví dụ

Input Output Giải thích
3 3 2 1 3 Đây chính là ví dụ a={2,1,3} ở trên, có 3 lần gọi. Đáp án khác, ví dụ 1 3 2, cũng được chấp nhận.
4 1 1 2 3 4 Mảng đã được sắp xếp nên chỉ có lời gọi đầu tiên.
5 6 -1 Không có hoán vị nào của 5 phần tử cho đúng 6 lần gọi.

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