Untitled
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...