Tóm tắt đề bài

Gần nhà Bờm có ga tàu điện. Số hiệu chuyến tàu ~x~ sẽ dừng ở ~T_0 + x \times D~. Có ~N~ hành khách chờ tàu, hành khách thứ ~i~ chờ ở thời điểm ~s_i~ và sẽ lên chuyến đầu tiên không sớm hơn ~s_i~. Hãy xác định số hiệu chuyến tàu của từng hành khách sẽ lên.

Lời giải

Với mỗi khách, ta cần tìm số nguyên ~x~ nhỏ nhất sao cho ~T_0 + k \times D \le s_i~. Tức là ~k = \frac{s_i - T_0 + D - 1}{D}~.

Nhưng do ~k~ đánh số từ ~1~, nên số hiệu chuyến tàu sẽ là ~k + 1~

ĐPT: ~O~(~n~).