GFSSOC ’15 Fall S2 – Hearth

One of Calvin’s favourite pastimes is playing Super-Hearthstone with his friends! In Super-Hearthstone, mana crystals are used to play spells and creatures. Each card has a cost, which when played will expend that many mana crystals. Of course, you cannot play a card if you do not have enough of these crystals. Now, Calvin is very good at Super-Hearthstone, but he has not once managed to beat Super-Grandmaster Awaykened. Why? Because Super-Grandmaster Awaykened is adept at seeing through all possible moves! Currently, master Calvin is in a game against Awaykened, has  cards in his hand, and can only use  mana crystals this turn. The  card costs  mana crystals, and has a unique name . Being Calvin’s lackey second in command, you need to help him beat Awaykened by listing all the possible three card combinations.

Input Specification

Line 1: Two integers, space separated — .

Next  lines:  and , representing one card in Calvin’s hand. The length of the card name will be one word long, all capitals, and less than or equal to  characters.

Output Specification

For each combination, list out the names of the three cards, space separated and sorted by lexicographic order. Combinations should be on one line each, and they should also be sorted lexicographically as well, with respect to pairwise comparisons of each of the three cards in the combination. If there are no possible three card combinations, do not output anything.

Constraints

Sample Input

Copy

5 5
KNIFEJUGGLER 2
HAUNTEDCREEPER 2
STONETUSKBOAR 1
LORDJARAXXUS 9
ANNOYOTRON 2

Sample Output

Copy

ANNOYOTRON HAUNTEDCREEPER STONETUSKBOAR
ANNOYOTRON KNIFEJUGGLER STONETUSKBOAR
HAUNTEDCREEPER KNIFEJUGGLER STONETUSKBOAR

Solution

import java.io.*;
import java.util.*;

public class ABC {
    public static void main(String[] args) {
Scanner in = new Scanner(System.in);
		int times = in.nextInt(),  budget = in.nextInt();
		String [][] test  = new String[2][times];
		for(int i=0; i < times; i++) {
			String name = in.next(), cost = in.next();
			test[0][i] = name;
			test[1][i] = cost;

		}
		ArrayList<String> output = new ArrayList<String>();
		for(int i=0; i < times-2; i++) {
			for(int o = i +1; o < times-1; o++) {
				for(int l= o+1; l < times; l++) {
					if(Integer.parseInt(test[1][i]) + Integer.parseInt(test[1][o]) + Integer.parseInt(test[1][l]) <= budget) {
						String [] sort = new String[3];
						sort[0] = test[0][i];
						sort[1] = test[0][o];
						sort[2] = test[0][l];
						Arrays.sort(sort);
						output.add(sort[0] + " " + sort[1] + " " + sort[2]);
					}
				}
			}
		}
		Collections.sort(output);
		for(int i=0; i < output.size(); i++) {
			System.out.println(output.get(i));
		}
    }
}