Thống kê mượn sách và phát hiện trùng ngày tại Thư viện số ThuVienSo

Thư viện số ThuVienSo có log gồm n lượt mượn sách. Với lượt mượn thứ i, hệ thống lưu: thời gian mượn t[i] (đơn vị phút) và mã ngày mượn d[i] (số nguyên).

Ban quản trị cần một chương trình thực hiện hai việc nối tiếp nhau:

• Tính tổng thời gian mượn của tất cả n lượt mượn (dùng một vòng lặp đơn cộng dồn).
• Đếm số cặp lượt mượn (i, j) với i < j có cùng mã ngày mượn — đây là các cặp cần rà soát khả năng mượn hộ (dùng vòng lặp lồng nhau so sánh từng cặp).

Sau khi tính xong, hãy áp dụng quy tắc cộng đã học để xác định độ phức tạp thời gian tổng thể của toàn chương trình (chương trình gồm bước 1 có độ phức tạp O(n) chạy nối tiếp với bước 2 có độ phức tạp O(n^2)) và in ra bậc O-lớn đó.

Định dạng vào: dòng 1 là n; dòng 2 gồm n số nguyên là thời gian mượn (phút); dòng 3 gồm n số nguyên là mã ngày mượn.

Định dạng ra: dòng 1 là tổng thời gian mượn; dòng 2 là số cặp lượt mượn cùng ngày; dòng 3 là bậc độ phức tạp thời gian tổng thể (dạng O(n^2)).