Solution.java

import java.util.*;

public class Solution {
    /*
        comopute the time spent from (x1, y1) to (x2, y2)
    */
    public static int timeConsumed(int x1, int y1, int x2, int y2) {
        int moveSpeed = 100;
        if (x1 == x2) {
            return Math.abs(y1 - y2) * moveSpeed;
        } else if (y1 == y2) {
            return Math.abs(x1 - x2) * moveSpeed;
        } else if (Math.abs(x1 - x2) == Math.abs(y1 - y2)) {
            return Math.abs(x1 - x2) * moveSpeed;
        } else {
            if (Math.abs(x1 - x2) < Math.abs(y1 - y2)) {
                return Math.abs(y1 - y2) * moveSpeed;
            } else {
                return Math.abs(x1 - x2) * moveSpeed;
            }
        }
    }

    /*
        return the zombie smashed in this sequence
    */
    public static int smashZombie(Zombie[] zombies) {
        int numOfZombieSmashed = 0;
        int curX = 0;
        int curY = 0;
        int curTime = 0;
        int rechargeTime = 750;
        int stayingTime = 1000;
        for (int i = 0; i < zombies.length; i++) {
            if (i != 0 && timeConsumed(curX, curY, zombies[i].x, zombies[i].y) < rechargeTime) {
                curTime += rechargeTime;
            } else {
                curTime += timeConsumed(curX, curY, zombies[i].x, zombies[i].y);
            }

            if (curTime > zombies[i].time + stayingTime) {
                break;
            } else if (curTime < zombies[i].time) {
                curTime = zombies[i].time;
            } 
            numOfZombieSmashed++;
        }   
        return numOfZombieSmashed;
    }

    /*
        do a permutation and return the Maximum number of zombie smashed
    */
    public static int permutation(Zombie[] zombies) {
        IntWrapper ret = new IntWrapper(0);
        permutation(zombies, 0, ret);
        return ret.value;
    }

    public static void permutation(Zombie[] zombies, int index, IntWrapper ret) {
        if (zombies.length == index) {
            ret.value = Math.max(ret.value, smashZombie(zombies));
        } else {
            for (int i = index; i < zombies.length; i++) {
                Zombie z = zombies[index];
                zombies[index] = zombies[i];
                zombies[i] = z;
                permutation(zombies, index + 1, ret);
                z = zombies[index];
                zombies[index] = zombies[i];
                zombies[i] = z;
            }
        }
    }
    
    public  static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numOfTestcase = Integer.parseInt(scanner.nextLine());
        for (int i = 1; i <= numOfTestcase; i++) {
            int numOfZombies = Integer.parseInt(scanner.nextLine());
            Zombie[] zombies = new Zombie[numOfZombies];
            for (int j = 0; j < numOfZombies; j++) {
                String str = scanner.nextLine();
                String[] strs = str.split(" ");
                zombies[j] = new Zombie(Integer.parseInt(strs[0]), 
                    Integer.parseInt(strs[1]), Integer.parseInt(strs[2]));
            }
            int ret = permutation(zombies);
            System.out.format("Case #%d: %d\n", i, ret);
        }
    }
}

class Zombie {
    int x;
    int y;
    int time;
    public Zombie(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

class IntWrapper {
    int value;
    public IntWrapper(int value) {
        this.value = value;
    }
}