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ứ 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ó 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 viên ngọc bích xanh (green jade) và viên ngọc thạch đỏ (red jasper). viên đá được xâu thành một chuỗi vòng lớn và được đánh số từ đến theo chiều kim đồng hồ (viên thứ kề với viên thứ , và viên thứ kề với viên thứ ). Đặc biệt, không có ba viên liên tiếp nào cùng loại. Biboo muốn làm món quà thuộc hai loại sau ( 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 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 (): số bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa số nguyên ().
- Dòng thứ hai chứa xâu độ dài mô tả chuỗi đá. Ký tự thứ là g nếu viên thứ là ngọc bích xanh, và là r nếu viên thứ là ngọc thạch đỏ.
Với mỗi bộ test, dữ liệu đảm bảo:
- Có đúng viên xanh và 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 trên tất cả các bộ test không vượt quá .
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 số nguyên (), trong đó 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ứ . 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
- , tổng trên tất cả các bộ test không vượt quá
- có đúng ký tự g và 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 (g r g) làm quà loại A, còn lại các viên là g r r theo vòng. Sau đó gỡ các viên (r g r) làm quà loại B. Chú ý chọn các viên 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 (g r g), còn lại là r r g theo vòng, rồi gỡ (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