trang chủ / đề bài / icpc25_nat_l

Giai đoạn đi đường

Đề bài

Mô tả

Năm 2030. Kiaya, một trong những tuyển thủ Leaf of Lemons giàu thành tích nhất thế giới, vào hàng chờ một trận xếp hạng để chuẩn bị cho giải đấu sắp tới. Trên màn hình chờ, một cái tên quen thuộc xuất hiện. Kiaya không tin vào mắt mình. Đối đầu với anh ở đường trên là Zeros the GOAT, đồng đội cũ của anh, từng được coi là tài năng trẻ triển vọng nhất của trò chơi, nhưng đáng tiếc đã bị cấm thi đấu từ nhiều năm trước vì hàng loạt bê bối. (GOAT là viết tắt của "Globally banned frOm All compeTitions", không hẳn như bạn nghĩ...)

"Chúc một trận đấu hay, ông già" (Kiaya lẩm bẩm khi điều khiển tướng của mình lên đường trên). Zeros đã ở trong tầm mắt, vẫn nhảy những điệu nhảy khiêu khích như hồi hai người còn trẻ.

Trong Leaf of Lemons, giai đoạn đầu của trận đấu gọi là giai đoạn đi đường, khi các tuyển thủ đối đầu với đối thủ ở một trong ba đường: trên, giữa và dưới. Để đơn giản, đường trên nơi Kiaya và Zeros giao chiến được mô tả là một dải gồm n ô đánh số từ 1 đến n. Hiện tại, tướng của Kiaya và Zeros lần lượt ở ô x và ô y (1≤x<y≤n). Hai người lần lượt di chuyển, Kiaya đi trước.

Đến lượt mình, người chơi đang ở vị trí p bắt buộc phải lướt tướng của mình bằng cách chọn một số nguyên khác 0 là k sao cho:

  • −a≤k≤a với Kiaya, −b≤k≤b với Zeros;
  • 1≤p+k≤n.

Sau khi lướt, vị trí mới của người đó là p+k.

Hơn nữa, vì cả hai đều là những tuyển thủ cực kỳ xuất sắc, nếu một người lướt tướng vào hoặc vượt qua đối thủ, người đó sẽ bị hạ gục ngay lập tức. Do đó, người chơi nào buộc được đối thủ phải lướt vào hoặc vượt qua tướng của mình sẽ thắng giai đoạn đi đường. Chính xác hơn, một người chơi lướt vào hoặc vượt qua đối thủ khi và chỉ khi sau lượt của người đó, vị trí của Kiaya lớn hơn hoặc bằng vị trí của Zeros.

Cho trạng thái hiện tại của đường trên, Kiaya muốn biết ai (nếu có) sẽ thắng giai đoạn đi đường, giả sử cả hai đều chơi tối ưu. Hãy giúp anh ấy!

Dữ liệu vào

Dòng đầu tiên chứa τ (1≤τ≤105): số bộ dữ liệu. Tiếp theo là τ bộ dữ liệu, mỗi bộ trên một dòng gồm năm số nguyên n,x,y,a,b (2≤n≤109, 1≤x<y≤n, 1≤a,b<n): số ô trên đường, vị trí xuất phát của Kiaya và Zeros, và số bước tối đa trong một lượt của Kiaya và Zeros.

Dữ liệu ra

Với mỗi bộ dữ liệu:

  • nếu Kiaya có chiến thuật thắng, in ra Kiaya;
  • nếu Zeros có chiến thuật thắng, in ra Zeros;
  • nếu không ai có chiến thuật thắng, in ra Draw.

Ràng buộc

  • 1≤τ≤105.
  • 2≤n≤109, 1≤x<y≤n, 1≤a,b<n.

Ví dụ

Input Output Giải thích
3
3 2 3 2 1
4 3 4 2 1
999 1 999 1 1
Zeros
Kiaya
Kiaya
Bộ thứ nhất: Kiaya buộc phải lùi một bước về ô 1; Zeros thắng bằng cách đi tới ô 2, buộc Kiaya phải lướt vào hoặc vượt qua anh ở lượt sau. Bộ thứ hai: Kiaya đi về ô 1; Zeros buộc phải đi tới ô 3; Kiaya đi tới ô 2; Zeros buộc phải đi tới ô 4; Kiaya đi tới ô 3, buộc Zeros phải lướt vào anh ở lượt sau. Bộ thứ ba: có thể chứng minh Kiaya thắng bằng cách luôn tiến lên một bước, bất kể Zeros làm gì.
4
10 4 7 2 2
10 9 10 3 1
10 6 8 2 5
10 6 8 1 5
Kiaya
Kiaya
Kiaya
Zeros
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ ba: Kiaya đi tới ô 7; Zeros buộc phải lùi về ô 9 hoặc 10, Kiaya luôn theo sát được (mỗi lượt đi tới 2 ô) cho đến khi Zeros bị dồn vào ô 10 với Kiaya ở ô 9. Bộ thứ tư: Kiaya chỉ đi được 1 bước nên không theo kịp khi Zeros lùi 2 bước.

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