Điều phối đường ray
Đề bài
Mô tả
Dooby là một người đam mê tàu hỏa, năng động và tỉ mỉ, vừa được tuyển làm nhân viên điều hành tàu. Tuy nhiên, nhiệm vụ đầu tiên của cô không hề đơn giản.
Dooby phụ trách một tuyến đường ray mới nối Primstation và Krustown. Đường ray là một đoạn thẳng dài mét. Mỗi ngày, Dooby phải lập lịch chạy cho các đoàn tàu trên tuyến này, và danh sách tàu thay đổi theo từng ngày.
Ban đầu chưa có đoàn tàu nào. Công việc của Dooby kéo dài ngày, vào ngày thứ xảy ra một trong các sự kiện sau:
- "+ ": một đoàn tàu dài mét, chạy với vận tốc không đổi mét mỗi giờ được thêm vào danh sách tàu của Dooby.
- "- ": một đoàn tàu dài mét, chạy với vận tốc không đổi mét mỗi giờ bị xóa khỏi danh sách tàu của Dooby. Dữ liệu đảm bảo danh sách hiện tại có ít nhất một đoàn tàu như vậy.
Mỗi ngày, tất cả các đoàn tàu trong danh sách của Dooby đều xuất phát từ Primstation và phải đi đến Krustown. Vì chỉ có một đường ray, các đoàn tàu phải được sắp theo một thứ tự nhất định và xuất phát vào những thời điểm nhất định để không va chạm. Khi một đoàn tàu tới Krustown, nó lập tức được đưa vào nhà kho, nhường đường cho đoàn tàu tiếp theo.
Trước khi khởi hành, đầu tàu của mỗi đoàn tàu được đặt thẳng hàng với điểm đầu của đường ray. Một đoàn tàu được coi là đã tới Krustown khi đuôi tàu vượt qua điểm cuối của đường ray.
Để chứng tỏ năng lực, Dooby phải tìm thời điểm xuất phát của mọi đoàn tàu mỗi ngày sao cho:
- không có hai đoàn tàu nào va chạm, và
- thời gian cần để tất cả các đoàn tàu tới Krustown là nhỏ nhất.
Nhiệm vụ của bạn là giúp Dooby lập lịch. Với mỗi ngày trong ngày, hãy tìm thời gian nhỏ nhất cần để tất cả các đoàn tàu đang có trong danh sách tới Krustown an toàn. In theo modulo .
Một cách hình thức, đặt . Có thể chứng minh rằng đáp án biểu diễn được dưới dạng phân số tối giản , trong đó là các số nguyên và . Hãy in ra số nguyên bằng , tức là số nguyên thỏa và .
Điều kiện va chạm. Với đoàn tàu thứ , gọi và lần lượt là vị trí đuôi tàu và đầu tàu tại thời điểm . Theo định nghĩa, . Hai đoàn tàu và được coi là va chạm nếu tồn tại thời điểm sao cho:
- cả đoàn tàu và đoàn tàu đều đã rời Primstation (đã xuất phát),
- cả hai đều chưa tới Krustown, và
- .
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ): độ dài đường ray (mét) và số ngày làm việc của Dooby.
Mỗi dòng trong dòng tiếp theo mô tả sự kiện của một ngày, có một trong hai dạng:
- "+ " (): thêm một đoàn tàu dài mét, vận tốc mét mỗi giờ vào danh sách.
- "- " (): xóa một đoàn tàu dài mét, vận tốc mét mỗi giờ khỏi danh sách. Dữ liệu đảm bảo danh sách hiện tại có ít nhất một đoàn tàu như vậy.
Dữ liệu ra
In ra dòng. Dòng thứ chứa thời gian nhỏ nhất cần để tất cả các đoàn tàu trong danh sách của ngày thứ tới Krustown an toàn, theo modulo . Nếu ngày thứ danh sách không có đoàn tàu nào, in ra .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 20 4 + 2 2 + 3 3 + 5 2 - 2 2 |
11 12 499122191 499122190 |
Ngày 1: chỉ có tàu (dài , vận tốc ); đầu tàu tới Krustown sau giờ, đuôi tàu ra khỏi đường ray thêm giờ. Ngày 2: tàu xuất phát lúc giờ và tới Krustown đúng lúc giờ; nếu xuất phát sớm hơn, ví dụ lúc giờ, nó sẽ va chạm với tàu lúc giờ. Ngày 3: tàu xuất phát lúc , tàu lúc , tàu lúc giờ và tới nơi lúc giờ; . Ngày 4: tàu xuất phát lúc , tàu lúc và tới nơi lúc giờ. |
| 10 6 + 4 5 + 6 5 - 4 5 - 6 5 + 1 1 + 1 1 |
399297744 4 598946615 0 11 12 |
Các đáp án lần lượt là giờ. Ngày 4 danh sách rỗng nên in . Ngày 6 có hai đoàn tàu giống hệt nhau. |
Bình luận