trang chủ / đề bài / icpcwf08_d

Thỏ và chó săn

Đề bài

Mô tả

Trong một cuộc đua "thỏ và chó săn", người chơi (các "chó săn") phải tìm ra một lộ trình gồm một hoặc nhiều con đường do người tổ chức (con "thỏ") chọn. Cả hai bên đều di chuyển trên các con đường gặp nhau tại các giao lộ. Khi đi vào một giao lộ bất kỳ (trừ các giao lộ đặc biệt sẽ được mô tả ngay sau đây), cả chó săn và thỏ đều chọn đường theo quy tắc đường chính. Quy tắc đường chính luôn là "đi thẳng nhất có thể", nghĩa là rẽ một góc nhỏ nhất (có thể bằng 0) cần thiết để đi tiếp. Nếu có hai lựa chọn như vậy (chẳng hạn ở một số giao lộ hình chữ "Y"), quy tắc đường chính chọn con đường bên phải hơn (theo góc nhìn của chó săn) trong hai lựa chọn đó.

Tại một số giao lộ, thỏ có thể vi phạm quy tắc đường chính bằng cách đi theo một con đường bất kỳ rời khỏi giao lộ (nhưng không bao giờ là con đường vừa dùng để đi tới giao lộ đó). Các giao lộ này được thỏ đánh dấu là điểm lựa chọn (thường bằng một vệt màu trên mặt đường trong giao lộ). Khi tới một điểm lựa chọn, chó săn phải thử từng con đường rời khỏi giao lộ và đi theo con đường đó (có thể đi qua các giao lộ khác) cho tới khi gặp một mốc xác nhận (thường là một nắm bột mì thỏ rắc trên đường) xác nhận rằng đã chọn đúng lộ trình. Một lựa chọn sai được nhận ra khi xảy ra một trong các điều sau:

  • Chó săn đã đi được một quãng đường tối đa cho trước tính từ điểm lựa chọn mà chưa gặp mốc xác nhận.
  • Chó săn tới một "ngõ cụt" (một "giao lộ" chỉ có đúng một con đường đi tới nó) trước khi gặp mốc xác nhận.
  • Chó săn tới một điểm lựa chọn trước khi gặp mốc xác nhận. (Thỏ luôn đặt một mốc xác nhận trên lộ trình sau mỗi điểm lựa chọn. Ngoài ra, thỏ không bao giờ quay lại một điểm lựa chọn đã đi qua.)

Khi phát hiện một lựa chọn sai, chó săn phải đi ngược lại đúng con đường đã đi để về điểm lựa chọn và chọn một hướng khác. Nếu chó săn đi qua điểm kết thúc trong lúc đang tìm mốc xác nhận, nó bỏ qua điểm đó.

Khi chọn đường tại một điểm lựa chọn, chó săn dùng quy tắc đường chính theo một cách hơi khác. Con đường được chọn đầu tiên giống như khi giao lộ đó không phải là điểm lựa chọn. Nhưng nếu chó săn phải quay về điểm lựa chọn (tức là con đường đầu tiên đi từ điểm lựa chọn không thuộc lộ trình của thỏ), thì nó chọn con đường thứ hai bằng quy tắc đường chính theo hướng mà nó đi về tới điểm lựa chọn (bỏ qua mọi hướng đã thử và cả hướng mà nó đã đi tới lúc ban đầu). Quá trình này lặp lại mỗi lần chó săn quay về điểm lựa chọn cho tới khi tìm được đường đúng. Việc áp dụng quy tắc đường chính nhiều lần như vậy chỉ xảy ra tại các điểm lựa chọn. Trong bài này, chó săn không nhớ kết quả của việc đi trên bất kỳ con đường nào, kể cả khi nó quay lại con đường đó nhiều lần trong lúc tìm kiếm ở một điểm lựa chọn.

Bạn được cho bản đồ đường (các con đường và giao lộ), danh sách các giao lộ là điểm lựa chọn, vị trí các mốc xác nhận, quãng đường tối đa từ một điểm lựa chọn tới mốc xác nhận, giao lộ bắt đầu và giao lộ kết thúc (cả hai đều không phải điểm lựa chọn), và hướng dùng để rời giao lộ bắt đầu. Dựa vào các thông tin đó, hãy mô phỏng quá trình chó săn tìm lộ trình của thỏ. Bạn có thể giả sử rằng chó săn, theo chiến lược mô tả ở trên, luôn tìm ra và đi đúng lộ trình của thỏ.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng gồm 7 số nguyên: ncp (số giao lộ là điểm lựa chọn), nroad (số con đường, không quá 150), ncm (số mốc xác nhận, không quá 100), confdist (quãng đường tối đa từ một điểm lựa chọn tới mốc xác nhận, không quá 2000), startisect (số hiệu giao lộ bắt đầu), endisect (số hiệu giao lộ kết thúc) và startdir (hướng của con đường xuất phát). Các giao lộ được đánh số bằng các số nguyên từ 1 đến 100.

Ngay sau dòng đầu là một dòng gồm ncp số nguyên: số hiệu các giao lộ là điểm lựa chọn (dòng này rỗng nếu ncp=0).

Tiếp theo là nroad dòng. Các con đường được đánh số bằng các số nguyên liên tiếp bắt đầu từ 1, theo thứ tự xuất hiện của các dòng mô tả. Mỗi dòng gồm 5 số nguyên: số hiệu hai giao lộ được con đường nối, hai hướng la bàn (từ 0 đến 359 độ, 0 là hướng bắc, 90 là hướng đông) mà con đường rời khỏi lần lượt hai giao lộ đó, và độ dài con đường. Mỗi con đường đi được theo cả hai chiều, và không có hai con đường nào đi vào cùng một giao lộ theo cùng một góc.

Cuối cùng là ncm dòng mô tả vị trí các mốc xác nhận. Mỗi dòng gồm ba số nguyên: số hiệu một giao lộ, số hiệu một con đường rời khỏi giao lộ đó, và khoảng cách từ giao lộ tới mốc xác nhận. Mốc xác nhận không được đặt tại giao lộ. Mốc xác nhận cũng không được đặt trên các con đường có hai đầu là cùng một giao lộ.

Sau bộ test cuối cùng là một dòng gồm 7 số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ 1), độ dài lộ trình của thỏ, độ dài quá trình tìm kiếm của chó săn (tính cả mọi đoạn đường sai đã đi tại các điểm lựa chọn), và số hiệu các con đường trong lộ trình của thỏ theo đúng thứ tự thỏ đi qua, theo định dạng trong ví dụ. In một dòng trống sau kết quả của mỗi bộ test.

Ràng buộc

  • 0≤ncp≤100, 1≤nroad≤150, 0≤ncm≤100, 1≤confdist≤2000; mỗi file có không quá 100 bộ test.
  • Độ dài mỗi con đường là số nguyên từ 1 đến 104; khoảng cách từ giao lộ tới mốc xác nhận là số nguyên dương nhỏ hơn độ dài con đường chứa mốc.
  • Giao lộ bắt đầu khác giao lộ kết thúc, và có đúng một con đường rời giao lộ bắt đầu theo hướng startdir.
  • Mọi quãng đường đều tính dọc theo đường đi. Trong mọi bộ test, chó săn không bao giờ gặp một mốc xác nhận ở đúng quãng đường confdist tính từ điểm lựa chọn.

Ví dụ

Input Output Giải thích
1 5 1 3 3 1 180
2
2 4 180 0 5
1 4 180 90 6
4 2 270 270 5
3 2 180 0 8
1 2 270 90 3
4 3 3
0 0 0 0 0 0 0
Case 1:
Length of hare's route is 19
Length of hound's search is 31
Route: 4 3 2
Chó săn rời giao lộ 3 theo con đường 4 (hướng 180) và tới điểm lựa chọn 2 với hướng đi 180. Lần thử 1: đi thẳng theo đường 1, đi được 3 mà chưa gặp mốc nên quay về (tốn 6). Về tới 2 với hướng 0: hai đường 3 (hướng 270) và 5 (hướng 90) đều phải rẽ 90 độ, chọn đường bên phải là đường 5; tới giao lộ 1 thì vừa đủ 3 (điểm kết thúc bị bỏ qua), quay về (tốn 6). Lần thử 3: đường 3, gặp mốc cách giao lộ 2 là 2; tới giao lộ 4 rồi đi thẳng theo đường 2 tới giao lộ 1. Thỏ đi 8+5+6=19, chó săn đi 19+12=31.
2 8 1 10 1 6 90
2 4
1 2 90 270 4
2 3 90 270 25
2 8 315 135 3
2 4 180 0 6
2 6 0 180 4
6 7 0 180 5
7 6 30 90 6
4 3 90 180 7
7 6 2
0 0 0 0 0 0 0
Case 1:
Length of hare's route is 19
Length of hound's search is 57
Route: 1 5 6 7
Tới điểm lựa chọn 2 với hướng 90. Thử đường 2 (đi thẳng): đi được 10 ở giữa đường, quay về (tốn 20). Về với hướng 270: đường 3 (hướng 315, rẽ phải 45 độ) tới ngõ cụt 8, quay về (tốn 6). Về với hướng 135: đường 4 (hướng 180) tới điểm lựa chọn 4, quay về (tốn 12). Còn lại đường 5: đi qua điểm kết thúc 6 (bỏ qua) rồi theo đường 6 gặp mốc ở quãng đường 4+3=7; sau đó đi tiếp tới 7 và theo đường 7 về 6.

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