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 (gồm các chỉ số ) của mảng đánh số từ :
- Nếu đoạn đã được sắp xếp không giảm (tức là với mọi ) thì kết thúc lời gọi hàm.
- Đặt .
- Gọi .
- Gọi .
- Trộn hai đoạn và để đoạn 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 . Mỗi lần hàm đượ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 chỉ có lần gọi, vì đoạn đã được sắp xếp. Với có lần gọi: chia thành và , hai lời gọi này kết thúc ngay vì đoạn tương ứng đã được sắp xếp.
Cho và , hãy tìm một hoán vị của các số sao cho khi sắp xếp bằng hàm trên thì số lần gọi đúng bằng .
Dữ liệu vào
Một dòng gồm hai số nguyên và .
Dữ liệu ra
Nếu không tồn tại hoán vị thỏa mãn, in ra . Ngược lại, in ra số nguyên 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
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 | 2 1 3 | Đây chính là ví dụ ở trên, có 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 phần tử cho đúng lần gọi. |
Bình luận