HSG12 Long An 2015 - Vòng 1 - Bảng A - Bài 1
View as PDFTrong trò chơi Zuma, cho một dãy các viên bi có bốn màu bất kỳ là: xanh, đỏ, tím, vàng liên tiếp nhau. Chú ếch Zuma sẽ bắn một viên bi (cũng có màu là một trong bốn màu trên) chèn vào dãy. Nếu viên bi mới chèn vào kết hợp với các viên bi bên trái hoặc bên phải vị trí chèn tạo ra một dãy có từ ba viên bi cùng màu trở lên thì chú ếch sẽ ăn được các viên bi cùng màu đó. Các viên bi còn lại sẽ sáp nhập lại, nếu tại vị trí sáp nhập tạo ra một dãy có từ ba viên bi cùng màu trở lên thì chú lại tiếp tục được ăn. Cứ như vậy cho đến khi không còn dãy ba viên bi cùng màu trở lên tạo ra từ vị trí sáp nhập.
Ví dụ: Cho dãy ~11~ viên bi như sau (X: xanh, D: đỏ, T: tím, V: vàng): TTXDDXXXVVV
Zuma bắn một viên bi màu đỏ vào vị trí thứ ~4~ sẽ tạo ra dãy bi sau (bi đỏ được chèn vào vị trí thứ ~4~): TTXDDDXXXVVV.
Bi bắn vào tạo ra dãy ~3~ bi đỏ, như vậy chú ăn được ~3~ bi đỏ, dãy còn lại là: TTXXXXVVV. Một bi xanh bên trái sáp nhập với ba bi xanh bên phải tạo thành một dãy ~4~ bi xanh nên Zuma ăn tiếp ~4~ bi này, dãy còn lại là: TTVVV (Dù dãy này có ~3~ bi vàng nhưng không được ăn vì ~3~ bi này không phải do sáp nhập từ hai phía). Vậy Zuma ăn được tổng cộng ~7~ bi (~3~ đỏ, ~4~ xanh).
Yêu cầu:
Cho trước dãy bi có bốn màu X, D, T, V bất kỳ và một viên bi dùng để bắn ra có một trong bốn màu trên và vị trí ~k~ chú ếch sẽ bắn, bạn hãy giúp Zuma tính xem ăn được bao nhiêu viên bi khi bắn vào vị trí ~ k~.
Dữ liệu vào
- Dòng đầu tiên gồm dãy ký tự
X,D,T,Vbiểu thị màu sắc các viên bi. Các ký tự được viết sát nhau . - Dòng thứ hai là một số nguyên ~k~ (~1 \leq k \leq ~ chiều dài của dãy bi) là vị trí bắn và một ký tự là một trong bốn ký tự
X,D,T,V).
Kết quả ra:
Tổng số viên bi mà Zuma ăn được.
Sample Input
TTXDDXXXVVV
4 D
Sample Output
7
Comments
oh no!!!!
Kho qua di thoi