READ - Tốc độ đọc sách
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
~K~ con bò ~(0 < K \le 1000)~ tham dự vào cuộc thi đọc sách hàng năm do nông dân John tổ chức. Trong cuộc thi này, mỗi con sẽ cùng đọc 1 quyển sách có ~N~ trang ~(0 < N \le 10^5)~. Con bò thứ ~k~ có thể đọc với tốc độ ~S_k~ trang/phút, nhưng nó chỉ có thể duy trì tốc độ này trong ~T_k~ phút liên tục. Sau đó, nó phải nghỉ trong ít nhất ~R_k~ phút, kể cả trong trường hợp nó không dùng hết khả năng để đọc ~(0 < S_k, T_k, R_k \le 100)~.
Xác định thời gian nhỏ nhất để mỗi con bò hoàn thành việc đọc sách.
Input
- Dòng đầu tiên chứa 2 số nguyên dương ~N~ và ~K~
- Dòng ~2..K + 1~: dòng thứ ~k + 1~ chứa 3 số nguyên dương ~S_k, T_k~ và ~R_k~
Output
- Đưa ra ~K~ dòng. Dòng thứ ~k~ là thời gian tối thiểu (tính theo phút) để con bò thứ ~k~ hoàn thành cuốn sách. Làm tròn kết quả lên số nguyên dương nhỏ nhất và lớn hơn hoặc bằng nó.
Sample
Input #1
10 3
2 4 1
6 1 5
3 3 3
Output #1
6
7
7
Problem source: Kc97ble - Free Contest 21
Bình luận
HI, bro. OK nếu bạn chưa thể AC bài, hãy xem solution nhé.
Đầu tiên ta sẽ thấy ngay số phút tối thiểu để con bò đọc xong n trang sách (không nghỉ, không bị giới hạn thời gian đọc liên tục) sẽ là: n // s + (n % s != 0) [phép toán (n % s != 0) sẽ trả về 0 nếu n chia hết cho s, ngược lại trả về 1]
Vậy là ta đã có số phút đọc không nghỉ, liên tục của chú bò (ta đặt là p). Thế nếu có thêm thời gian nghỉ sau mỗi t phút đọc liên tục nữa thì rõ ràng ta phải đi tìm x thoả mãn p + x * r (với x là số lần nghỉ, r là thời gian nghỉ), sao cho p + x * r nhỏ nhất. Ta làm như sau.
Đề cho ta tham số t (con bò có thể đọc được liên tục trong t phút) nghĩa là ta có thể chia p thành nhiều đoạn bằng phép toán p // t + (p % t != 0).
Ở giữa mội đoạn sẽ có thời gian nghỉ r chen vào giữa. Vậy tổng thời gian nghỉ sẽ là (p // t + (p % t != 0) - 1) * r.
Vậy x của ta chính là (p // t + (p % t != 0) - 1). Kết quả là p + (p // t + (p % t != 0) - 1) * r