🎓 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

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

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

Giữa dòng sông Hậu có một cù lao, quanh cù lao có ~N~ nhà học trò của thầy Sơn, mỗi nhà có một bến xuồng. Các bến xếp thành một vòng tròn và được đánh số ~1, 2, \dots, N~ theo chiều nước chảy: từ bến ~i~ chèo xuôi sẽ tới bến ~i + 1~, còn từ bến ~N~ chèo xuôi sẽ quay về bến ~1~.

Dịp đầu năm học, thầy Sơn chèo xuồng đi thăm nhà học trò. Thầy chọn một bến xuất phát ~s~, rồi ghé lần lượt các nhà ~s, s + 1, s + 2, \dots~ theo chiều nước chảy (đi qua bến ~N~ thì tiếp tục với bến ~1~), không bỏ qua nhà nào và không ghé nhà nào hai lần (nên ghé tối đa ~N~ nhà). Ghé nhà thứ ~i~ mất ~a_i~ phút (tính luôn thời gian chèo tới bến kế tiếp); có nhà ~a_i = 0~ vì nhà vắng người, thầy chỉ treo quà ở cổng rồi đi ngay.

Thầy chỉ có ~T~ phút, nên tổng thời gian của các nhà được ghé không được vượt quá ~T~. Hãy giúp thầy Sơn tính:

• ~K~ là số nhà nhiều nhất thầy có thể ghé thăm (khi chọn bến xuất phát tốt nhất);
• ~C~ là số bến xuất phát ~s~ (~1 \le s \le N~) mà nếu xuất phát từ ~s~ thì thầy ghé được đúng ~K~ nhà.

Nếu thầy không thể ghé được nhà nào (tức ~K = 0~), quy ước ~C = 0~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~T~ ~(1 \le N \le 2 \times 10^5;~ ~0 \le T \le 10^{18})~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_i \le 10^9)~.

Kết quả

In ra hai số nguyên ~K~ và ~C~, cách nhau một dấu cách.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 300~.
• Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

6 12
3 6 2 7 2 9

Sample Output 1

3 2

Giải thích

• Xuất phát từ bến ~1~: ghé nhà ~1, 2, 3~ hết ~3 + 6 + 2 = 11~ phút (thêm nhà ~4~ thì thành ~18 > 12~) → ~3~ nhà.
• Xuất phát từ bến ~2~: ghé nhà ~2, 3~ hết ~8~ phút (thêm nhà ~4~ thì thành ~15~) → ~2~ nhà.
• Xuất phát từ bến ~3~: ghé nhà ~3, 4, 5~ hết ~2 + 7 + 2 = 11~ phút (thêm nhà ~6~ thì thành ~20~) → ~3~ nhà.
• Xuất phát từ bến ~4~: ghé nhà ~4, 5~ hết ~9~ phút (thêm nhà ~6~ thì thành ~18~) → ~2~ nhà.
• Xuất phát từ bến ~5~: ghé nhà ~5, 6~ hết ~11~ phút (thêm nhà ~1~ thì thành ~14~) → ~2~ nhà.
• Xuất phát từ bến ~6~: ghé nhà ~6~ rồi nhà ~1~, hết ~9 + 3 = 12~ phút (thêm nhà ~2~ thì thành ~18~) → ~2~ nhà.

Vậy ~K = 3~ và có ~C = 2~ bến xuất phát (bến ~1~ và bến ~3~) đạt được ~3~ nhà.

Sample Input 2

6 6
0 5 0 4 7 2

Sample Output 2

3 1

Giải thích

Nhà ~1~ và nhà ~3~ vắng người nên ghé mất ~0~ phút. Xuất phát từ bến ~1~, thầy ghé nhà ~1, 2, 3~ hết ~0 + 5 + 0 = 5~ phút (thêm nhà ~4~ thì thành ~9 > 6~) → ~3~ nhà. Xuất phát từ các bến ~2, 3, 4, 5, 6~ thì ghé được lần lượt ~2, 2, 1, 0, 2~ nhà (riêng bến ~5~: nhà ~5~ đã mất ~7 > 6~ phút nên không ghé được nhà nào). Vậy ~K = 3~ và ~C = 1~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).