Packets (POJ 1017)

A box packing problem, we have object of size $1\times 1$, $2\times 2$, $3\times 3$ $4\times 4$, $5 \times 5$ and $6 \times 6$. We can always use a box of size $6\times 6$ to pack these objects. We find that all objects will compitible to each other except $2\times 2$ and $3\times 3$. Two types of objects are compitible if they are either not able to be put into a box at the same time, or if size of one objects is divisible by the other.

If the objects is all compitible, we can greedily put large objects into the box and divide the box's free space to two parts and recursively put other objects. So we follow this idea and take $3\times 3$ as a special case to handle and solve this problem.

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

public class Packets {
    private static int putPackets(int[] packets, int width, int height) {
        int w = Math.min(width, height);
        int h = Math.max(width, height);
        for (int i = w; i > 0; i--) {
            if (packets[i - 1] == 0) continue;
            int res = Math.min(packets[i - 1], h / i);
            packets[i - 1] -= res;
            if (i == 3 && res == 1 && w == 6) {
                return res + putPackets(packets, 2, 6) + putPackets(packets, 3, 4) + putPackets(packets, 1, 3);
            } else {
                return res + putPackets(packets, w - i, h) + putPackets(packets, i, h - res * i);
            }
        }
        return 0;
    }
    private static void solve(int[] packets, int count) {
        int res = 0;
        while (count > 0) {
            count -= putPackets(packets, 6, 6);
            res++;
        }
        System.out.println(res);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str;
        while (true) {
            int[] packets = new int[6];
            str = in.readLine().split(" ");
            int count = 0;
            for (int i = 0; i < 6; i++) {
                packets[i] = Integer.parseInt(str[i]);
                count += packets[i];
            }
            if (count == 0) return;
            solve(packets, count);
        }
    }
}