Elearning CodePath – CTP Online Judge

Đếm Số Lượng Giá Trị Tần Suất Cao

DISTINCT_VALUES

🟢 Easy #General #Hash

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy gồm $N$ số nguyên dương $A = (a_1, a_2, \dots, a_n)$ và một số nguyên dương $M$.

Yêu cầu: Đếm số lượng **phần tử có giá trị khác nhau** (distinct values) xuất hiện ít nhất $M$ lần trong dãy $A$.

Đặt $Count(x)$ là số lần giá trị $x$ xuất hiện trong dãy $A$.
Ta cần tìm:
$$
\text{Số lượng giá trị khác nhau } x \text{ sao cho } Count(x) \ge M
$$

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `BAI1.INP`:

* Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$.
* Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, \dots, a_n$.

Giới hạn: $1 \le N \le 2 \times 10^5$, $1 \le M \le N$, $1 \le a_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `BAI1.OUT` một dòng duy nhất chứa số lượng giá trị xuất hiện ít nhất $M$ lần. Nếu không có giá trị nào thỏa mãn, kết quả là $0$.

---
### ✨ Ví dụ

| Input (`BAI1.INP`) | Output (`BAI1.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `10 2` <br> `1 3 1 5 2 3 3 2 2 4` | `3` | Tần suất: $Count(1)=2, Count(3)=3, Count(2)=3, Count(5)=1, Count(4)=1$. <br> Các giá trị có $Count(x) \ge M=2$ là $1, 2, 3$. $\Rightarrow 3$ giá trị khác nhau. |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $30\%$ | 
| 2 | $N \le 2 \times 10^5$ | $70\%$ |

---

✅ Đã AC: 7 / 8 submissions