trang chủ / đề bài / icpc24_reg_d

Hoán vị đặc biệt

Đề bài

Mô tả

Một mảng A độ dài n được gọi là một hoán vị nếu nó gồm n số nguyên phân biệt từ 1 đến n theo thứ tự bất kỳ. Ví dụ, [2,3,1,5,4] là một hoán vị, nhưng [1,2,2] không phải hoán vị (số 2 xuất hiện hai lần), và [1,3,4] cũng không phải hoán vị (n=3 nhưng mảng có số 4).

Với một hoán vị P, định nghĩa F(P) là số mảng con liên tiếp của P là hoán vị. Ví dụ, với P=(5,3,1,4,2), các mảng con liên tiếp là hoán vị gồm:

  1. (1),
  2. (3,1,4,2),
  3. (5,3,1,4,2).

Do đó F(P)=3.

Một hoán vị P độ dài n được gọi là đặc biệt nếu F(P) lớn nhất trong số mọi hoán vị độ dài n.

Cho n và k. Xét tất cả các hoán vị đặc biệt độ dài n, hãy tìm hoán vị nhỏ thứ k theo thứ tự từ điển.

Hoán vị a nhỏ hơn hoán vị b (cùng độ dài) theo thứ tự từ điển khi và chỉ khi ở vị trí đầu tiên mà a và b khác nhau, phần tử của a nhỏ hơn phần tử tương ứng của b.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤105): số bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên n và k (1≤n≤105, 1≤k≤1018).

Dữ liệu đảm bảo:

  • k không vượt quá số hoán vị đặc biệt độ dài n;
  • tổng n trên tất cả các bộ test không vượt quá 105.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng gồm n số nguyên: hoán vị đặc biệt nhỏ thứ k theo thứ tự từ điển.

Ràng buộc

  • 1≤t≤105
  • 1≤n≤105, 1≤k≤1018
  • k không vượt quá số hoán vị đặc biệt độ dài n.
  • Tổng n không vượt quá 105.

Ví dụ

Input Output Giải thích
1
4 2
2 1 3 4 Với n=4, các hoán vị nhỏ nhất theo thứ tự từ điển là (1,2,3,4) với F=4; (1,2,4,3) và (1,3,2,4) với F=3; (1,3,4,2), (1,4,2,3), (1,4,3,2) với F=2; rồi (2,1,3,4) với F=4. Giá trị lớn nhất của F là 4, nên hoán vị đặc biệt thứ hai là (2,1,3,4).
3
4 1
4 8
1 1
1 2 3 4
4 3 2 1
1
Với n=4, hoán vị đặc biệt nhỏ nhất là (1,2,3,4) và lớn nhất là (4,3,2,1).

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