Đề

Lớp bầu lớp trưởng, mỗi phiếu ghi một tên. Hãy kiểm phiếu: in mỗi người và số phiếu của người đó theo số phiếu giảm dần; những người cùng số phiếu thì in theo tên tăng dần.

Dữ liệu vào

• Dòng đầu chứa n là số phiếu.
• n dòng tiếp theo, mỗi dòng một tên trên phiếu.

Kết quả

Mỗi người được bầu một dòng: tên và số phiếu, cách nhau một dấu cách, theo thứ tự nói trên.

Ràng buộc

• ~1 \le n \le 10^5~.
• Tên là một từ dài 1–20 ký tự: chữ đầu là chữ in hoa, các chữ sau là chữ thường (Lan, Quan). Hai tên khác nhau là hai người khác nhau. Tên so sánh theo thứ tự chuỗi (A < An < Anh < B).

Ví dụ

Dữ liệu vào:

3
Lan
Quan
Quan

Kết quả:

Quan 2
Lan 1

Giải thích ví dụ

Đếm phiếu được {"Lan": 1, "Quan": 2}. Quan nhiều phiếu hơn nên in trước, dù Lan xuất hiện trước trong dữ liệu.

Một ví dụ khác về người hòa phiếu: với 4 phiếu Quan, Minh, Quan, Minh thì Minh và Quan cùng 2 phiếu, in Minh 2 rồi Quan 2 (tên tăng dần), không theo thứ tự xuất hiện.

Lưu ý

• Hàm khóa trả về tuple (-so, ten) rồi gọi sorted(so_phieu.items(), key=...) (mục 8.3). Nếu hàm khóa chỉ trả về số phiếu và dùng reverse=True, những người hòa phiếu sẽ giữ thứ tự nhập — sai khi dữ liệu đến theo thứ tự khác.
• Có thể có tới ~10^5~ người khác nhau: đếm bằng dict; gọi list.count() cho từng người sẽ quá chậm.

Nguồn: Bài C8-09, mục 8.9, giáo trình Lập trình cơ sở với Python — TS. Nguyễn Quốc Long.

Nguồn trong sách: bài tập C8-09 (mục 8.9) · Mức: (**)