Xáo Bài Của 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 gồm $N$ lá, đánh số từ $1$ đến $N$ từ trên xuống. Một phép xáo bài được định nghĩa trên $M$ lá đầu: sau khi xáo, lá thứ $i$ trong $M$ lá đầu sẽ chuyển đến vị trí $P [i]$ (trong $M$ lá đầu đó).

Quá trình thực hiện như sau: lặp lại cho đến khi bộ bài còn ít hơn $M$ lá:

Xáo $M$ lá đầu theo hoán vị $P$ .
Rút lá trên cùng ra, đặt úp (face-down) lên bàn thành một chồng.

Khi bộ bài còn ít hơn $M$ lá, rút từng lá từ trên xuống (không xáo), đặt úp lên chồng bài đó cho đến hết.

Sau khi xong, chồng bài úp trên bàn có $N$ lá. Lá trên cùng chồng là lá được đặt xuống cuối cùng (vị trí 1), lá dưới cùng là lá đặt đầu tiên (vị trí $N$ ).

Cho $Q$ truy vấn, mỗi truy vấn hỏi: lá ở vị trí $q$ trong chồng bài (từ trên xuống, vị trí 1 = trên cùng) có số hiệu là bao nhiêu?

Dữ liệu vào

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

Dữ liệu ra

$Q$ dòng, mỗi dòng là số hiệu lá bài tại vị trí $q_{i}$ trong danh sách rút.

Ràng buộc

$2 \leq M \leq 100000$
$M \leq N \leq 10^{9}$
$1 \leq Q \leq 5000$
$1 \leq q_{i} \leq N$
50% test có $N \leq 100000$

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]. P=[3,1,2], nghĩa là lá ở vị trí 1→3, 2→1, 3→2. Xáo [1,2,3]: vị trí 1 lấy lá từ vị trí 2 (P[2]=1) → [2,3,1,4,5], rút lá 2. Tiếp theo: xáo [3,1,4]→[1,4,3,5], rút lá 1. Tiếp: xáo [4,3,5]→[3,5,4], rút lá 3. Còn 2 lá [5,4]: rút 5 rồi 4. Thứ tự rút: 2,1,3,5,4. Chồng bài (trên cùng = rút cuối): vị trí 1=4, 2=5, 3=3, 4=1, 5=2.

Bình luận

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