trang chủ / đề bài / icpc24_nat_j

Chuỗi đá quý

Đề bài

Mô tả

Kosexy Biboo, một trong những nhà sưu tầm sỏi nổi tiếng nhất thế giới, đang ăn mừng viên sỏi thứ 700000 trong bộ sưu tập! Để cảm ơn những người đã ủng hộ mình, Biboo dự định tặng quà lưu niệm cho các người hâm mộ. Vì sỏi quá quý giá nên không hợp để làm quà, cô quyết định dùng bộ sưu tập khác của mình: đá quý.

Có 2·n người hâm mộ, mỗi người nhận một món quà. Thật trùng hợp, bộ sưu tập đá quý của Biboo gồm đúng 3·n viên ngọc bích xanh (green jade) và 3·n viên ngọc thạch đỏ (red jasper). 6·n viên đá được xâu thành một chuỗi vòng lớn và được đánh số từ 1 đến 6·n theo chiều kim đồng hồ (viên thứ i kề với viên thứ i+1, và viên thứ 6·n kề với viên thứ 1). Đặc biệt, không có ba viên liên tiếp nào cùng loại. Biboo muốn làm 2·n món quà thuộc hai loại sau (n món mỗi loại):

  • Loại A gồm một viên xanh, một viên đỏ, một viên xanh theo đúng thứ tự đó.
  • Loại B gồm một viên đỏ, một viên xanh, một viên đỏ theo đúng thứ tự đó.

Vì việc gỡ đá khỏi bộ sưu tập để làm quà tốn thời gian, mỗi lần Biboo chỉ có thể chọn ba viên đá liên tiếp (theo chiều kim đồng hồ) để làm một món quà. Lưu ý rằng sau khi gỡ một số viên, các viên còn lại sẽ trở nên kề nhau. Ngoài ra, vì Biboo khó theo dõi số lượng quà mỗi loại (cô đang học đếm), cô quyết định làm một món loại A, rồi một món loại B, rồi một món loại A, và cứ thế luân phiên cho đến khi dùng hết 6·n viên đá.

Cho cấu hình ban đầu của bộ sưu tập, hãy giúp Biboo tìm cách làm các món quà theo yêu cầu, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤10000): số bộ test. Mỗi bộ test gồm:

  • Dòng thứ nhất chứa số nguyên n (1≤n≤100000).
  • Dòng thứ hai chứa xâu s độ dài 6·n mô tả chuỗi đá. Ký tự thứ i là g nếu viên thứ i là ngọc bích xanh, và là r nếu viên thứ i là ngọc thạch đỏ.

Với mỗi bộ test, dữ liệu đảm bảo:

  • Có đúng 3·n viên xanh và 3·n viên đỏ.
  • Không có ba viên liên tiếp nào (tính cả vòng) cùng loại.

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 100000.

Dữ liệu ra

Với mỗi bộ test, nếu không thể làm các món quà theo yêu cầu, in ra "NO" (không có dấu ngoặc kép).

Ngược lại, in ra "YES" (không có dấu ngoặc kép). Dòng tiếp theo in ra 2·n số nguyên a1,a2,…,a2·n (1≤ai≤6·n), trong đó ai là số hiệu của viên đá đầu tiên (theo chiều kim đồng hồ) trong ba viên Biboo gỡ ra để làm món quà thứ i. Lưu ý: in số hiệu của viên đá trong cấu hình ban đầu, không phải vị trí hiện tại của nó.

Nếu có nhiều cách thỏa mãn, in ra một cách bất kỳ.

Ràng buộc

  • 1≤t≤10000
  • 1≤n≤100000, tổng n trên tất cả các bộ test không vượt quá 100000
  • s có đúng 3·n ký tự g và 3·n ký tự r, không có ba ký tự liên tiếp (tính cả vòng) giống nhau

Ví dụ

Input Output Giải thích
2
1
ggrrgr
2
grrggrrggrrg
YES
5 4
NO
Bộ test thứ nhất: gỡ các viên 5,6,1 (g r g) làm quà loại A, còn lại các viên 2,3,4 là g r r theo vòng. Sau đó gỡ các viên 4,2,3 (r g r) làm quà loại B. Chú ý chọn các viên 2,3,4 sẽ được g r r, không phải loại B. Bộ test thứ hai: ngay từ đầu không có ba viên liên tiếp nào là g r g.
4
1
grgrgr
1
ggrgrr
2
ggrrggrrgrgr
2
ggrrggrrggrr
YES
1 4
YES
2 6
YES
11 10 9 8
NO
Bộ test thứ hai: gỡ các viên 2,3,4 (g r g), còn lại 5,6,1 là r r g theo vòng, rồi gỡ 6,1,5 (r g r). Bộ test thứ tư: không có ba viên liên tiếp nào là g r g.

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