Tập hợp xấu xa
Đề bài
Mô tả
Cho một tập hợp gồm số nguyên không âm phân biệt. Ta định nghĩa của một tập hợp là số nguyên không âm nhỏ nhất không xuất hiện trong tập hợp đó. Ví dụ, và .
Trong mỗi thao tác, bạn có thể thêm một số nguyên không âm bất kỳ vào tập hợp (nếu nó chưa có), hoặc xoá một phần tử đang có khỏi tập hợp.
Hãy tìm số thao tác ít nhất cần thực hiện để tập hợp có đúng bằng .
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và — kích thước tập hợp và giá trị mong muốn.
- Dòng thứ hai chứa số nguyên không âm phân biệt, mỗi số không vượt quá , mô tả tập hợp.
Dữ liệu ra
- In ra một số nguyên duy nhất — số thao tác ít nhất cần thực hiện.
Ràng buộc
- Các phần tử của tập hợp phân biệt và không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 0 4 5 6 7 |
2 | Cần có đủ nhưng đang thiếu và ; giá trị chưa có nên không cần xoá. Thêm và là đủ, tốn thao tác. |
| 1 0 0 |
1 | Muốn thì phải không có trong tập. Xoá , tốn thao tác. |
| 5 0 1 2 3 4 5 |
0 | vốn đã không có trong tập nên đã bằng , không cần thao tác nào. |
Bình luận