package CodeJam.c2012.clasificacion;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

/**
 * Problem
 *
 * You're watching a show where Googlers (employees of Google) dance, and then
 * each dancer is given a triplet of scores by three judges. Each triplet of
 * scores consists of three integer scores from 0 to 10 inclusive. The judges
 * have very similar standards, so it's surprising if a triplet of scores
 * contains two scores that are 2 apart. No triplet of scores contains scores
 * that are more than 2 apart.
 *
 * For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8,
 * 8) are surprising. (7, 6, 9) will never happen.
 *
 * The total points for a Googler is the sum of the three scores in that
 * Googler's triplet of scores. The best result for a Googler is the maximum of
 * the three scores in that Googler's triplet of scores. Given the total points
 * for each Googler, as well as the number of surprising triplets of scores,
 * what is the maximum number of Googlers that could have had a best result of
 * at least p?
 *
 * For example, suppose there were 6 Googlers, and they had the following total
 * points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising
 * triplets of scores, and you want to know how many Googlers could have gotten
 * a best result of 8 or better.
 *
 * With those total points, and knowing that two of the triplets were
 * surprising, the triplets of scores could have been:
 *
 * 10 9 10 6 6 8 (*) 2 3 3 6 6 6 6 6 6 6 7 8 (*)
 *
 * The cases marked with a (*) are the surprising cases. This gives us 3
 * Googlers who got at least one score of 8 or better. There's no series of
 * triplets of scores that would give us a higher number than 3, so the answer
 * is 3.
 *
 * Input
 *
 * The first line of the input gives the number of test cases, T. T test cases
 * follow. Each test case consists of a single line containing integers
 * separated by single spaces. The first integer will be N, the number of
 * Googlers, and the second integer will be S, the number of surprising triplets
 * of scores. The third integer will be p, as described above. Next will be N
 * integers ti: the total points of the Googlers.
 *
 * Output
 *
 * For each test case, output one line containing "Case #x: y", where x is the
 * case number (starting from 1) and y is the maximum number of Googlers who
 * could have had a best result of greater than or equal to p.
 *
 * Limits
 *
 * 1 â¤ T â¤ 100. 0 â¤ S â¤ N. 0 â¤ p â¤ 10. 0 â¤ ti â¤ 30. At least S of the ti values
 * will be between 2 and 28, inclusive.
 *
 * Small dataset
 *
 * 1 â¤ N â¤ 3.
 *
 * Large dataset
 *
 * 1 â¤ N â¤ 100.
 *
 * Sample
 *
 * Input Output 4 Case #1: 3 3 1 5 15 13 11 Case #2: 2 3 0 8 23 22 21 Case #3: 1
 * 2 1 1 8 0 Case #4: 3 6 2 8 29 20 8 18 18 21
 *
 * @author Leandro Baena Torres
 */
public class B {

    public static void main(String[] args) throws FileNotFoundException, IOException {
        BufferedReader br = new BufferedReader(new FileReader("B.in"));
        String linea;
        int numCasos, N, S, p, t[], y, minSurprise, minNoSurprise;

        linea = br.readLine();
        numCasos = Integer.parseInt(linea);
        for (int i = 0; i < numCasos; i++) {
            linea = br.readLine();
            String[] aux = linea.split(" ");
            N = Integer.parseInt(aux[0]);
            S = Integer.parseInt(aux[1]);
            p = Integer.parseInt(aux[2]);
            t = new int[N];
            y = 0;
            minSurprise = p + ((p - 2) >= 0 ? (p - 2) : 0) + ((p - 2) >= 0 ? (p - 2) : 0);
            minNoSurprise = p + ((p - 1) >= 0 ? (p - 1) : 0) + ((p - 1) >= 0 ? (p - 1) : 0);
            for (int j = 0; j < N; j++) {
                t[j] = Integer.parseInt(aux[3 + j]);
                if (t[j] >= minNoSurprise) {
                    y++;
                } else {
                    if (t[j] >= minSurprise) {
                        if (S > 0) {
                            y++;
                            S--;
                        }
                    }
                }
            }

            System.out.println("Case #" + (i + 1) + ": " + y);
        }
    }
}

package codejam.codejam_2012;

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 * User: csrazvan
 * Date: 14.04.2012
 * Time: 02:43
 * To change this template use File | Settings | File Templates.
 */
public class DancingWithGooglers {
    static private boolean DEBUG = false;

    public void solve() throws Exception {
        Scanner scanner = new Scanner(new File("dancing.in"));
        int t = scanner.nextInt();
        scanner.nextLine();
        BufferedWriter bw = new BufferedWriter(new FileWriter(new File("dancing.out")));
        for (int i = 1; i <= t; i++) {
            String split[] = scanner.nextLine().split(" ");
            System.out.println("Solving " + i);
            solveCase(split, i, bw);
        }
        bw.close();

    }

    public void solveCase(String[] split, int caseNr, BufferedWriter bw) throws FileNotFoundException, IOException {
        int n = Integer.parseInt(split[0]);
        int surprisingCount = Integer.parseInt(split[1]);
        int p = Integer.parseInt(split[2]);
        Case[][] matrix = new Case[n][7];
        int size[] = new int[n];

        for (int i = 0; i < n; i++) {
            int j = 0;
            int number = Integer.parseInt(split[3 + i]);

            // 1:a a a
            if (number % 3 == 0) {
                int a = number / 3;
                boolean ge = false;
                if (a >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(false, ge, 1);
                size[i]++;
            }
            // 2:a a a+1
            if ((number - 1 >= 0) & ((number - 1) % 3 == 0)) {
                int a = (number - 1) / 3;
                boolean ge = false;
                if ((a + 1) >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(false, ge, 2);
                size[i]++;
            }

            // 3:a a+1 a+1
            if ((number - 2 >= 0) & ((number - 2) % 3 == 0)) {
                int a = (number - 2) / 3;
                boolean ge = false;
                if ((a + 1) >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(false, ge, 3);
                size[i]++;
            }

            // 4:a a a+2
            if ((number - 2 >= 0) & ((number - 2) % 3 == 0)) {
                int a = (number - 2) / 3;
                boolean ge = false;
                if ((a + 2) >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(true, ge, 4);
                size[i]++;
            }
            // 5:a a a+2
            if ((number - 4 >= 0) & ((number - 4) % 3 == 0)) {
                int a = (number - 4) / 3;
                boolean ge = false;
                if ((a + 2) >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(true, ge, 5);
                size[i]++;
            }

            // 6:a a+1 a+2
            if ((number - 3 >= 0) & ((number - 3) % 3 == 0)) {
                int a = (number - 3) / 3;
                boolean ge = false;
                if ((a + 2) >= p || (a + 1) >= p) {
                    ge = true;
                }
                matrix[i][j++] = new Case(true, ge, 6);
                size[i]++;
            }
        }

        if (DEBUG) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < size[i]; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }

        // a little backtracking .....:(
        int combinations[] = new int[n];
        Arrays.fill(combinations, 0);
        int bestScore = 0;
        int k = n - 1;
        while (combinations[0] < size[0] && k >= 0) {
            // do some logic 
            int nrStrange = 0;
            int bestLocal = 0;

            for (int i = 0; i < n; i++) {
                if (matrix[i][combinations[i]].hasGE) {
                    bestLocal++;
                }
                if (matrix[i][combinations[i]].isSurprising()) {
                    nrStrange++;
                }
                if (nrStrange > surprisingCount) {
                    break;
                }
            }
            if (nrStrange == surprisingCount && bestLocal > bestScore) {
                bestScore = bestLocal;
                if (DEBUG) {
                    System.out.println(Arrays.toString(combinations) + " - " + bestLocal);
                }
            }
            // next combi
            if (combinations[k] < size[k] - 1) {
                combinations[k]++;
            } else {
                combinations[k] = 0;
                if (k - 1 >= 0) {
                    combinations[--k]++;
                }else {break;}
                while (k >= 1 && combinations[k] >= size[k]) {
                    combinations[k] = 0;
                    combinations[--k]++;
                }
                k = n - 1;
            }


        }
        if (bw != null) {
            bw.write(String.format("Case #%s: %s\n", caseNr, bestScore));
        }      else {
            System.out.println(String.format("Case #%s: %s\n", caseNr, bestScore));
        }

    }

    public static void main(String[] args) {
        try {
            new DancingWithGooglers().solve();
//            new DancingWithGooglers().solveCase("1 0 7 16".split(" "), 1, null);
//            new DancingWithGooglers().solveCase("3 1 5 15 13 11".split(" "),1,null);
//            new DancingWithGooglers().solveCase("3 0 8 23 22 21".split(" "),1,null);
//            new DancingWithGooglers().solveCase("2 1 1 8 0".split(" "),1,null);
//            new DancingWithGooglers().solveCase("6 2 8 29 20 8 18 18 21".split(" "), 1,null);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


}

class Case {
    boolean surprising = false;
    boolean hasGE = false;
    int caz = 0;

    public int getCaz() {
        return caz;
    }

    public void setCaz(int caz) {
        this.caz = caz;
    }

    public boolean isSurprising() {
        return surprising;
    }

    public void setSurprising(boolean surprising) {
        this.surprising = surprising;
    }

    public boolean isHasGE() {
        return hasGE;
    }

    public void setHasGE(boolean hasGE) {
        this.hasGE = hasGE;
    }

    Case(boolean surprising, boolean hasGE, int caz) {
        this.surprising = surprising;
        this.hasGE = hasGE;
        this.caz = caz;

    }

    @Override
    public String toString() {
        return "Case{" +
                "surprising=" + surprising +
                ", hasGE=" + hasGE +
                ", caz=" + caz +
                '}';
    }
}