trang chủ / đề bài / icpcwf04_a

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 1 cm, di chuyển và đào đất với tốc độ 1 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 0. 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 1 cm: p0=(0,0),p1,…,pL là các điểm nguyên lần lượt trên đường đi, L là độ dài đường. Một điểm mà Carl đi qua hai lần, pi=pj với i<j, 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 ph. 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 ở ph là ph+1, trừ một trường hợp: ph là lần đi qua thứ nhất của một giao điểm (ph=pj với j>h) và đầu của Carl đã đi qua pj (đầu Carl đang ở pg với g>j, hoặc Carl đã chui xuống đất). Khi đó vệt mới nhất là vệt Carl để lại khi rời pj, nên điểm kế tiếp là pj+1 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 ở pL ở thời điểm t chui xuống đất và hoàn thành đường đi ở thời điểm t+1 (khi đó điểm pL trống ở thời điểm t+1).
  • Carl (kiến số 0) có đầu ở p0 ở thời điểm 0. Kiến số k (k≥1) chui lên, tức là có đầu ở p0, ở thời điểm nguyên nhỏ nhất không nhỏ hơn k·d và không nhỏ hơn thời điểm kiến k−1 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 T 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 n, m, d: n là số đoạn thẳng trên đường đi của Carl, m là số con kiến đi trên đường (kể cả Carl), d là khoảng thời gian giữa hai lần xuất phát liên tiếp. Carl (số hiệu 0) xuất phát ở thời điểm 0. Con kiến tiếp theo (số hiệu 1) chui lên ở thời điểm d, con tiếp theo ở thời điểm 2d, và cứ thế.

Mỗi dòng trong n dòng tiếp theo chứa một cặp số nguyên x y 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ạ độ (0,0), đ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 đó C là số thứ tự bộ test (bắt đầu từ 1), a1,a2,…,am là số hiệu các con kiến theo thứ tự chui xuống đất, t1 và t2 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

  • 1≤T≤20.
  • 1≤n≤50, 1≤m≤100, 1≤d≤100.
  • −100≤x,y≤100.
  • 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 (0,0). 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 12, cắt chính nó tại (0,2): lần thứ nhất ở p2 (thời điểm 2), lần thứ hai ở p10 (thời điểm 10). Carl tới cuối đường ở thời điểm 12, chui xuống xong ở thời điểm 13. Bộ 1: kiến 1 tới (0,2) ở thời điểm 6, lúc đó chưa có vệt mới nên đi vòng như Carl; kiến 2 muốn vào (0,2) ở thời điểm 10 cùng lúc với Carl, Carl được đi trước, kiến 2 vào ở thời điểm 11 rồi rẽ trái đi tắt, xong ở thời điểm 14; kiến 3 và kiến 1 cùng muốn vào (0,2) ở thời điểm 14, kiến 1 đượ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 (0,1)=p1=p5. Ở thời điểm 4, Carl ở p4, kiến 1,2,3 ở p3,p2,p1, kiến 4 ở gốc. Trong giây tiếp theo, Carl, kiến 1,2,3 tạo thành vòng khép kín và cùng di chuyển (Carl thắng kiến 4 khi cùng muốn vào (0,1) vì số hiệu nhỏ hơn). Ở thời điểm 6, kiến 4 (đã chờ từ thời điểm 4) thắng kiến 1 (đến p4 ở thời điểm 5), vào (0,1) rồi đi tắt sang p6 và xong ở thời điểm 8; kiến 1,2,3 xong ở thời điểm 9,10,11.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0