Nhóm Bạn Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.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

Farmer John có $N$ con bò xếp thành hàng, mỗi con có nhãn từ $1$ đến $N$ . Một nhóm bạn gồm các con bò có nhãn giống nhau sao cho mỗi con bò cách tất cả con bò khác trong nhóm không quá $x$ vị trí. Mỗi con bò phải thuộc đúng một nhóm bạn. Với mỗi giá trị $x$ từ $1$ đến $N$ , xác định số nhóm bạn tối thiểu cần thiết.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ).
Dòng thứ hai: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq N$ ) - nhãn các con bò.

Dữ liệu ra

$N$ dòng, dòng thứ $i$ chứa số nhóm bạn tối thiểu khi $x = i$ .

Ràng buộc

Test $2$ - $3$ : $N \leq 5000$
Test $4$ - $7$ : Tất cả $a_{i} \leq 10$
Test $8$ - $11$ : Không nhãn nào xuất hiện quá $10$ lần
Test $12$ - $20$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
9 1 1 1 9 2 1 2 1 1	7 5 4 4 4 4 4 3 3	Với $x = 1$ : cần 7 nhóm. Với $x = 8$ hoặc $x = 9$ : tất cả bò cùng nhãn có thể gộp lại, chỉ cần 3 nhóm.

Bình luận

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