Nhảy cóc trong mảng
Đề bài
Mô tả
Xét một mảng gồm ô, đánh số từ đến . Ban đầu, với mỗi từ đến , số được đặt tại ô có chỉ số ; tất cả các ô còn lại đều rỗng.
Ở mỗi bước, ta chọn ô không rỗng có chỉ số lớn nhất và chuyển số đang nằm trong ô đó sang ô rỗng gần nhất về phía bên trái của nó. Quá trình lặp lại cho đến khi cả số cùng nằm trong ô đầu tiên của mảng.
Cho truy vấn, mỗi truy vấn gồm một chỉ số . Với mỗi truy vấn, hãy cho biết số nào nằm ở ô sau khi quá trình kết thúc.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : số lượng phần tử và số truy vấn.
- dòng tiếp theo, mỗi dòng chứa một số nguyên : chỉ số của ô cần biết giá trị.
Dữ liệu ra
In ra dòng, dòng thứ là số nằm ở ô sau khi quá trình kết thúc.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 2 3 4 |
3 2 4 |
Mảng ô ban đầu chứa . Số ở ô chuyển sang ô , rồi từ ô chuyển tiếp sang ô . Khi đó ô không rỗng có chỉ số lớn nhất là ô chứa số , số này chuyển sang ô . Mảng cuối cùng là . |
| 13 4 10 5 4 8 |
13 3 8 9 |
Mảng cuối cùng là . |
| 3 3 3 2 1 |
2 3 1 |
Số ở ô chuyển sang ô , rồi từ ô chuyển sang ô . Mảng cuối cùng là . |
Bình luận