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 ) 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 số nguyên: (số giao lộ là điểm lựa chọn), (số con đường, không quá ), (số mốc xác nhận, không quá ), (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á ), (số hiệu giao lộ bắt đầu), (số hiệu giao lộ kết thúc) và (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ừ đến .
Ngay sau dòng đầu là một dòng gồm 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 ).
Tiếp theo là dòng. Các con đường được đánh số bằng các số nguyên liên tiếp bắt đầu từ , theo thứ tự xuất hiện của các dòng mô tả. Mỗi dòng gồm số nguyên: số hiệu hai giao lộ được con đường nối, hai hướng la bàn (từ đến độ, là hướng bắc, 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à 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 số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ), độ 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
- , , , ; mỗi file có không quá bộ test.
- Độ dài mỗi con đường là số nguyên từ đến ; 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 .
- 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 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ộ theo con đường (hướng ) và tới điểm lựa chọn với hướng đi . Lần thử 1: đi thẳng theo đường , đi được mà chưa gặp mốc nên quay về (tốn ). Về tới với hướng : hai đường (hướng ) và (hướng ) đều phải rẽ độ, chọn đường bên phải là đường ; tới giao lộ thì vừa đủ (điểm kết thúc bị bỏ qua), quay về (tốn ). Lần thử 3: đường , gặp mốc cách giao lộ là ; tới giao lộ rồi đi thẳng theo đường tới giao lộ . Thỏ đi , chó săn đi . |
| 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 với hướng . Thử đường (đi thẳng): đi được ở giữa đường, quay về (tốn ). Về với hướng : đường (hướng , rẽ phải độ) tới ngõ cụt , quay về (tốn ). Về với hướng : đường (hướng ) tới điểm lựa chọn , quay về (tốn ). Còn lại đường : đi qua điểm kết thúc (bỏ qua) rồi theo đường gặp mốc ở quãng đường ; sau đó đi tiếp tới và theo đường về . |
Bình luận