{"problem":{"name":"[SNCPC2019] Turn It Off","description":{"content":"It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off. There are $n$ lights, numbered from 1 to $n$, ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9644"},"statements":[{"statement_type":"Markdown","content":"It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.\n\nThere are $n$ lights, numbered from 1 to $n$, arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer $i$ and turn all the lights numbered from $i$ to $(i+L-1)$ (both inclusive) off, where $L$ is a predefined positive integer. Note that each time the value of $L$ must be the same.\n\nGiven the initial status of all the lights, please help BaoBao determine the smallest possible $L$ so that he can turn all the lights off within $k$ times.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $k$ ($1 \\le k \\le n \\le 2 \\times 10^5$).\n\nThe second line contains a string $s$ ($|s| = n$, $s \\in \\{\\text{`0'}, \\text{`1'}\\}$) indicating the initial status of the lights. Let $s_i$ be the $i$-th character in $s$, if $s_i = \\text{`1'}$ then the $i$-th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one `1· in $s$.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $2 \\times 10^6$.\n\n## Output\n\nFor each test case output one line containing one integer, indicating the smallest possible $L$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9644","tags":["2019","二分","O2优化","陕西","省赛/邀请赛"],"sample_group":[["2\n10 4\n0101011111\n3 1\n010","3\n1"]],"created_at":"2026-03-03 11:09:25"}}