trang chủ / đề bài / icpc26_nat_f

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 (x,y) có tọa độ nguyên thỏa mãn |x|≤109 và |y|≤109.

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ứ 1,3,5,… (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ứ 2,4,6,… (nhảy gần), nếu Bash đang ở (x,y), hắn di chuyển tới một điểm (x′,y′) đượ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 |x−x′|+|y−y′|≤106.

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 (xA,yA) và (xB,yB) 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à (xA−xB)2+(yA−yB)2. 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 (xA−xB)2+(yA−yB)2 trước hết được làm tròn tới bội số gần nhất của 1000 (nếu khoảng cách nằm chính giữa hai bội số liên tiếp của 1000 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 4020041≈2005,004 được làm tròn thành 2000, và Alexia biết được 20002=4000000.

Ban đầu, Alexia ở (0,0) 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á 2000 lần di chuyển.

Tương tác

Đầu tiên, chương trình đọc số bộ test τ (1≤τ≤100). Với mỗi bộ test:

  • Đầu tiên, chương trình đọc một số nguyên d: bình phương khoảng cách giữa vị trí ban đầu (0,0) của Alexia và vị trí ban đầu của Bash.
  • Sau đó chương trình thực hiện không quá 2000 lần di chuyển. Với mỗi lần di chuyển:
    • Chương trình in ra hai số nguyên x và y (|x|≤109, |y|≤109), nghĩa là Alexia di chuyển tới (x,y).
    • Chương trình đọc một số nguyên d: bình phương khoảng cách giữa Alexia và Bash sau khi Alexia di chuyển. Nếu d=0, 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 d: 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 1000 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ứ 2000, trình tương tác in ra −1 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

  • 1≤τ≤100
  • Mọi điểm của Alexia và Bash có tọa độ nguyên, |x|≤109, |y|≤109.
  • Mỗi bộ test được di chuyển không quá 2000 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 ở (3,−4), d=25. Alexia di chuyển tới (109,109), khoảng cách tới (3,−4) có bình phương 2000000002000000025. Bash nhảy xa tới (999999995,109), d=25. Alexia di chuyển tới (999999995,109) và bắt được Bash (d=0).
1
4073
2000000030000004073
1999999972000000100
961330542669438760
961327303729000000
1999995972004032100
50
0
1000000000 1000000000
-409979200 890644490
1000000000 1000000000
999999993 999999999
Bash ban đầu ở (37,−52), d=4073. Alexia tới (109,109); Bash nhảy xa tới (6,8). Alexia tới (−409979200,890644490), Bash không ở đó (d=961330542669438760); Bash nhảy gần tới (6,2008), khoảng cách ≈980472834,96 được làm tròn thành 980473000, nên Alexia đọc được 9804730002=961327303729000000. Alexia về (109,109); Bash nhảy xa tới (999999993,999999999), d=50. Alexia tới đó và bắt được Bash.

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