# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* hjindal

*abhidot*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1143

# PREREQUISITES:

Greedy

# PROBLEM:

Given a binary string S, you can perform the following operations on it:

- Change a 0 to a 1
- Insert a 0 anywhere in the string

Find the maximum possible integer that can be formed after at most K operations.

# EXPLANATION:

Let X be the decimal value of the string.

Let’s see how the given operations affect the value of X.

- Suppose we change bit i from 0 to 1. This increases the value of X by 2^i.
- Suppose we insert a 0 after bit i. This doesn’t change anything about bits 0, 1, 2, \ldots, i-1, but shifts bits i, i+1, \ldots to the left by one step, i.e, multiplies their values by 2.

So, if Y is the total value of bits \geq Y, X will increase by exactly Y.

From this, it’s easy to see that whenever we insert a 0, it’s always optimal to do so at the end of the string, since it directly multiplies the value of X by 2.

So, we only need to decide when to insert a 0 and when to change a 0 into a 1.

In fact, this can be done greedily!

- If the leftmost character of S is 1, then insert a 0 at the end of S
- Otherwise, change the leftmost character of S to 1.

Each operation is easily performed in \mathcal{O}(1), so the final string can be found in \mathcal{O}(N+K).

# TIME COMPLEXITY

\mathcal{O}(N + K) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
s, k = input().split()
k = int(k)
s = list(s)
if s[0] == '0':
s[0] = '1'
k -= 1
s += ['0']*k
print(''.join(s))
```