A. Vadim's Collection
Source: codeforces
Tags: brute force, greedy

We call a phone number a beautiful if it is a string of $10$ digits, where the $i$-th digit from the left is at least $10 - i$. That is, the first digit must be at least $9$, the second at least $8$, $\ldots$, with the last digit being at least $0$.
For example, 9988776655 is a beautiful phone number, while 9099999999 is not, since the second digit, which is $0$, is less than $8$.
Vadim has a beautiful phone number. He wants to rearrange its digits in such a way that the result is the smallest possible beautiful phone number. Help Vadim solve this problem.
Please note that the phone numbers are compared as integers.

-----Input-----
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The only line of each test case contains a single string $s$ of length $10$, consisting of digits. It is guaranteed that $s$ is a beautiful phone number.

-----Output-----
For each test case, output a single string of length $10$ — the smallest possible beautiful phone number that Vadim can obtain.

-----Examples-----
Input:
4
9999999999
9988776655
9988776650
9899999999
Output:
9999999999
9876556789
9876567890
9899999999

-----Note-----
In the first test case, for the first phone number 9999999999, regardless of the rearrangement of digits, the same phone number is obtained.
In the second test case, for the phone number 9988776655, it can be proven that 9876556789 is the smallest phone number that can be obtained by rearranging the digits.

C++ solution:
#include<bits/stdc++.h>
using namespace std; 

int main(){
	int t;cin>>t;
	while(t--) {
		string s;cin>>s;
		map<int,int> cnt;
		for(auto c:s) cnt[c-'0']++;
		for(int i=9;i>=0;i--) {
			int p=i; 
			while(!cnt[p]) p++;
			cout<<p; cnt[p]--;
 		}
 		cout<<endl;
	}
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	t, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < t; i++ {
		scanner.Scan()
		s := scanner.Text()
		m := []byte(s)
		sort.Slice(m, func(i, j int) bool { return m[i] < m[j] })

		ans := make([]byte, 10)
		for pos := 0; pos < 10; pos++ {
			required := byte('0' + (9 - pos))
			// Find the smallest digit >= required in m
			idx := sort.Search(len(m), func(i int) bool { return m[i] >= required })
			if idx < len(m) {
				ans[pos] = m[idx]
				// Remove m[idx] from m
				m = append(m[:idx], m[idx+1:]...)
			} else {
				// If no digit >= required, take the largest remaining digit
				ans[pos] = m[len(m)-1]
				m = m[:len(m)-1]
			}
		}
		fmt.Println(string(ans))
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            String s = br.readLine().trim();
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            List<Character> digits = new ArrayList<>();
            for (char c : chars) {
                digits.add(c);
            }
            StringBuilder ans = new StringBuilder();
            for (int j = 0; j < 10; j++) {
                int req = 9 - j;
                int pos = findFirstGreaterOrEqual(digits, (char) (req + '0'));
                ans.append(digits.remove(pos));
            }
            System.out.println(ans.toString());
        }
    }

    private static int findFirstGreaterOrEqual(List<Character> list, char target) {
        int low = 0;
        int high = list.size() - 1;
        int res = list.size();
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) >= target) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let t;
let cases = [];

rl.on('line', (line) => {
    if (!t) {
        t = parseInt(line, 10);
    } else {
        cases.push(line.trim());
        if (cases.length === t) {
            solve();
            rl.close();
        }
    }
});

function solve() {
    for (const s of cases) {
        let m = s.split('').sort();
        let ans = [];
        for (let i = 0; i < 10; i++) {
            const req = 9 - i;
            let idx = 0;
            while (idx < m.length && parseInt(m[idx], 10) < req) {
                idx++;
            }
            if (idx < m.length) {
                ans.push(m[idx]);
                m.splice(idx, 1);
            } else {
                ans.push(m.pop());
            }
        }
        console.log(ans.join(''));
    }
}

Python solution:
import sys
import bisect
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    s = sorted(input().strip())
    ans = []
    for i in range(10):
        req = str(9 - i)
        j = bisect.bisect_left(s, req)
        ans.append(s.pop(j))
    print(''.join(ans))

Ruby solution:
def solve
  t = gets.to_i
  t.times do
    s = gets.chomp
    m = s.chars.sort
    ans = []
    (0..9).each do |i|
      need = (9 - i).to_s
      # Find the smallest digit >= need in m
      idx = m.bsearch_index { |x| x >= need }
      if idx.nil?
        idx = m.size - 1
      end
      ans << m.delete_at(idx)
    end
    puts ans.join
  end
end

solve