Link Sub: http://www.spoj.com/PTIT/problems/PTIT135B/
Người Gửi: Vô Danh
- Problem:
Luka lái xe trên một đoạn đường thẳng, có rất nhiều đèn giao thông trên đoạn đường này. Khi Luka bắt đầu chuyển động từ vị trí xuất phát thì tất cả các đèn giao thông đều hiện thỉ màu đỏ và bắt đầu chu kì.
Luka đi một đơn vị đường hết 1s. Nhiệm vụ của các bạn là hãy tính xem Luka cần bao nhiêu thời gian để đi hết quãng đường này?
Input
Dòng đầu tiên gồm 2 số N và L là số đèn giao thông trên đường và chiều dài quãng đường. (1 <= N <= 100, 1 <= L <= 1000).
N dòng tiếp theo, mỗi dòng gồm 3 số D, R, G là khoảng cách từ điểm xuất phát tới đèn giao thông đó, số giây đèn đỏ và số giây đèn xanh. (1 <= D < L, 1 <= R <= 100, 1 <= G <= 100).
Các đèn giao thông sẽ được sắp xếp theo khoảng cách tăng dần, không có 2 đèn nào ở cùng 1 vị trí.
Output
Thời gian mà Luka cần để hoàn thành hết quãng đường đó.
Example:
Thời gian mà Luka cần để hoàn thành hết quãng đường đó.
Input
2 10
3 5 5
5 2 2
Output:
12
Input
4 30
7 13 5
14 4 4
15 3 10
25 1 1
Output:
36
- Solution:
Giải thích test 1: Luka sẽ phải chờ 2s ở đèn thứ nhất, sau đó đi đến đèn giao thông thứ 2 (giây thứ 7)thì đèn thứ 2 đang là màu xanh, do đó đi tiếp đến hết quãng đường cần 5s nữa, tổng cộng cần 12s.Input
4 30
7 13 5
14 4 4
15 3 10
25 1 1
Output:
36
*Cách làm: - Sử dụng struct lưu trạng thái. - Chạy xe đến từng đèn báo. - Thay vì ta chạy chu kỳ đèn đỏ rồi mới đến đèn xanh thì ta sẽ chạy chu kỳ trên cả time 2 đèn (total). Bằng việc sử dụng toán tử % ta có thể xác định được đèn đang ở trong khoảng R or G. - Chú ý: lúc dừng đèn đỏ thì vẫn phải cập nhật trạng thái cho các đèn khác.