Trước thềm World Cup 2026, để tăng doanh số bán hàng, một hãng bánh quy triển khai chương trình khuyến mãi “Gom thẻ rinh quà” với thể lệ như sau: Trong mỗi hộp bánh có một thẻ chứa mã dự thưởng: hai thẻ có mã dự thưởng giống nhau sẽ đổi được một phần quà lưu niệm và mỗi thẻ dự thưởng chỉ được sử dụng một lần.
Mã dự thưởng là một chuỗi có độ dài khoảng 15 ký tự, gồm: các ký tự chữ cái in hoa trong bảng chữ cái tiếng Anh (A-Z) hoặc các ký tự chứ số (0-9) hoặc cả ký tự chữ cái và chữ số.
Ngay khi biết được chương trình khuyến mãi, Bo đã mua \(n\) hộp bánh, các hộp bánh được đánh số từ 1 đến \(n\). Hộp bánh thứ \(i\ (1 \leq i \leq n)\) có mã dự thưởng \(s_{i}\).
Yêu cầu: Cho \(n\) và dãy số \(s_{1},s_{2},\ldots,s_{n}\). Hãy đếm số quà nhiều nhất mà Bo có thể đổi được từ chương trình khuyến mãi trên.
Dữ liệu vào:
- Dòng 1 ghi số nguyên dương \(n\ (1 \leq n \leq 10^{5})\);
- \(n\) dòng tiếp theo, dòng thứ \(i\ (1 \leq i \leq n)\) ghi mã dự thưởng \(s_{i}\).
Kết quả: Ghi một số nguyên là số quà nhiều nhất mà Bo có thể đổi được.
Ràng buộc:
- Subtask 1 (10% số điểm): tất cả các mã dự thưởng giống nhau;
- Subtask 2 (10% số điểm): \(n \leq 10^{3}\);
- Subtask 3 (10% số điểm): mã dự thưởng có độ dài không quá 6 kí tự, gồm: các kí tự chữ số (0-9) và không bằng đầu bằng kí tự 0;
- Subtask 4 (70% số điểm): không có ràng buộc gì thêm.
Ví dụ:
| Input | Output | Input | Output | |
|---|---|---|---|---|
5 WORLD2026 D2026 WORLD2026 WORLD2026 D2026 |
2 | 5 29 05 2026 29 TS10 |
1 |
Đang kiểm tra gợi ý...