CCC Bad Haha Solution | Canada Day Contest 2021

CCC Bad Haha Solution

Lookcook the geniosity easily finished the Canadian Computing Competition this year and got a score of nn. He wants to reduce his score to avoid going to CCO and having to meet AQT. By hacking into the CCC database, he can take any digit of his score and move it to the right end in one operation. However, he can only make up to KK operations before he is caught. What’s the minimum score he can end up with?

See Also : Canada Day Contest 2021

Input Specification

The first line contains TT, the number of test cases.

Then TT test cases follow.

The first line of each case contains nn, an integer containing only digits from 11 to 99.

The second line contains KK, the number of digits you can move.

Output Specification

The smallest number that can be obtained by moving at most KK digits of nn to the end.

Constraints

1≤T≤1000001≤T≤100000

2≤n≤101000002≤n≤10100000

0≤K≤1000000≤K≤100000

nn will not contain zeroes, all digits will be from 11 to 99.

The product of nn across all test cases will not exceed 1010000010100000.

Sample Input

8
891
0
891
1
891
2
51111
100
98614
3
9921991111
5
1324331974
8
2364851699
5

Sample Output

891
819
189
11115
14689
1111129999
1123334479
2169934568

Hint

In what cases will operating on digit increase the number?Copy

**Hint**

When the digit is larger than the one after it.

Hint
The earlier digits always make a bigger difference than the later ones.

Solution Given KK moves, Lookcook should move back the first KK digits that are larger than the digit after it. These KK digits can be found by keeping a monotonically nondecreasing stack. After finding these KK values, move them in nondecreasing order (move the smallest of the KK digits first and the largest last). This takes O(nlogn)O(nlog⁡n) time for an nn digit number.

Example

1
26451689
5

66 is bigger than 44. So 66 should be one of the digits that gets moved. The resulting number is 24516892451689.

55 is bigger than 11, so it should be moved. The resulting number is 241689241689.

Now that 11 is directly after 44, 44 should be moved. This leaves 2168921689.

Now that 11 is directly after 22, 22 should be moved. This leaves 16891689.

99 is the last element. But we know that we will move 22 to the end, and it will be smaller than 99. So 99 should also be moved, leaving 168168.

88 Should be moved for the same reason as 99, but we’ve used up all our 55 operations, so we stop now.

The KK digits we’ve selected are {6,5,4,2,9}{6,5,4,2,9}. They should be moved in the nondecreasing order 2,4,5,6,92,4,5,6,9, giving the result as 1682456916824569.

Leave a Comment