Scan the digits from left to right. Insert the new digit before the first digit smaller than it because placing it before a smaller digit maximizes the overall value by ensuring that the new digit occupies a higher significant position in the resulting number. This positioning ensures that the number formed is as large as possible. If no smaller digit is found, append the new digit at the end.

for i in range(int(input())):
    n, d = list(map(int, input().split()))
    s = input()
 
    flag = True
    for i in range(len(s)):
        if int(s[i]) < d:
            print(s[:i] + str(d) + s[i:])
            flag = False
            break
    
    if flag:
        print(s + str(d))

We can precalculate a prefix sum array $$$sum$$$ over the piles. I.e. $$$sum_{i} = a_{1} + a_{2} + ... + a_{i}$$$. We can now perform a binary search for each query $$$q_{i}$$$ to find the result $$$j$$$ with the properties $$$sum_{j - 1} < q_{i}$$$ and $$$sum_{j} ≥ q_{i}$$$.

Time complexity $$$O(n + m·log(n))$$$

n = int(input())
a = list(map(int, input().split()))
m = int(input())
q = list(map(int, input().split()))


prefix_sum = [0]
for pile in a:
    prefix_sum.append(prefix_sum[-1] + pile)


for label in q:
    low = 0
    high = n

    while low <= high:
        mid = low + (high - low)//2
        if prefix_sum[mid] < label:
            low = mid + 1
        
        else:
            high = mid - 1
    
    print(low)

We are given $$$s$$$ spaceships, each with an attacking power $$$a_i$$$, and $$$b$$$ bases, each with a defensive power $$$d_j$$$ and gold $$$g_j$$$.

We are asked to output for each spaceship, the sum of the gold of the bases it can attack, that is: $$$res(i) = \sum g_j, ∀_j : a_i ≥ d_j$$$

An $$$O(sb)$$$ solution would not pass the time limit. Instead the intended solution is to sort the bases by their defensive power, and the ships by their attacking power, in increasing order. Then, we can use the fact that if a weaker ship can attack a base, so can a stronger ship. This way we only have to iterate once over all the bases. The overall complexity reduces to $$$O((s) log (s) + (b) log (b))$$$.

Another solution of that would pass the time limit would be to sort the bases in increasing order of their defensive strength. Then, compute the prefix sum of the gold (that is, $$$prefix[j]$$$ would hold the sum of gold of all the bases from $$$0...j$$$). Finally, for each ship, perform a binary search over the prefix sum and the bases arrays to compute how much gold it could steal.

Overall complexity: $$$O((s) log (b) + (b) log (b))$$$.

from bisect import bisect_right
from sys import stdin


def input(): return stdin.readline()[:-1]


S, B = map(int, input().split())
a = list(map(int, input().split()))
dg = []
for _ in range(B):
    d, g = map(int, input().split())
    dg.append((d, g))

dg.sort()
pref_sum = [0]
cur_sum = 0
ds = []
for d, g in dg:
    ds.append(d)
    cur_sum += g
    pref_sum.append(cur_sum)

ans = []
for ai in a:
    idx = bisect_right(ds, ai)
    ans.append(pref_sum[idx])
print(*ans)

Since we are sure that if $$$x$$$ can be the answer to the problem, then every value below $$$x$$$ can be the answer, So we can use binary search on the answer to solve the problem.

To check whether some value $$$x$$$ can be a valid solution, we have to sum all our gains that come from values greater than $$$x$$$. We can calculate the gain for one value by taking its difference with $$$x$$$. Let's say its difference is $$$diff$$$. Our gain will be $$$diff - (diff * k / 100)$$$. We can do the same for all values greater than $$$x$$$ and add the results; that will be our total gain. We also need to calculate the total need. We can do that for values less than $$$x$$$ by taking their difference with $$$x$$$ and adding those values. Then, we can compare if our total gain is greater than or equal to our total need. In that case, it can be considered valid.

import sys
n, k = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))

def chekcker(x):
    gain = 0
    need = 0
    for num in nums:
        if num > x:
            diff = num - x
            gain += (diff - diff * k / 100)
        if num < x:
            need  += (x - num)
    
    return gain >= need

low = min(nums)
high = max(nums)
while high  - low > 10 ** -7:
    mid = (high + low) / 2
    if chekcker(mid):
        low = mid
    else:
        high = mid
print(high)

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

If there is more than one section between the two we want to break, then any shot hits only one of these sections, so each shot should be aimed at one of those sections, and we break them independently. Since one doesn’t affect the other, we could just pick the two minimum and try to break them independently, let's say their strength is $$$a_i$$$ and $$$a_j$$$, the total is going to be $$$\lceil\frac{a_i}{2}\rceil + \lceil\frac{a_j}{2}\rceil$$$.

If there is only one section between them, if we shoot at the section between them, we deal 1 damage to both sections; if we shoot at one of those sections, we deal 2 damage to it and 0 damage to the other section. So, each shot distributes 2 damage between these two sections the way we want to distribute it, and the number of shots required to break these two sections is $$$\lceil\frac{a_i + a_{i+2}}{2}\rceil$$$.

The case when we try to break two adjacent sections is the trickiest one. Let's say that these sections are $$$i$$$ and $$$i+1$$$, $$$x=\max(a_i, a_{i+1})$$$, and $$$y=\min(a_i, a_{i+1})$$$. If we target one of these sections, we deal 2 damage to it and 1 damage to the other section. Let's try to run the following algorithm: shoot at the section with higher durability until both of them break. It can be slow, but we can see that after the first $$$x-y$$$ shots, the durabilities of the sections become equal, and each pair of shots after that deals 3 damage to both sections. So, we can model the first $$$x-y$$$ shots, subtract $$$2(x-y)$$$ from $$$x$$$ and $$$(x-y)$$$ from $$$y$$$, and then we'll need $$$\lceil\frac{x+y}{3}\rceil$$$ shots. The only case when this doesn't work is if we break both sections before we equalize their durabilities; it means that $$$2y \leq x$$$, and we need to do only $$$\lceil\frac{x}{2}\rceil$$$ shots.

from math import ceil
def check(a, mid):
	n = len(a)
	local_min = a[0]

	for i in range(1, n - 1):
    	   x = max(a[i], a[i - 1])
    	   y = min(a[i], a[i - 1])

    	   # case one using the two min values
    	   if (ceil(local_min / 2) + ceil(a[i] / 2)) <= mid:
        	return True

    	   # case two using i, i + 2
    	   elif (ceil((a[i - 1] + a[i + 1]) / 2)) <= mid:
        	return True

    	   # case 3 using i, i + 1
    	   elif max(ceil(x / 2), ceil((x + y) / 3)) <= mid:
        	return True

    	   # update local min
    	   local_min = min(local_min, a[i])

	return False


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	low, high, ans = 1, max(a), float('inf')
	a.append(1e7)
	while low <= high:
    	   mid = low + (high - low) // 2
    	   if check(a, mid):
        	ans = min(ans, mid)
        	high = mid - 1
    	   else:
        	low = mid + 1

	print(ans)


if __name__ == "__main__":
	solve()