BUBGAME - Bubbies Game
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

Ngoài trò chơi với bảng số, Vasya còn gửi cho An một trò chơi khác có tên là Bubbies Game. Trong game, Bubbies nhìn giống như một con sâu được tạo thành bởi B hình tròn bằng nhau (giống như những quả bong bóng, vì vậy mà nó có tên là Bubbies) và có L cái chân. Các chân này có thể di chuyển từ hình tròn này sang hình tròn khác, tuy nhiên tất cả các chân phải nằm dưới các hình tròn, mỗi hình tròn chỉ có thể chứa tối đa 1 chân và khi các chân duy chuyển, chân sau không được vượt lên, nằm ở các hình tròn phía trước cái chân nằm liền trước nó.

Nhiệm vụ của trò chơi là phải đưa Bubbies đi qua một cây cầu cũ kỹ có độ dài N. Cây cầu cũng được chia thành N đoạn, mỗi đoạn có thể có các tấm ván lót hoặc không (tấm ván lót tại vị trí đó đã bị hỏng theo thời gian). Tại mỗi thời điểm, Bubbies có thể thực hiện một trong hai hành động sau:

 - Di chuyển một chân của nó đến một vị trí nào đó thỏa mãn các yêu cầu trên.

 - Di chuyển thân của nó (vị trí của các chân được giữ nguyên, hay nói cách khác là cho thân của nó trượt trên các chân) lên trước một đơn vị và vẫn phải thỏa mãn các yêu cầu trên.

Ban đầu Bubbies đứng ở bên trái cầu và thân của nó trải dài trên B miếng ván đầu tiên bên trái của cây cầu. Các chân của nó nằm ở L vị trí đầu tiên của cây cầu. Bubbies được xem là đi hết cây cầu nếu như thân của nó nằm ở B vị trí tận cùng bên phải của cây cầu và các chân của nó nằm ở L vị trí tận cùng bên phải của cây cầu.

Yêu cầu của trò chơi là phải tìm ra số hành động ít nhất của Bubbies để nó có thể đi đến đầu bên kia của cây cầu. Mặc dù rất hứng thú với trò chơi, nhưng An lại không thể tìm ra cách đi tối ưu nhất cho Bubbies, một lí do khác là sau khi các bạn NTUCoder giúp cậu ta viết chương trình kiểm tra đáp án của trò chơi với bảng số nên cậu ta đang mãi mê phá đảo trò chơi đó nên lại phải nhờ đến các bạn tìm ra đáp án cho trò chơi này. Hãy giúp cậu ta thêm một lần nữa nhé.

Dữ liệu nhập: Dòng đầu tiên chứa một số nguyên dương T - số lượng test case (T ≤ 10). Mỗi test case được biểu diễn trên 2 dòng:

 - Dòng đầu tiên chứa 3 số nguyên dương L, B, N (1 ≤ L ≤ B ≤ N ≤ 106).

 - Dòng thứ hai chứa N kí tự '0' và '1', kí tự thứ i là '1' nếu vị trí thứ i của cây cầu còn nguyên vẹn và '0' nếu nó đã bị hỏng.

Dữ liệu xuất: với mỗi test case xuất ra số hành động ít nhất để Bubbies có thể đi sang đầu kia của cây cầu. Nếu không thể đi qua bên kia cầu, xuất ra -1.

Ví dụ

  • input
    3
    1 2 2
    11
    2 3 5
    11011
    1 3 5
    11011
    output
    1
    -1
    5
Back to Top