Kỳ thi năm mới
Đề bài
Mô tả
Một kỳ thi lập trình bắt đầu lúc 18:00 ngày 31 tháng 12 và kết thúc lúc 6:00 ngày 1 tháng 1, tức là kéo dài đúng phút. Thời điểm Giao thừa (0:00) rơi vào đúng phút thứ tính từ lúc bắt đầu.
Có bài trong kỳ thi. Thí sinh dành đúng phút đầu tiên để đọc và ước lượng độ khó, nên chỉ có thể bắt đầu viết lời giải từ phút thứ . Bài thứ cần đúng phút để viết xong.
Thí sinh có thể chuyển qua lại giữa các bài bất cứ lúc nào và quay lại đúng chỗ đang dở, nên tổng thời gian viết bài luôn là phút. Việc nộp bài coi như tốn thời gian, và có thể nộp nhiều bài cùng một lúc. Một lời giải chỉ có thể được nộp sau khi đã viết xong, và có thể được nộp vào bất kỳ thời điểm nào sau đó (kể cả giữ lại chờ nộp muộn hơn). Mọi lời giải đều đúng ngay từ lần nộp đầu tiên.
Thời gian phạt của một bài là khoảng cách (tính bằng phút) từ thời điểm nộp bài đó tới Giao thừa. Ví dụ, bài nộp lúc phút thứ hay phút thứ đều bị phạt . Được phép nộp bài đúng vào lúc kỳ thi kết thúc (phút thứ ). Tổng thời gian phạt là tổng thời gian phạt của tất cả các bài đã giải.
Trong số các chiến lược giúp giải được nhiều bài nhất có thể, hãy tìm chiến lược có tổng thời gian phạt nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên là số bài.
- Dòng thứ hai chứa số nguyên , thời gian (phút) cần để viết lời giải bài thứ .
Dữ liệu ra
In ra hai số nguyên: số bài giải được và tổng thời gian phạt nhỏ nhất khi chọn chiến lược tối ưu.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 30 330 720 |
2 10 | Bắt đầu viết bài 1 lúc phút , xong lúc phút . Viết tiếp bài 2 (cần phút), xong lúc phút . Bài 1 xong trước Giao thừa nên giữ lại nộp đúng lúc phút (phạt ); bài 2 nộp lúc phút (phạt ). Bài 3 cần phút nên không kịp. Tổng phạt . |
| 5 100 200 300 400 500 |
3 250 | Giải 3 bài ngắn nhất (), hoàn thành tại các phút . Hai bài đầu nộp lúc phút (phạt ), bài thứ ba nộp lúc phút (phạt ). |
| 1 710 |
1 360 | Hoàn thành đúng lúc phút , phạt . |
Bình luận