import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.Stack; public class kie { public static ArrayList<int[]> variations = new ArrayList<int[]>(); public static int i = 0; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int howManyNominals = scanner.nextInt(); int nominals[] = new int[howManyNominals]; for(int i = 0; i < howManyNominals; i++){ nominals[i] = scanner.nextInt(); } scanner.close(); int maxSum = sumOfArray(nominals); Arrays.sort(nominals); for(int k = 1; k <= nominals.length; k++){ variations = enumKCombos(nominals, k); for(int i = 0; i < variations.size(); i++){ int sum = sumOfArray(variations.get(i)); if((maxSum - sum) % 2 == 0 && sum < maxSum){ System.out.println(maxSum - sumOfArray(variations.get(i))); return; } } variations.clear(); } System.out.println("NIESTETY"); return; } public static ArrayList<int[]> enumKCombos(int[] array, int k) { ArrayList<int[]> comboList = new ArrayList<int[]>(); assert(k > 0); if (k > 1) { assert(array.length >= k); // Store the first member of the array. int[] first = new int[1]; first[0] = array[0]; array = Arrays.copyOfRange(array, 1, array.length); while (array.length + 1 >= k) { ArrayList<int[]> subComboList = new ArrayList<int[]>(); // Call the recursive function and temporarily store the // returned arrays. subComboList = enumKCombos(array, k - 1); // Concatenate the stored first member onto the front of the // returned arrays. int[] subArray; for (int i = 0; i < subComboList.size(); i++) { subArray = subComboList.get(i); int[] concatenated = new int[subArray.length + 1]; concatenated[0] = first[0]; for (int j = 0; j < subArray.length; j++) { concatenated[j + 1] = subArray[j]; } comboList.add(concatenated); } // Add the newly-concatenated arrays to the comboList. // Replace first with array[0]. first[0] = array[0]; // Splice array to remove the first member. array = Arrays.copyOfRange(array, 1, array.length); } } else { // Return the individual members of array as individual 1-member // arrays. for (int i = 0; i < array.length; i++) { comboList.add(Arrays.copyOfRange(array, i, i + 1)); } } return comboList; } public static int sumOfArray(int[] array){ int sum = 0; for(int i = 0; i < array.length; i++){ sum += array[i]; } return sum; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.Stack; public class kie { public static ArrayList<int[]> variations = new ArrayList<int[]>(); public static int i = 0; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int howManyNominals = scanner.nextInt(); int nominals[] = new int[howManyNominals]; for(int i = 0; i < howManyNominals; i++){ nominals[i] = scanner.nextInt(); } scanner.close(); int maxSum = sumOfArray(nominals); Arrays.sort(nominals); for(int k = 1; k <= nominals.length; k++){ variations = enumKCombos(nominals, k); for(int i = 0; i < variations.size(); i++){ int sum = sumOfArray(variations.get(i)); if((maxSum - sum) % 2 == 0 && sum < maxSum){ System.out.println(maxSum - sumOfArray(variations.get(i))); return; } } variations.clear(); } System.out.println("NIESTETY"); return; } public static ArrayList<int[]> enumKCombos(int[] array, int k) { ArrayList<int[]> comboList = new ArrayList<int[]>(); assert(k > 0); if (k > 1) { assert(array.length >= k); // Store the first member of the array. int[] first = new int[1]; first[0] = array[0]; array = Arrays.copyOfRange(array, 1, array.length); while (array.length + 1 >= k) { ArrayList<int[]> subComboList = new ArrayList<int[]>(); // Call the recursive function and temporarily store the // returned arrays. subComboList = enumKCombos(array, k - 1); // Concatenate the stored first member onto the front of the // returned arrays. int[] subArray; for (int i = 0; i < subComboList.size(); i++) { subArray = subComboList.get(i); int[] concatenated = new int[subArray.length + 1]; concatenated[0] = first[0]; for (int j = 0; j < subArray.length; j++) { concatenated[j + 1] = subArray[j]; } comboList.add(concatenated); } // Add the newly-concatenated arrays to the comboList. // Replace first with array[0]. first[0] = array[0]; // Splice array to remove the first member. array = Arrays.copyOfRange(array, 1, array.length); } } else { // Return the individual members of array as individual 1-member // arrays. for (int i = 0; i < array.length; i++) { comboList.add(Arrays.copyOfRange(array, i, i + 1)); } } return comboList; } public static int sumOfArray(int[] array){ int sum = 0; for(int i = 0; i < array.length; i++){ sum += array[i]; } return sum; } } |