oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

penguins Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

penguin.html

Problem Description

Yu Peng the Penguin is taking photos with his penguin friends today! Penguins have white bellies and black wings and back, and as penguins are more or less of the same height, the photos taken can be represented as a binary string, where '0' denotes a black pixel and '1' denotes a white pixel.

Yu Peng has taken T photos, where the ith photo is of length Ni. He tells you that in the ith photo, there are at most Ki penguins. Yu Peng recognises a penguin as a contiguous segment of white pixels (penguin with belly facing front), or a contiguous segment of black pixels (penguin with back facing front), both of arbitrary length. However, some naughty penguins faced the camera sideways when the photos were taken, and hence, there may be more than Ki penguins in the ith photo, according to Yu Peng's rules.

Yu Peng is not happy with these naughty penguins and wants to edit the photos. He wonders, for the ith photo, what is the minimum number of pixels that he has to change the colour of, such that he sees at most Ki penguins in the photo.

Input

The first line contains a single integer T, the number of photos.

Then, there are T pairs of lines, each describing a single photo taken.

For the ith pair of lines:

The first line contains two integers Ni and Ki.

The second line contains a binary string of length Ni.

Output

Output T lines. The ith line should contain a binary string of length Ni, describing the ith edited photo, according to Yu Peng's requirements.

If there are several possible optimal edited photos, output any of them.

Limits

Subtask 1 (11%): 1 ≤ Ki ≤ Ni ≤ 10. 1 ≤ ∑ Ni ≤ 5000.

Subtask 2 (24%): 1 ≤ Ki ≤ Ni ≤ 100. 1 ≤ ∑ Ni ≤ 5000.

Subtask 3 (24%): 1 ≤ Ki ≤ Ni ≤ 1000. 1 ≤ ∑ Ni ≤ 50 000.

Subtask 4 (21%): 1 ≤ Ki ≤ 5000. 1 ≤ ∑ Ni ≤ 100 000.

Subtask 5 (20%): 1 ≤ Ki ≤ 200 000. 1 ≤ ∑ Ni ≤ 200 000.

Subtask 6 (0%): Sample Testcases

Sample Testcase 1

Input

3
9 3
000111000
10 3
0111011010
4 4
0001

Output

000111000
0111111000
0001

Tags

ROI 2015

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
111342s512MBMinimum
224452s512MBMinimum
324572s512MBMinimum
421692s512MBMinimum
520902s512MBMinimum
6012s512MBMinimum

Judge Compile Command

g++-8 ans.cpp -o penguins -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.