CANDY - Kẹo ba màu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Nói đến bài thơ thằng Bờm, không ai trong chúng ta là không biết tới. Nhưng câu chuyện ngày hôm nay thì lại khác, Phú Ông muốn đổi cây quạt mo của Bờm, sau khi ra đủ điều kiện "Ba bò chín trâu", "Ao sâu cá mè" mà Bờm không đồng ý, Phú Ông phát hiện ra lý do Bờm không đồng ý đổi những món đó là do Bờm là con nít và chỉ thích ăn kẹo thôi, và sau đó Phú Ông đề nghị đổi cây quạt mo của Bờm lấy kẹo thì Bờm đồng ý ngay. Tuy nhiên vị Phú Ông keo kiệt không muốn cho Bờm quá nhiều kẹo, thế là ông ta nghĩ ra một trò chơi để làm Bờm không lấy được nhiều kẹo như sau:

Phú ông có N viên kẹo, xếp thành một hàng ngang. Tổng cộng có 3 loại màu kẹo khác nhau: Đỏ, VàngXanh. Mỗi lượt chơi diễn ra như sau:

 - Nếu chỉ còn 1 viên kẹo duy nhất thì trò chơi kết thúc.

 - Nếu dãy kẹo còn N (N ≥ 2) viên kẹo, Bờm sẽ được chọn 2 viên kẹo liên tiếp khác màu nhau và lấy được 2 viên kẹo đó. Tuy nhiên sau đó Bờm phải đặt 1 viên kẹo khác màu với màu của 2 viên kẹo vừa lấy được vào lại vị trí vừa lấy 2 viên kẹo ra và dãy kẹo sẽ còn lại N-1 viên. Ví dụ Bờm lấy 2 viên kẹo màu Đỏ và Vàng thì Bờm phải đặt lại 1 viên kẹo màu Xanh...

 - Nếu Bờm không có cách nào để chọn 2 viện kẹo liên tiếp khác màu thì trò chơi sẽ kết thúc.

Bờm hiện không có viên kẹo nào, do đó trước khi chơi trò chơi Bờm có thể mượn Phú Ông một số kẹo nhất định nhưng sau khi kết thúc trò chơi Bờm phải trả lại đúng số lượng kẹo này cho Phú Ông. Phú Ông không quan tâm về màu kẹo mà chỉ quan tâm đến số lượng viên kẹo mà Bờm trả lại có bằng số lượng kẹo mà Bờm đã mượn hay không, điều đó có nghĩa là nếu đầu trò chơi Bờm mượn 2 viên kẹo màu Đỏ thì cuối trò chơi Bờm có thể trả lại cho Phú Ông 2 viện kẹo màu Xanh cũng được.

Ví dụ: ban đầu Phú Ông có 3 viên kẹo từ trái sang phải lần lợt là {Đỏ, Xanh, Vàng}

  • Trước khi bắt đầu, Bờm mượn của Phú Ông 1 viên kẹo màu Vàng.
  • Ở lượt chơi đầu tiên, Bờm lấy ra 2 viện kẹo liên tiếp ở vị trí thứ 1 và 2 từ trái sang: [Đỏ, Xanh], Bờm phải đặt lại viên kẹo màu Vàng. Dãy còn lại 2 viên kẹo [Vàng, Vàng].
  • Lượt tiếp theo, Bờm không thể chọn được 2 viên kẹo liên tiếp khác màu và trò chơi kết thúc. Lúc này Bờm có 2 viên kẹo: Đỏ, Xanh, Bờm phải trả lại cho Phú Ông 1 viên kẹo. Kết quả là Bờm lấy được của Phú Ông 1 viên kẹo.

Gặp trò chơi hóc búa mà Phú Ông đưa ra. Bờm không biết nên chơi như thế nào để lấy được nhiều kẹo của Phú Ông nhất. Biết được màu sắc của N viên kẹo từ trái sang phải, bạn hãy giúp Bờm tìm ra cách chơi để lấy được nhiều kẹo từ Phú Ông nhất nhé.

Dữ liệu nhập: Dòng đầu tiên chứa số nguyên T - Số lượng test case (1 ≤ ≤ 10). Tiếp theo là 2*T dòng, mỗi 2 dòng thể hiện cho 1 test case:

  • Dòng đầu tiên chứa số nguyên N - số lượng viên kẹo  (1 ≤ ≤ 100).
  • Dòng thứ 2 chữa một xâu N kí tự thể hiện màu của N viên kẹo từ trái sang phải. Xâu chỉ gồm 3 kí tự 'D', 'V' và 'X' tượng trưng cho ;ần lượt 3 màu: Đỏ, Vàng và Xanh của viên kẹo.

Dữ liệu xuất: Gồm T dòng, mỗi dòng là kết quả của test case tương ứng, chứa một số nguyên duy nhất là số kẹo mà Bờm có thể lấy được nhiều nhất từ Phú Ông.

Ví dụ

  • input
    3
    3
    DXV
    4
    DXVD
    5
    DDDDD
    output
    1
    3
    0

Đề thi Olympic tin học trường Đại học Khoa Học Tự Nhiên thành phố Hồ Chí Minh năm 2014 - bảng Chuyên Tin

Back to Top