COLFLAG - Treo cờ
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Trong một hội nghị thuật toán thế giới, Ban tổ chức đã treo cờ dọc theo đường dẫn vào trung tâm hội nghị, có 𝑁 lá cờ được đánh số từ 1 đến 𝑁, lá cờ thứ i có màu là 𝐴𝑖 . Tuy nhiên, sau khi treo cờ lên, ngài Chủ tịch hội nghị nhận thấy dãy cờ có quá nhiều màu khác nhau là không hợp lí. Bộ phận phụ trách rà soát và cho biết còn dư 𝑀 lá cờ, được đánh số từ 1 đến 𝑀, lá cờ thứ 𝑗 có màu là 𝐵𝑗 nên họ quyết định sẽ thay thế một số lá cờ để được dãy cờ có ít màu nhất có thể. Lá cờ bị thay xuống hiển nhiên sẽ không được sử dụng trong các lần thay thế tiếp theo vì đã bị rách. Đồng thời lá cờ đã được gắn lên cũng không được phép gỡ xuống.

Yêu cầu: Hãy tìm cách thay một số (hoặc giữ nguyên) lá cờ đã treo bằng một số lá cờ trong số cờ còn dư sao cho tổng số màu xuất hiện trên dãy cờ chính thức là ít nhất.

Dữ liệu:

- Dòng đầu ghi số nguyên 𝑁 và 𝑀 là số cờ đã treo và số cờ còn dư;
- Dòng thứ 2 ghi 𝑁 số nguyên 𝐴𝑖 cho biết màu của các lá cờ đã treo (0 ≤ 𝐴𝑖 ≤ 255, 1 ≤ 𝑖 ≤ 𝑁); 
- Dòng thứ 3 ghi 𝑀 số nguyên 𝐵𝑖 cho biết màu của các lá cờ còn dư (0 ≤ 𝐵𝑗 ≤ 255, 1 ≤ 𝑗 ≤ 𝑀). Các số trên cùng dòng cách nhau bởi dấu cách.

Kết quả:

Ghi ra một dòng duy nhất ghi số nguyên 𝐾 là số màu còn lại của dãy cờ chính thức sau khi thực hiện thay thế. 

Ví dụ

Input

9 4
1 2 5 4 8 9 3 5 5
2 5 5 5

Output

3

Giải thích: Dãy cờ mới sẽ là: 1 2 5 5 2 5 5 5 5. Các số tô đậm mô tả các lá cờ được thay thế.

Giới hạn:

- Có 40% số test có 𝑁 ≤ 1000; 𝑀 = 1;
- Có 30% số test có 𝑁 ≤ 1000; 𝑀 ≤ 1000;
- Có 30% số test còn lại có 𝑁 ≤ 105 ; 𝑀 ≤ 105 


Nguồn: 3D '1819

Back to Top