Đề

Cho dãy ~n~ số nguyên và số nguyên ~k~. Hãy xoay dãy sang phải ~k~ bước và in kết quả. Mỗi bước xoay phải, phần tử cuối dãy chuyển lên đầu dãy, các phần tử còn lại lùi về sau một chỗ.

Chương trình phải chạy nhanh cả khi ~k~ rất lớn (tới ~10^9~) và dãy dài tới ~10^5~ phần tử.

Dữ liệu vào

• Dòng 1: hai số nguyên ~n~ và ~k~.
• Dòng 2: ~n~ số nguyên ~a_1, \ldots, a_n~, cách nhau một dấu cách.

Kết quả

Một dòng: dãy sau khi xoay phải ~k~ bước, các số cách nhau một dấu cách.

Ràng buộc

• ~1 \le n \le 10^5~; ~0 \le k \le 10^9~.
• ~-10^9 \le a_i \le 10^9~.

Ví dụ

Dữ liệu vào:

7 10
1 2 3 4 5 6 7

Kết quả:

5 6 7 1 2 3 4

Giải thích ví dụ

Xoay 7 bước thì dãy 7 phần tử trở lại như cũ, nên xoay 10 bước giống xoay ~10 \bmod 7 = 3~ bước:

Kết quả là 3 phần tử cuối 5 6 7 đưa lên trước 4 phần tử đầu 1 2 3 4: với ~r = k \bmod n~, đáp án là ds[n - r:] + ds[:n - r].

Lưu ý

• Xoay từng bước (ds.insert(0, ds.pop())) đúng nhưng quá chậm khi ~k~ lớn: ~k~ tới ~10^9~ bước. Bộ test có ~k = 10^9~ để bắt cách làm này (Time Limit). Đã lấy ~k \bmod n~ mà vẫn xoay từng bước thì mỗi insert(0, ...) phải dời cả dãy — với ~n = 10^5~ là khoảng ~10^{10}~ lần dời phần tử, rất sát giới hạn; đừng dựa vào may rủi, hãy dùng lát cắt.
• Nhớ lấy ~k \bmod n~ trước khi cắt lát; ~k = 0~ hoặc ~k~ là bội của ~n~ thì dãy không đổi.
• Xoay phải: phần tử cuối lên đầu. ds[k:] + ds[:k] là xoay trái.

Nguồn trong sách: Bài C6-15, mục 6.12, giáo trình Lập trình cơ sở với Python — TS. Nguyễn Quốc Long · Mức: (****)