Người Nhận Quà Tham Lam

Đ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ó $N$ người xếp hàng theo thứ tự từ 1 đến $N$ . Mỗi người $i$ có một số nguyên $d_{i}$ ( $0 \leq d_{i} < N$ ). Trò chơi diễn ra vô hạn như sau:

Người đứng đầu hàng tặng quà cho mọi người (tức là người đó nhận được lượt tặng quà) rồi bước ra khỏi đầu hàng và chen vào vị trí $d_{i} + 1$ tính từ đầu hàng (vượt qua $d_{i}$ người).
Quá trình lặp lại mãi mãi.

Hãy tính xem có bao nhiêu người không bao giờ đến được đầu hàng để tặng quà.

Dữ liệu vào

Dòng đầu tiên gồm một số nguyên $N$ .
Dòng thứ hai gồm $N$ số nguyên $d_{1}, d_{2}, \dots, d_{N}$ .

Dữ liệu ra

Một số nguyên duy nhất — số lượng người không bao giờ nhận được lượt tặng quà.

Ràng buộc

$1 \leq N \leq 10^{5}$
$0 \leq d_{i} < N$

Ví dụ

Input	Output	Giải thích
3 1 2 0	1	Ban đầu hàng: [1, 2, 3] với $d = [1, 2, 0]$ . Người 1 (d=1) nhận quà, chen vào sau 1 người → hàng: [2, 1, 3]. Người 2 (d=2) nhận quà, chen vào sau 2 người → hàng: [1, 3, 2]. Người 1 (d=1) nhận quà, chen vào sau 1 người → hàng: [3, 1, 2]. Người 3 (d=0) nhận quà... Nhưng thực ra người 3 có $d_{3} = 0$ , tức số nhảy $j_{3} = 3 - 0 = 3 > N - 1$ , nên người 3 luôn bị người 1 và 2 chen trước. Chỉ có người 3 không bao giờ đến được đầu hàng.
100 42 8 40 74 5 34 2 12 38 37 73 27 0 82 45 35 96 27 40 21 28 64 61 42 53 95 53 57 74 99 70 69 7 10 43 64 44 45 77 35 34 2 62 34 36 8 22 33 87 62 54 67 78 67 9 32 62 63 41 89 62 11 58 21 22 1 37 18 46 66 53 80 68 68 67 5 28 89 90 15 3 96 82 34 63 44 18 78 7 59 67 21 22 77 94 96 78 83 15 76	70	Trong 100 người, có 70 người không bao giờ nhận được lượt tặng quà.

Ghi chú

Khi một người chen hàng vào vị trí $d_{i} + 1$ , nếu $d_{i} = 0$ thì người đó đứng ở đầu hàng ngay (nhưng cũng được tính là vừa nhận quà xong nên vào cuối hàng sau). Những người có số nhảy $j_{i} = N - d_{i}$ nhỏ (tức chen vào gần đầu hàng) sẽ có lợi thế hơn và có xu hướng nhận quà liên tục, trong khi những người có $j_{i}$ lớn (chen vào gần cuối hàng) có thể không bao giờ lên được đầu hàng.

Bình luận

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