Codeforces Round 893 (Div. 2) |
---|
Finished |
The teachers of the Summer Informatics School decided to plant $$$n$$$ trees in a row, and it was decided to plant only oaks and firs. To do this, they made a plan, which can be represented as a binary string $$$s$$$ of length $$$n$$$. If $$$s_i = 0$$$, then the $$$i$$$-th tree in the row should be an oak, and if $$$s_i = 1$$$, then the $$$i$$$-th tree in the row should be a fir.
The day of tree planting is tomorrow, and the day after tomorrow an inspector will come to the School. The inspector loves nature very much, and he will evaluate the beauty of the row as follows:
The teachers know the value of the parameter $$$a$$$, but for security reasons they cannot tell it to you. They only told you that $$$a$$$ is an integer from $$$1$$$ to $$$n$$$.
Since the trees have not yet been planted, the teachers decided to change the type of no more than $$$k$$$ trees to the opposite (i.e., change $$$s_i$$$ from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$ in the plan) in order to maximize the beauty of the row of trees according to the inspector.
For each integer $$$j$$$ from $$$1$$$ to $$$n$$$ answer the following question independently:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3000$$$, $$$0 \le k \le n$$$) — the number of trees in the row and the maximum number of changes.
The second line contains a string $$$s$$$ of length $$$n$$$, consisting of zeros and ones — the plan description.
It is guaranteed that the sum of all $$$n$$$ values for all test cases does not exceed $$$3000$$$.
For each test case, print $$$n$$$ integers, the $$$j$$$-th ($$$1 \le j \le n$$$) of which is the maximum beauty of the row of trees after no more than $$$k$$$ changes if $$$a = j$$$ is used to calculate the beauty.
53 01114 101105 0100006 21011017 10001101
3 3 3 4 5 7 9 5 9 13 17 21 6 9 13 17 21 25 7 10 13 17 21 25 29
In the first test case no changes are allowed, so $$$l_0 = 0$$$ and $$$l_1 = 3$$$ always hold. Thus, regardless of the value of $$$a$$$, the beauty of the row of trees will be $$$3$$$.
In the second test case for $$$a \in \{1, 2\}$$$ the teachers can, for example, change the plan $$$s$$$ to $$$0111$$$ (by changing $$$s_4$$$), and for $$$a \in \{3, 4\}$$$ — to $$$0010$$$ (by changing $$$s_2$$$). In this case, the beauty of the row for each $$$a$$$ is calculated as follows:
It can be shown that the changes described above are optimal for all $$$a$$$ from $$$1$$$ to $$$4$$$.
Name |
---|