Untitled

 avatar
unknown
plain_text
2 years ago
2.3 kB
10
Indexable
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class EarningBiggestPrizeMoney2 {
	static int ans;
	static int tinhTien;
	static char theSo[];
	static int soTraoDoi;
	static boolean foundBest;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("tienThuongLonNhat"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			theSo = sc.next().toCharArray();
			soTraoDoi = sc.nextInt();
			ans = 0;
			foundBest = false;

			backtrack(soTraoDoi);
			System.out.println("Case #" + tc);
			System.out.println(ans);
		}
	}

	public static void backtrack(int _soTraoDoi) {

		if (_soTraoDoi == 0) {
			ans = Math.max(ans, tinhTien());
			return;
		}
		
		boolean isDecrease = true;//
		for (int i = 1; i < theSo.length && isDecrease; i++)
			if (theSo[i] > theSo[i - 1])
				isDecrease = false;
		if (isDecrease) {
			boolean hasSame = false;
			for (int i = 0; i < theSo.length && !hasSame; i++) {
				for (int j = i + 1; j < theSo.length && !hasSame; j++) {
					if (theSo[i] == theSo[j])
						hasSame = true;
				}
			}
			if (!hasSame && _soTraoDoi % 2 != 0) {
				hoanDoiThe(theSo.length - 1,theSo.length - 2);
//				char tmp = theSo[theSo.length - 2];
//				theSo[theSo.length - 2] = theSo[theSo.length - 1];
//				theSo[theSo.length - 1] = tmp;
			}

			foundBest = true;
			ans = Math.max(ans, tinhTien());
			return;
		}
		if (foundBest) {
			//ans = Math.max(ans, tinhTien());
			return;
		}
		for (int i = 0; i < theSo.length; i++) {
			for (int j = i + 1; j < theSo.length; j++) {
//				if(theSo[i]==9)
//				{
//					System.out.print(theSo[j]+" ");
//				}
				hoanDoiThe(i, j);
				//System.out.print(theSo[j]+" ");
				backtrack(_soTraoDoi - 1);
				hoanDoiThe(i, j);
			}

		}
	}

	public static int tinhTien() {
		tinhTien = 0; //
		for (int i = 0; i < theSo.length; i++) {
			int convertSo = theSo[i] - '0';
			tinhTien = tinhTien * 10 + convertSo;

		}
		return tinhTien;
	}

	public static void hoanDoiThe(int i, int j) {
		char tmp = theSo[i];
		theSo[i] = theSo[j];
		theSo[j] = tmp;

	}
}
Editor is loading...