Cuộc rượt đuổi vui nhộn
Đề bài
Mô tả
Đây là bài toán tương tác.
Viên kim cương Fornax, viên đá quý giá nhất thiên hà, đã bị Bash, tên trộm khét tiếng nhất thiên hà, đánh cắp! Alexia, một sĩ quan của Cảnh sát Liên thiên hà, đang truy đuổi hắn. Thiên hà là một mặt phẳng tọa độ Descartes, và cả Alexia lẫn Bash luôn đứng tại các điểm có tọa độ nguyên thỏa mãn và .
Alexia có một khẩu súng cổng dịch chuyển, có thể đưa cô tới bất kỳ điểm nào của thiên hà. Bash trốn chạy bằng một khẩu súng cổng dịch chuyển đời cũ đã hỏng: nó luôn đưa hắn tới một điểm ngẫu nhiên. Vì pin yếu, Bash phải luân phiên giữa một lần nhảy xa và một lần nhảy gần. Cụ thể, các lần nhảy của Bash luân phiên như sau:
- Ở các lần nhảy thứ (nhảy xa), Bash di chuyển tới một điểm được chọn ngẫu nhiên đều trong tất cả các điểm của thiên hà.
- Ở các lần nhảy thứ (nhảy gần), nếu Bash đang ở , hắn di chuyển tới một điểm được chọn ngẫu nhiên đều trong tất cả các điểm của thiên hà thỏa mãn .
Mọi lựa chọn ngẫu nhiên là độc lập, và các lần nhảy của Bash không phụ thuộc vào cách di chuyển của Alexia.
May mắn thay, Cảnh sát Liên thiên hà đã giấu một thiết bị theo dõi bên trong viên kim cương Fornax để bảo vệ nó. Gọi và là vị trí của Alexia và Bash. Vào lúc bắt đầu cuộc truy đuổi, mỗi khi Alexia di chuyển, và mỗi khi Bash nhảy xa, Alexia biết được bình phương khoảng cách Euclid giữa hai người, tức là . Tuy nhiên, vì pin yếu, khi nhảy gần khẩu súng cũ của Bash chạy ở chế độ tiết kiệm năng lượng và phát ra nhiều nhiễu điện từ tới mức làm nhiễu tín hiệu của thiết bị theo dõi, nên thiết bị chỉ ước lượng được khoảng cách một cách thô: mỗi khi Bash nhảy gần, khoảng cách Euclid trước hết được làm tròn tới bội số gần nhất của (nếu khoảng cách nằm chính giữa hai bội số liên tiếp của thì làm tròn lên), sau đó Alexia chỉ biết bình phương của khoảng cách đã làm tròn này. Ví dụ, khoảng cách được làm tròn thành , và Alexia biết được .
Ban đầu, Alexia ở và Bash ở một điểm được chọn ngẫu nhiên đều trong tất cả các điểm của thiên hà. Sau đó Alexia và Bash lần lượt thực hiện lượt của mình, Alexia đi trước:
- Alexia di chuyển tới một điểm bất kỳ của thiên hà (được phép đứng yên tại vị trí hiện tại).
- Bash thực hiện lần nhảy tiếp theo của hắn.
Alexia bắt được Bash bằng cách di chuyển tới đúng điểm Bash đang đứng. Lưu ý rằng nếu Bash nhảy tới vị trí của Alexia thì hắn chưa bị bắt; hắn chỉ có thể bị bắt ở lượt tiếp theo của Alexia nếu cô chọn đứng yên tại vị trí hiện tại. Hãy giúp Alexia bắt Bash với không quá lần di chuyển.
Tương tác
Đầu tiên, chương trình đọc số bộ test (). Với mỗi bộ test:
- Đầu tiên, chương trình đọc một số nguyên : bình phương khoảng cách giữa vị trí ban đầu của Alexia và vị trí ban đầu của Bash.
- Sau đó chương trình thực hiện không quá lần di chuyển. Với mỗi lần di chuyển:
- Chương trình in ra hai số nguyên và (, ), nghĩa là Alexia di chuyển tới .
- Chương trình đọc một số nguyên : bình phương khoảng cách giữa Alexia và Bash sau khi Alexia di chuyển. Nếu , Alexia đã bắt được Bash, và chương trình chuyển sang bộ test tiếp theo, hoặc kết thúc nếu đây là bộ test cuối cùng.
- Ngược lại, Bash nhảy, và chương trình đọc một số nguyên : bình phương khoảng cách giữa Alexia và Bash nếu đây là lần nhảy xa, hoặc bình phương của khoảng cách đã làm tròn tới bội số gần nhất của nếu đây là lần nhảy gần.
Nếu chương trình in ra một lần di chuyển không hợp lệ, hoặc Alexia vẫn chưa bắt được Bash sau lần di chuyển thứ , trình tương tác in ra thay cho khoảng cách. Khi đó chương trình cần kết thúc ngay lập tức và sẽ nhận kết quả Wrong Answer.
Sau mỗi dòng in ra, nhớ in ký tự xuống dòng và flush luồng ra (ví dụ cout << endl; hoặc fflush(stdout); trong C++, sys.stdout.flush() trong Python).
Ràng buộc
- Mọi điểm của Alexia và Bash có tọa độ nguyên, , .
- Mỗi bộ test được di chuyển không quá lần.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 25 2000000002000000025 25 0 |
1000000000 1000000000 999999995 1000000000 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra (theo thứ tự xen kẽ như mô tả ở trên). Bash ban đầu ở , . Alexia di chuyển tới , khoảng cách tới có bình phương . Bash nhảy xa tới , . Alexia di chuyển tới và bắt được Bash (). |
| 1 4073 2000000030000004073 1999999972000000100 961330542669438760 961327303729000000 1999995972004032100 50 0 |
1000000000 1000000000 -409979200 890644490 1000000000 1000000000 999999993 999999999 |
Bash ban đầu ở , . Alexia tới ; Bash nhảy xa tới . Alexia tới , Bash không ở đó (); Bash nhảy gần tới , khoảng cách được làm tròn thành , nên Alexia đọc được . Alexia về ; Bash nhảy xa tới , . Alexia tới đó và bắt được Bash. |
Bình luận