Chú kiến Carl
Đề bài
Mô tả
Kiến để lại những vệt hoá chất nhỏ trên mặt đất để đánh dấu đường cho các con kiến khác đi theo. Thông thường những vệt này khá thẳng. Nhưng trong một tổ kiến có một con kiến tên là Carl, và Carl không phải một con kiến bình thường. Carl thường đi zíc zắc chẳng vì lý do gì, đôi khi cắt ngang đường đi của chính mình nhiều lần. Khi các con kiến khác đến một giao điểm, chúng luôn đi theo con đường có mùi mạnh nhất, tức là con đường mới nhất dẫn ra khỏi giao điểm đó.
Kiến dài cm, di chuyển và đào đất với tốc độ cm mỗi giây, và đi đúng theo đường của mình (rẽ vuông góc ở các góc). Kiến không thể đi xuyên qua hay chồng lên nhau. Nếu hai con kiến gặp nhau đúng cùng một thời điểm tại một giao điểm, con kiến đã ở trên đường của Carl lâu hơn được đi trước; ngược lại, con kiến đã chờ ở giao điểm lâu nhất sẽ đi trước.
Carl chui lên khỏi mặt đất để bắt đầu tại gốc toạ độ ở thời điểm . Sau đó Carl đi hết đường của mình và chui xuống đất tại điểm cuối. Các con kiến còn lại lần lượt đi theo sau, cách nhau đều đặn. Cho mô tả đường đi của Carl và thời điểm các con kiến khác xuất phát, hãy xác định sau bao lâu toàn bộ đàn kiến chui hết xuống đất. Đảm bảo mọi con kiến đều đi hết đường.
Để kết quả được xác định duy nhất, chuyển động của đàn kiến tuân theo đúng các quy tắc sau (khớp với ví dụ của đề gốc):
- Đường đi của Carl được chia thành các bước dài cm: là các điểm nguyên lần lượt trên đường đi, là độ dài đường. Một điểm mà Carl đi qua hai lần, với , là một giao điểm (đó luôn là chỗ hai đoạn vuông góc cắt nhau).
- Vị trí của một con kiến là vị trí đầu của nó; ở mỗi thời điểm nguyên, đầu mỗi con kiến đang ở trên đường nằm tại một điểm . Trong mỗi giây, mỗi con kiến hoặc tiến đầu sang điểm kế tiếp trên đường của nó, hoặc đứng yên.
- Điểm kế tiếp của con kiến có đầu ở là , trừ một trường hợp: là lần đi qua thứ nhất của một giao điểm ( với ) và đầu của Carl đã đi qua (đầu Carl đang ở với , hoặc Carl đã chui xuống đất). Khi đó vệt mới nhất là vệt Carl để lại khi rời , nên điểm kế tiếp là và con kiến đi tiếp từ đó.
- Ở mỗi thời điểm nguyên, mỗi điểm có không quá một đầu kiến. Một con kiến được đi vào một điểm đúng trong giây mà con kiến có đầu ở điểm đó rời đi (kiến nối đuôi sát nhau, hoặc đi cắt ngang ngay sau đuôi con kiến khác). Ngoài điều đó, thân kiến không cản đường kiến khác.
- Nếu nhiều con kiến cùng muốn đi vào một điểm trong cùng một giây, con kiến đã đến vị trí hiện tại của nó sớm nhất (đã chờ lâu nhất) được đi; nếu bằng nhau, con có số hiệu nhỏ hơn (ở trên đường lâu hơn) được đi. Các con còn lại đứng yên trong giây đó.
- Một con kiến di chuyển trong một giây nếu nó được quyền đi vào điểm kế tiếp và điểm đó đang trống hoặc con kiến đang ở điểm đó cũng di chuyển trong giây này. Nếu một nhóm kiến tạo thành vòng khép kín (mỗi con muốn đi vào điểm của con tiếp theo trong vòng) và tất cả đều được quyền, cả vòng cùng di chuyển.
- Con kiến có đầu ở ở thời điểm chui xuống đất và hoàn thành đường đi ở thời điểm (khi đó điểm trống ở thời điểm ).
- Carl (kiến số ) có đầu ở ở thời điểm . Kiến số () chui lên, tức là có đầu ở , ở thời điểm nguyên nhỏ nhất không nhỏ hơn và không nhỏ hơn thời điểm kiến chui lên, mà tại đó gốc toạ độ không có đầu kiến nào sau các di chuyển của giây vừa qua. Nói cách khác, nếu lối ra bị chắn, kiến chui lên ngay khi có thể và đúng thứ tự.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên là số bộ test.
Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương , , : là số đoạn thẳng trên đường đi của Carl, là số con kiến đi trên đường (kể cả Carl), là khoảng thời gian giữa hai lần xuất phát liên tiếp. Carl (số hiệu ) xuất phát ở thời điểm . Con kiến tiếp theo (số hiệu ) chui lên ở thời điểm , con tiếp theo ở thời điểm , và cứ thế.
Mỗi dòng trong dòng tiếp theo chứa một cặp số nguyên là điểm cuối của một đoạn thẳng trên đường đi của Carl, theo đúng thứ tự Carl đi. Đoạn thứ nhất bắt đầu từ gốc toạ độ , điểm đầu của mỗi đoạn sau là điểm cuối của đoạn trước.
Dữ liệu ra
Kết quả của mỗi bộ test có dạng:
Case C:
Carl finished the path at time t1
The ants finished in the following order:
a1 a2 a3 ... am
The last ant finished the path at time t2
Trong đó là số thứ tự bộ test (bắt đầu từ ), là số hiệu các con kiến theo thứ tự chui xuống đất, và là thời điểm (tính bằng giây) Carl và con kiến cuối cùng chui hết xuống đất. Giữa hai bộ test liên tiếp in đúng một dòng trống.
Ràng buộc
- .
- , , .
- .
- Mỗi đoạn thẳng song song với một trục toạ độ và có độ dài dương.
- Các điểm cuối đôi một khác nhau và khác . Không điểm cuối nào (kể cả gốc toạ độ) nằm trên một đoạn thẳng mà nó không phải là đầu mút.
- Với mọi bộ test, theo các quy tắc trên mọi con kiến đều đi hết đường.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 7 4 0 4 2 4 2 2 -2 2 4 7 2 0 4 2 4 2 2 -2 2 |
Case 1: Carl finished the path at time 13 The ants finished in the following order: 0 2 1 3 4 5 6 The last ant finished the path at time 29 Case 2: Carl finished the path at time 13 The ants finished in the following order: 0 4 1 5 2 6 3 The last ant finished the path at time 19 |
Đường dài , cắt chính nó tại : lần thứ nhất ở (thời điểm ), lần thứ hai ở (thời điểm ). Carl tới cuối đường ở thời điểm , chui xuống xong ở thời điểm . Bộ 1: kiến tới ở thời điểm , lúc đó chưa có vệt mới nên đi vòng như Carl; kiến muốn vào ở thời điểm cùng lúc với Carl, Carl được đi trước, kiến vào ở thời điểm rồi rẽ trái đi tắt, xong ở thời điểm ; kiến và kiến cùng muốn vào ở thời điểm , kiến được đi trước. |
| 1 4 5 1 0 2 1 2 1 1 -1 1 |
Case 1: Carl finished the path at time 7 The ants finished in the following order: 0 4 1 2 3 The last ant finished the path at time 11 |
Ví dụ tự thêm. Giao điểm . Ở thời điểm , Carl ở , kiến ở , kiến ở gốc. Trong giây tiếp theo, Carl, kiến tạo thành vòng khép kín và cùng di chuyển (Carl thắng kiến khi cùng muốn vào vì số hiệu nhỏ hơn). Ở thời điểm , kiến (đã chờ từ thời điểm ) thắng kiến (đến ở thời điểm ), vào rồi đi tắt sang và xong ở thời điểm ; kiến xong ở thời điểm . |
https://oj.chuyentin.pro/problem/icpcwf04_a
Bình luận