Trò chơi miễn phí

Điểm: 5,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

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Một vách đá cao $h$ đơn vị. Trên mỗi độ cao $x$ từ $1$ tới $h$ có đúng một bục di động, đang ở trạng thái ẩn (ở bên trong vách) hoặc đẩy ra (nhô ra ngoài). Ban đầu có $n$ bục đang đẩy ra ở các độ cao $p_{1}, p_{2}, \dots, p_{n}$ (với $h = p_{1} > p_{2} > \dots > p_{n} \geq 1$ ). Nhân vật đang đứng trên bục ở độ cao $h$ .

Nếu nhân vật đang đứng ở độ cao $x$ (bục $x$ đang đẩy ra), nó có thể kéo cần gạt: bục $x$ sẽ chuyển sang trạng thái ẩn, đồng thời bục ở độ cao $x - 1$ đảo trạng thái (đẩy ra $\to$ ẩn hoặc ẩn $\to$ đẩy ra). Đây là cách duy nhất để di chuyển giữa các bục.

Nhân vật rất mỏng manh: nó chỉ sống sót khi rơi tối đa $2$ đơn vị. Tức là rơi từ $x$ xuống bục $x - 1$ hoặc $x - 2$ là an toàn, còn rơi tới $x - 3$ trở xuống (mà chưa được bục nào đỡ) là chết.

Nhân vật có thể mua các viên pha lê ma thuật. Mỗi viên cho phép đảo trạng thái của một bục bất kỳ, trừ bục ở độ cao $h$ . Mỗi viên chỉ dùng được một lần.

Hỏi số viên pha lê tối thiểu cần mua để nhân vật đáp xuống mặt đất (độ cao $0$ ) an toàn.

Dữ liệu vào

Dòng đầu chứa số nguyên $q$ — số truy vấn.
Mỗi truy vấn gồm hai dòng:
- Dòng thứ nhất chứa hai số nguyên $h$ và $n$ .
- Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ theo thứ tự giảm dần.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên — số viên pha lê tối thiểu cần dùng.

Ràng buộc

$1 \leq q \leq 100$
$1 \leq h \leq 10^{9}$
$1 \leq n \leq min (h, 2 \cdot 10^{5})$
$h = p_{1} > p_{2} > \dots > p_{n} \geq 1$
Tổng $n$ trên tất cả các truy vấn không vượt quá $2 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
4 3 2 3 1 8 6 8 7 6 5 3 2 9 6 9 8 5 4 3 1 1 1 1	0 1 2 0	Truy vấn 1: kéo cần gạt ở $3$ — bục $3$ ẩn, bục $2$ chuyển từ ẩn thành đẩy ra. Rơi xuống và đáp ở $2$ . Từ $2$ kéo cần — bục $2$ ẩn, bục $1$ chuyển từ đẩy ra thành ẩn. Rơi xuống mặt đất an toàn (rơi $2$ đơn vị). Không cần pha lê. Truy vấn 4: từ độ cao $1$ kéo cần — bục $1$ ẩn, bục $0$ (mặt đất) coi như đẩy ra. Đáp xuống mặt đất an toàn.

Bình luận

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