trang chủ / đề bài / icpc23_mn_a

Trò chơi với đàn bò

Đề bài

Mô tả

Hiếu và RR là hai cậu bé chăn bò làm việc ở một trang trại. Chuồng bò có 109 ô, đánh số từ 1 đến 109 từ trái sang phải. Mỗi ô chứa nhiều nhất một con bò.

Có N con bò được đánh số từ 1 đến N. Mỗi ngày lúc 3 giờ chiều, đàn bò từ bãi cỏ trở về chuồng. Mỗi con bò chọn ngẫu nhiên một ô: con bò thứ i vào ô ai, và các ai đôi một khác nhau.

Để việc cho ăn dễ hơn, Hiếu và RR muốn dồn tất cả N con bò sang trái (chiếm các ô từ 1 đến N). Hai bạn biến việc này thành một trò chơi, lần lượt đi theo lượt:

  • Hiếu đi trước.
  • Ở mỗi lượt, người chơi phải di chuyển con bò ở bên phải nhất (con bò ở ô max(ai)) đến một ô trống bất kỳ nằm bên trái nó.
  • Người không thể di chuyển được là người thua.

Cho vị trí ban đầu của N con bò, hãy xác định ai thắng nếu cả hai đều chơi tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T (1≤T≤105): số bộ test. Tiếp theo là mô tả các bộ test.

Mỗi bộ test gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên N (1≤N≤106): số con bò.
  • Dòng thứ hai chứa N số nguyên đôi một khác nhau a1,a2,…,aN (1≤ai≤109).

Dữ liệu đảm bảo tổng N của tất cả các bộ test không vượt quá 106.

Dữ liệu ra

Với mỗi bộ test, in ra Hieu nếu Hiếu thắng, hoặc RR nếu RR thắng, khi cả hai đều chơi tối ưu.

Ràng buộc

  • 1≤T≤105
  • 1≤N≤106, tổng N không vượt quá 106
  • 1≤ai≤109, các ai đôi một khác nhau

Ví dụ

Input Output Giải thích
4
2
3 4
3
1 2 4
3
1 3 5
5
1 2 3 4 5
RR
Hieu
Hieu
RR
Bộ test 1: Hiếu phải đưa con bò ở ô 4 về ô 1 hoặc 2; RR đưa con bò ở ô 3 về ô còn lại và Hiếu hết nước đi. Bộ test 2: Hiếu đưa con bò ở ô 4 về ô 3 là xong. Bộ test 4: các con bò đã ở ô 1 đến 5, Hiếu không đi được.
3
1
1
1
7
5
9 2 8 4 5
RR
Hieu
RR
Bộ test 2: Hiếu đưa con bò về ô 1. Bộ test 3: hai con bò trên cùng ở ô 8 và 9 liền nhau, bên trái ô 9 có 4 ô trống (1, 3, 6, 7).

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