Trung vị
Đề bài
Mô tả
Thầy Phương đang tổ chức một học phần "Lập trình thi đấu" đặc biệt để chuẩn bị cho học sinh của mình tham dự kỳ thi ICPC sắp tới.
Tại mọi thời điểm, thầy Phương muốn tính trung vị năng lực của cả lớp để có thể chọn một bộ đề phù hợp với năng lực của học sinh.
Lớp có học sinh, đánh số từ đến , với năng lực được sắp xếp theo thứ tự không giảm.
- Nếu lẻ, trung vị bằng (phép chia lấy phần nguyên).
- Nếu chẵn, trung vị bằng .
Có sự kiện, mỗi sự kiện thuộc một trong loại:
- IN : một học sinh có năng lực vào lớp;
- OUT : một học sinh có năng lực rời lớp;
- MEDIAN: thầy Phương muốn biết giá trị trung vị hiện tại.
Hãy giúp thầy Phương trả lời các câu hỏi.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên là số sự kiện.
dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng ở trên.
Ban đầu lớp không có học sinh nào. Khi có sự kiện OUT , đảm bảo trong lớp đang có ít nhất một học sinh năng lực (đã vào bằng một sự kiện IN trước đó và chưa rời đi); sự kiện này chỉ làm đúng một học sinh như vậy rời lớp. Nhiều học sinh có thể có cùng năng lực.
Dữ liệu ra
Với mỗi sự kiện MEDIAN, in ra trên một dòng giá trị trung vị tại thời điểm đó. Trung vị luôn là số nguyên hoặc số nguyên cộng : in số nguyên ở dạng thông thường, còn trường hợp sau in phần nguyên, tiếp theo là ".5" (dấu chấm thập phân), ví dụ 1.5.
Ràng buộc
- .
- .
- Khi có sự kiện MEDIAN, lớp có ít nhất một học sinh; có ít nhất một sự kiện MEDIAN.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 22 IN 1 MEDIAN IN 2 MEDIAN IN 3 MEDIAN IN 4 MEDIAN IN 5 MEDIAN OUT 1 MEDIAN IN 6 MEDIAN OUT 2 MEDIAN IN 7 MEDIAN OUT 5 MEDIAN IN 8 MEDIAN |
1 1.5 2 2.5 3 3.5 4 4.5 5 5 6 |
Ví dụ, sau OUT 1 lớp gồm nên trung vị là . |
| 10 IN 5 IN 5 IN 1 MEDIAN OUT 5 MEDIAN IN 1000000000 MEDIAN OUT 1 MEDIAN |
5 3 5 500000002.5 |
OUT 5 chỉ làm một trong hai học sinh năng lực rời lớp, lớp còn . Cuối cùng lớp gồm và . |
Bình luận