Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
3.6 kB
5
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int[] a,sorted;
	static int k,k1,maximum,top;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		for(int t=1;t<=tc;t++){
			String s = sc.next();
			k = sc.nextInt();
			k1 = k;
			a = new int[s.length()];
			sorted = new int[s.length()];
			top = 0;
			for(int i=0;i<s.length();i++){
				a[i]= Integer.parseInt(String.valueOf(s.charAt(i)));
				sorted[i] = a[i];
			}
			for(int i=0;i<s.length()-1;i++){
				for(int j=i+1;j<s.length();j++){
					if(sorted[i]<sorted[j]){
						int tmp = sorted[i];
						sorted[i] = sorted[j];
						sorted[j] = tmp;
					}
				}
			}
			maximum = Integer.parseInt(s);
//			System.out.println(tc);
			exchange(0);
//			System.out.println(k);
			String ans = "";
			k = k1;
			if(k<0||k%2==0){
				ans = String.valueOf(maximum);
			}
			else{
				if(same(a,a.length)) 
					ans = String.valueOf(maximum);
				else {
//					System.out.println("OK");
					int x = maximum%10;
					int y = (maximum/10)%10;
					ans = String.valueOf((maximum/100)*100+x*10+y);
				}
			}
			System.out.println("Case #"+t);
			System.out.println(ans);
		}
	}
	public static void exchange(int start){
//		for(int i=0;i<a.length;i++){
//			System.out.print(a[i]);
//		}
//		System.out.println(" "+k+" "+start);
		if(k<=0||check(a,a.length)||start>=a.length) {
			String res = "";
			for(int i=0;i<a.length;i++){
				res += String.valueOf(a[i]);
			}
			if(maximum < Integer.parseInt(res)) maximum = Integer.parseInt(res);
			k1 = k;
			return;
		}
		else {
			if(a[start]==sorted[top]) {
				top++;
				exchange(start+1);
				top--;
			}
			else {
				for(int i=start+1;i<a.length;i++){
					if(a[i]==sorted[top]){
						int tmp = a[start];
						a[start] = a[i];
						a[i] = tmp;
						top++;
						k--;
						exchange(start+1);
						a[i] = a[start];
						a[start] = tmp;
						k++;
						top--;
					}
				}
			}
		}
	}
	public static boolean check (int[] arr,int len) {
		for(int i=0;i<len-1;i++){
			if(a[i]<a[i+1]) return false;
		}
		return true;
	}
	public static boolean same(int[] arr,int len) {
		for(int i=0;i<len-1;i++){
			for(int j=i+1;j<len;j++)
				if(a[i]==a[j]) return true; 
		}
		return false;
	}
}
50
772 8
441296 9
5525 2
114 2
6575 3
0473 7
7321 10
1138 4
53179 9
975054 4
0128 9
50665 7
937 2
55960 5
564 9
50308 8
57308 6
215 4
377088 3
340 1
1136 6
37 2
58 8
1375 8
655673 10
29 4
153 3
583185 8
812 7
361 9
394 5
60153 1
65433 4
267825 10
969 9
027147 10
08343 8
57568 1
805683 8
83 8
97 9
7734 5
5005 7
216926 7
3560 7
50 1
679 9
16813 3
1415 8
751 10

Case #1
772
Case #2
964421
Case #3
5552
Case #4
411
Case #5
7655
Case #6
7403
Case #7
7321
Case #8
8311
Case #9
97531
Case #10
975540
Case #11
8201
Case #12
66550
Case #13
937
Case #14
96550
Case #15
654
Case #16
85300
Case #17
87503
Case #18
521
Case #19
887730
Case #20
430
Case #21
6311
Case #22
37
Case #23
58
Case #24
7513
Case #25
766553
Case #26
29
Case #27
513
Case #28
885531
Case #29
821
Case #30
631
Case #31
934
Case #32
65103
Case #33
65433
Case #34
876522
Case #35
996
Case #36
774210
Case #37
84330
Case #38
87565
Case #39
886530
Case #40
83
Case #41
79
Case #42
7743
Case #43
5500
Case #44
966221
Case #45
6530
Case #46
5
Case #47
976
Case #48
86311
Case #49
5411
Case #50
751