Tôi có một dãy gồm \(N\) chữ số nhị phân. Tôi muốn tìm một đoạn con có đúng tỉ lệ số 0 và số 1 mong muốn; nhưng đoạn như vậy có thể không tồn tại, nên tôi chấp nhận một đoạn chỉ “khá tốt”.

Hãy tìm một đoạn con mà tỉ lệ các chữ số 1 gần phân số \(F\) đã cho nhất có thể. In chỉ số bắt đầu sớm nhất trong số các đoạn con đạt độ gần tối ưu.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,F\), rồi chuỗi \(N\) ký tự 0/1.

Dữ liệu ra

In Case #x: y, với \(y\) là chỉ số bắt đầu 0-based nhỏ nhất.

Ràng buộc

• \(1\le T\le100\), \(0\le F\le1\).

Phân nhóm

• Nhỏ: \(1\le N\le1000\).
• Lớn: \(1\le N\le500000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
12 0.666667
001001010111
11 0.400000
10000100011
9 0.000000
111110111
5 1.000000
00000
15 0.333333
000000000011000

Case #1: 5
Case #2: 5
Case #3: 5
Case #4: 0
Case #5: 6

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Pretty Good Proportion.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.