Xáo Bài Bessie

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có một bộ bài $N$ lá được đánh số $1$ đến $N$ theo thứ tự từ trên xuống dưới. Cho một hoán vị $P$ gồm $M$ phần tử mô tả thao tác xáo bài: lá bài ở vị trí $i$ trong nhóm $M$ lá trên cùng sẽ chuyển sang vị trí $P [i]$ .

Thực hiện thao tác sau lặp đi lặp lại cho đến khi bộ bài còn ít hơn $M$ lá:

Xáo $M$ lá trên cùng theo hoán vị $P$ .
Lấy lá bài trên cùng ra và úp xuống (xây một chồng bài mặt-xuống).

Sau đó, các lá bài còn lại trong bộ bài được úp xuống từng lá một (từ trên xuống).

Chồng bài mặt-xuống sau khi hoàn thành: vị trí $1$ là lá trên cùng (lá úp xuống cuối cùng), vị trí $N$ là lá dưới cùng (lá úp xuống đầu tiên).

Cho $Q$ truy vấn, mỗi truy vấn hỏi lá bài ở vị trí $q_{i}$ trong chồng bài cuối cùng.

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $M$ , $Q$ .
$M$ dòng tiếp theo: Số nguyên $P [i]$ — mỗi dòng một giá trị.
$Q$ dòng tiếp theo: Số nguyên $q_{i}$ — vị trí truy vấn.

Dữ liệu ra

$Q$ dòng, mỗi dòng là nhãn của lá bài tại vị trí $q_{i}$ trong chồng bài cuối cùng.

Ràng buộc

$2 \leq M \leq 100 000$
$M \leq N \leq 100 000$
$1 \leq Q \leq 5 000$
$1 \leq P [i] \leq M$ (hoán vị hợp lệ)
$1 \leq q_{i} \leq N$

Ví dụ

Input	Output	Giải thích
5 3 5 3 1 2 1 2 3 4 5	4 5 3 1 2	Bộ bài ban đầu: [1,2,3,4,5]. Xáo lần 1: [1,2,3] → [2,3,1], lấy lá 2. Xáo lần 2: [3,1,4] → [1,4,3], lấy lá 1. Xáo lần 3: [4,3,5] → [3,5,4], lấy lá 3. Còn lại [5,4] úp xuống. Chồng cuối (trên→dưới): [4,5,3,1,2].

Ghi chú

Số lần xáo bài là $R = N - M + 1$ , sau đó còn lại $M - 1$ lá được úp xuống.
Vị trí $1$ đến $M - 1$ tương ứng với $M - 1$ lá cuối úp xuống (theo thứ tự ngược).
Vị trí $M$ đến $N$ là các lá bị lấy ra trong các lần xáo (theo thứ tự từ gần nhất đến xa nhất).

Bình luận

Không có bình luận tại thời điểm này.