brick.in.sample

5 3 4 2 6
0

BrickLaying.java

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

public class BrickLaying {
    
    public static void main(String[] args) throws IOException
    {
        (new BrickLaying()).run();
    }
    
    public void run() throws IOException
    {
        BufferedReader br = new BufferedReader(new FileReader("brick.in"));
        
        while (true)
        {
            String s = br.readLine();
            if (s == null)
            {
                break;
            }
            String[] ss = s.split(" ");
            
            BrickLayingCase c = new BrickLayingCase();
            
            c.width = Integer.parseInt(ss[0]);
            if (c.width == 0)
            {
                break;
            }
            
            c.height = Integer.parseInt(ss[1]);
            
            c.brick3 = Integer.parseInt(ss[2]);
            c.brick2 = Integer.parseInt(ss[3]);
            c.brick1 = Integer.parseInt(ss[4]);
            
            if (c.solve())
            {
                // Print
                int brickIndex = 0;
                for (int i = 0; i < c.height && brickIndex < c.brickCount; i++)
                {
                    int remainingWidth = c.width;
                    while (remainingWidth > 0 && brickIndex < c.brickCount)
                    {
                        if (c.solution[brickIndex] == BrickType.TYPE1)
                        {
                            System.out.print("1");
                            remainingWidth--;
                        }
                        else if (c.solution[brickIndex] == BrickType.TYPE2)
                        {
                            System.out.print("22");
                            remainingWidth -= 2;
                        }
                        else if (c.solution[brickIndex] == BrickType.TYPE3)
                        {
                            System.out.print("333");
                            remainingWidth -= 3;
                        }
                        brickIndex++;
                    }
                    System.out.println();
                }
            }
            else 
            {
                System.out.println("CAN'T BE DONE");
            }
            System.out.println();
        }
    }
    
    class BrickLayingCase 
    {
        public int width;
        public int height;
        public int brick3;
        public int brick2;
        public int brick1;
        public int brickCount;
        public BrickType[] solution;
        
        public boolean solve()
        {
            HashSet<String> permutations = new HashSet<String>();
            brickCount = brick1 + brick2 + brick3;
            // Generate a list of all the bricks.
            BrickType[] allbricks = new BrickType[brickCount];
            int allbricksindex = 0;
            for (int i = brick3; i > 0; i--)
            {
                allbricks[allbricksindex] = BrickType.TYPE3;
                allbricksindex++;
            }
            for (int i = 0; i < brick2; i++)
            {
                allbricks[allbricksindex] = BrickType.TYPE2;
                allbricksindex++;
            }
            for (int i = 0; i < brick1; i++)
            {
                allbricks[allbricksindex] = BrickType.TYPE1;
                allbricksindex++;    
            }
            
            int[] indexes = new int[brickCount];
            for (int i = 0; i < brickCount; i++)
            {
                indexes[i] = i;
            }
            
            while (true)
            {
                // Generate permutations
                boolean permFound = false;
                int k;
                for (k = brickCount - 2; k >= 0; k--)
                {
                    if (indexes[k] < indexes[k + 1])
                    {
                        permFound = true;
                        break;
                    }
                }
                if (!permFound)
                {
                    return false;
                }
                
                int l;
                for (l = brickCount - 1; l >= 0; l--)
                {
                    if (indexes[k] < indexes[l])
                    {
                        break;
                    }
                }
                
                swap(indexes, k, l);
                
                reverse(indexes, k + 1, brickCount - 1);
                
                // End of permutation generation
                
                // Get current list of bricks
                BrickType[] currentBricks = new BrickType[brickCount];
                String currentBricksString = "";
                for (int i = 0; i < brickCount; i++)
                {
                    currentBricks[i] = allbricks[indexes[i]];
                    currentBricksString += currentBricks[i];
                }
                
                // Generate a string and check if already generated.
                if (permutations.contains(currentBricksString))
                {
                    continue;
                }
                else
                {
                    permutations.add(currentBricksString);
                }
                
                // DEBUG: Print current bricks
                System.out.print("Trying permutation: ");
                for (int i = 0; i < brickCount; i++)
                {
                    System.out.print(currentBricks[i].getValue() + " ");
                }
                System.out.println();
                
                // Check if it fits our brick-laying criteria
                // 1. Must not be exact in the rows.
                int currentBrickIndex = 0;
                boolean failCriteria1 = false;
                
                for (int i = 0; i < height; i++)
                {
                    int remainingWidth = width;
                    while (remainingWidth > 0)
                    {
                        remainingWidth -= currentBricks[currentBrickIndex].getValue();
                        currentBrickIndex++;
                    }
                    
                    if (remainingWidth < 0)
                    {
                        failCriteria1 = true;
                        break;
                    }
                }
                
                if (failCriteria1)
                {
                    continue;
                }
                
                // 2. Divisions must not be the same as the previous row.
                List<int> prevDivisions;
                List<int> currentDivisons;
                currentBrickIndex = 0;
                boolean failCriteria2 = false;
                
                for (int i = 0; i < height; i++)
                {
                    int remainingWidth = width;
                    division 
                    while (remainingWidth > 0)
                    {
                        remainingWidth -= currentBricks[currentBrickIndex].getValue();
                        
                        if ()
                        
                        currentBrickIndex++;
                    }
                }
                
                
                solution = currentBricks;
                return true;
            }
        }
    }
    
    public enum BrickType
    {
        NONE (0),
        TYPE1 (1),
        TYPE2 (2),
        TYPE3 (3);
        
        private final int value;
        
        BrickType(int value)
        {
            this.value = value;
        }
        
        public int getValue()
        {
            return this.value;
        }
    }
    
    public static void swap(int[] arr, int index1, int index2)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
    public static void reverse(int[] arr, int index1, int index2)
    {
        for (int i = 0; i < (index2 - index1) / 2; i++)
        {
            swap(arr, index1 + i, index2 - i);
        }
    }
}