HDU 6351

Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits.

Let the decimal representation of n as (x1x2... xm)10 satisfying that 1 ≤ x1 ≤ 9, 0 ≤ xi ≤ 9 (2 ≤ i ≤ m), which means . In each swap, Anton can select two digits xi and xj (1 ≤ i ≤ j ≤ m) and then swap them if the integer after this swap has no leading zero.

Could you please tell him the minimum integer and the maximum integer he can obtain after k swaps?

Input The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains two space-separated integers n and k.

1 ≤ T ≤ 100, 1 ≤ n, k ≤ 109.

Output For each test case, print in one line the minimum integer and the maximum integer which are separated by one space.

Sample 1

5

12 1

213 2

998244353 1

998244353 2

998244353 3

---------------------------------------------------------------------------------------------

12 21

123 321

298944353 998544323

238944359 998544332

233944859 998544332

WA code

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define inf 9187201950435737471
const int maxn=3e5+10;
using namespace std;
int t,k,num[25];
string s;
signed main(){
	cin >> t;
	while(t--){
		cin >> s >> k;
		int cnt=k;
		for(int i=0;i<s.size();i++){
			num[i+1]=s[i]-'0';
		}
		for(int i=1;i<=s.size();i++){
			if(k==0) break;
			int x=-1,y=num[i];
			for(int j=s.size();j>i;j--){
				if(num[j]<y){
					if(i==1 && num[j]==0) continue;
					y=num[j];
					x=j;
				}
			}
			if(x!=-1){
				swap(num[i],num[x]);
				k--;
			}
		}
		for(int i=1;i<=s.size();i++){
			cout << num[i];
		}
		cout << " ";
		k=cnt;
		for(int i=0;i<s.size();i++){
			num[i+1]=s[i]-'0';
		}
		for(int i=1;i<=s.size();i++){
			if(k==0) break;
			int x=-1,y=num[i];
			for(int j=s.size();j>i;j--){
				if(num[j]>y){
					if(i==1 && num[j]==0) continue;
					y=num[j];
					x=j;
				}
			}
			if(x!=-1){
				swap(num[i],num[x]);
				k--;
			}
		}
		for(int i=1;i<=s.size();i++){
			cout << num[i];
		}
		cout << endl;
	}
	return 0;
}