Báo cáo lương theo phòng ban

Bối cảnh

Một công ty lưu nhân viên dưới dạng record Employee {id, department, salary}. Cuối tháng, hệ thống cần lập báo cáo theo phòng ban: tổng quỹ lương, số nhân viên và người có lương cao nhất trong từng phòng. Nếu hai người cùng lương cao nhất, chọn ID nhỏ hơn. Các phòng được in theo tên tăng dần.

Bài toán không khó ở cú pháp struct mà ở việc chuyển từ danh sách record sang thống kê theo nhóm. Mỗi Employee vẫn là một thực thể đầy đủ; map chỉ dùng để gom các aggregate theo department. Đây là bước nâng từ "duyệt record" sang "group-by record", rất gần các bài dữ liệu trong HSG/ICPC nhập môn.

Ngoài kết quả số học, bài còn kiểm tra việc mỗi thực thể được giữ dưới dạng một record nhất quán: các field phải luôn đi cùng nhau qua bước đọc, lọc, thống kê hoặc sắp xếp. Khi thiết kế lời giải, nên xác định rõ record gốc và record/aggregate suy ra để tránh dùng nhiều mảng song song làm lệch dữ liệu.

Yêu cầu

1. Dùng struct Employee.
2. Đọc n employee.
3. Với mỗi department, tính count, totalSalary, topEmployee.
4. Tie top salary bằng ID nhỏ hơn.
5. In department tăng dần: department count total topId topSalary.

Input

Dòng 1 n; n dòng id department salary.

Output

Mỗi department một dòng.

Ràng buộc

1≤n≤5000, salary không âm và tổng nằm trong long long.

Ví dụ 1

Input

6
E1 IT 100
E2 HR 80
E3 IT 120
E4 HR 80
E5 SALE 90
E0 IT 120

Output

HR 2 160 E2 80
IT 3 340 E0 120
SALE 1 90 E5 90

Giải thích

IT có E1=100, E3=120, E0=120 nên count=3, total=340. Top salary 120 hòa giữa E3 và E0, tie chọn ID nhỏ hơn E0. HR có count2 total160, top salary80 và tie giữa E2/E4 chọn E2. SALE có một người90. Department in tăng dần HR, IT, SALE.

Ví dụ này đồng thời kiểm tra rằng các field của cùng một record không bị lệch khi duyệt hoặc sắp xếp. Quy tắc tie-break/giữ thứ tự chỉ được áp dụng sau khi dữ liệu cần so sánh đã được xác định đúng, nên kết quả trên là hệ quả trực tiếp của state record sau xử lý.

Ví dụ 2

Input

3
A X 10
B X 10
C X 5

Output

X 3 25 A 10

Giải thích

Cả ba employee thuộc X nên count=3, total=25. Top salary10 hòa A và B; ID A nhỏ hơn nên top là A10. Output duy nhất X 3 25 A 10.

Ví dụ này đồng thời kiểm tra rằng các field của cùng một record không bị lệch khi duyệt hoặc sắp xếp. Quy tắc tie-break/giữ thứ tự chỉ được áp dụng sau khi dữ liệu cần so sánh đã được xác định đúng, nên kết quả trên là hệ quả trực tiếp của state record sau xử lý.

Thông tin học tập

• Module: M07
• Buổi: B23
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: struct, vector, map, sorting, aggregation, tie-break
• Giới hạn kiến thức: B01-B23
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100