Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Bài toán gốc trên LeetCode (thiết kế lớp) được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout).

Một hệ thống tàu điện ngầm đang theo dõi thời gian di chuyển của khách hàng giữa các ga khác nhau. Họ dùng dữ liệu này để tính thời gian trung bình để đi từ một ga tới một ga khác.

Hãy cài đặt lớp UndergroundSystem:

• void checkIn(int id, string stationName, int t)
  • Một khách hàng có mã thẻ là id quẹt thẻ vào (check in) tại ga stationName ở thời điểm t.
  • Tại mỗi thời điểm, một khách hàng chỉ có thể đang check in ở một nơi.
• void checkOut(int id, string stationName, int t)
  • Một khách hàng có mã thẻ là id quẹt thẻ ra (check out) tại ga stationName ở thời điểm t.
• double getAverageTime(string startStation, string endStation)
  • Trả về thời gian trung bình để đi từ ga startStation tới ga endStation.
  • Thời gian trung bình được tính từ tất cả các lần di chuyển trước đó từ startStation tới endStation diễn ra trực tiếp, nghĩa là check in tại startStation rồi check out tại endStation.
  • Thời gian đi từ startStation tới endStation có thể khác thời gian đi từ endStation tới startStation.
  • Đảm bảo đã có ít nhất một khách hàng đi từ startStation tới endStation trước khi getAverageTime được gọi.

Bạn có thể giả sử mọi lời gọi checkIn và checkOut đều hợp lệ. Nếu một khách hàng check in tại thời điểm ~t_1~ rồi check out tại thời điểm ~t_2~ thì ~t_1 \lt t_2~. Mọi sự kiện diễn ra theo thứ tự thời gian.

Dữ liệu vào

• Dòng đầu là số nguyên ~Q~ — tổng số lời gọi.
• ~Q~ dòng tiếp theo, mỗi dòng là một lời gọi theo một trong ba dạng:
  • checkIn id stationName t
  • checkOut id stationName t
  • getAverageTime startStation endStation

Kết quả

• Với mỗi lời gọi getAverageTime, in ra trên một dòng thời gian trung bình tương ứng, làm tròn với đúng ~5~ chữ số sau dấu chấm thập phân.

Giới hạn

• ~1 \le~ id, t ~\le 10^6~
• ~1 \le~ stationName.length, startStation.length, endStation.length ~\le 10~
• Mọi xâu chỉ gồm chữ cái tiếng Anh in hoa, in thường và chữ số.
• Có tổng cộng nhiều nhất ~2 \cdot 10^4~ lời gọi tới checkIn, checkOut và getAverageTime.
• Đáp án sai khác giá trị thật không quá ~10^{-5}~ được chấp nhận.

Sample Input 1

12
checkIn 45 Leyton 3
checkIn 32 Paradise 8
checkIn 27 Leyton 10
checkOut 45 Waterloo 15
checkOut 27 Waterloo 20
checkOut 32 Cambridge 22
getAverageTime Paradise Cambridge
getAverageTime Leyton Waterloo
checkIn 10 Leyton 24
getAverageTime Leyton Waterloo
checkOut 10 Waterloo 38
getAverageTime Leyton Waterloo

Sample Output 1

14.00000
11.00000
11.00000
12.00000

Sample Input 2

9
checkIn 10 Leyton 3
checkOut 10 Paradise 8
getAverageTime Leyton Paradise
checkIn 5 Leyton 10
checkOut 5 Paradise 16
getAverageTime Leyton Paradise
checkIn 2 Leyton 21
checkOut 2 Paradise 30
getAverageTime Leyton Paradise

Sample Output 2

5.00000
5.50000
6.66667

Nguồn: LeetCode 1396.