import java.util.Scanner;

/**
 * The Class BaldosasAV.
 * Clase que calcula mediante un algoritmo voraz la solución óptima para rellenar el suelo de un solar de dimensiones cuadradas
 * con baldosas también cuadradas de diferentes dimensiones.
 */

public class ProblemaBaldosas {
	/**
	 * The main method.
	 *
	 * @param args the arguments
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int baldosas[];
		 System.out.println("Introduzca las dimensiones del solar (metros cuadrados): ");
		 int solar = scan.nextInt(); 
		 System.out.println("Indique el número de baldosas diferentes: ");
		 int nBaldosas = scan.nextInt();
		 baldosas = new int[nBaldosas];
		 
		 System.out.println("Inserte los tamaños de las baldosas: "); 
		 for(int i = 0; i < nBaldosas; i++) {
			 System.out.println((i+1) + ".-Inserte un tamaño: ");
			 baldosas[i] = scan.nextInt();
		 } 
		 algoritmoVoraz(baldosas, solar);
	}

	/**
	 * Algoritmo voraz.
	 *
	 * @param tamBaldosas the tam baldosas
	 * @param metros the metros
	 */
	private static void algoritmoVoraz (int[] tamBaldosas, int metros){
		
		int solucion[][] = new int [metros] [metros];
		
		int[] baldosas = mergesort(tamBaldosas, 0, tamBaldosas.length-1);
		
		int actual, size;
		int side = metros;
		actual = baldosas.length-1;
		size = baldosas[actual];
		int []puestas= new int[baldosas.length];
		for(int i = 0; i < side; i++) { 
			for(int j = 0; j < side; j++) {
				while(solucion[i][j]==0 && actual >=0) {
					size=baldosas[actual];
					if(cabe(size, i, j, solucion, side)) {
						for(int fila = i; fila < i + size; fila++) {
							for(int col = j; col <j + size; col++) {
								solucion[fila][col] = size;
								
							}
						}
						puestas[actual]++;
					}else {
						actual--;
					}
				}
			}
		}
		
		System.out.println();
		for(int k=0; k<solucion.length; k++) {
			for(int r=0; r<solucion.length; r++) {
				System.out.print(solucion[k][r]);
			}
			System.out.println();
		}
		System.out.println("\nLas baldosas puestas son las siguientes: ");
		for(int s=0; s<baldosas.length; s++) {
			System.out.println("De tamaño "+baldosas[s]+" se han puesto "+puestas[s]+" baldosas.");
		}

}
	
	/**
	 * Método para saber si cabe una baldosa en el espacio restante.
	 *
	 * @param size the size
	 * @param r the r
	 * @param c the c
	 * @param solucion1 the solucion 1
	 * @param lado the lado
	 * @return true, si cabe la baldosa
	 */
	private static boolean cabe (int size, int r, int c, int [][] solucion1, int lado){
		boolean fits = r + size <= lado && c + size <= lado; 
		if(fits){
		  for(int row = r; fits && row < r + size; row++){
			for(int col = c; fits && col < c + size; col++){
			  if(solucion1[row][col] != 0) {
				  fits = false;
			  }
			}
		  }
		}
		return fits;
	  }
	
	/**
	 * Mergesort.
	 *
	 * @param array the array
	 * @param left posicion del numero de la izquierda
	 * @param right the right
	 * @return el array de enteros ordenado
	 */
	private static int[] mergesort(int[] array, int left, int right){
		if (left < right) {
			int mid = (left+right)/2;
			mergesort (array, left, mid);
			mergesort (array, mid + 1, right);
			merge (array, left, mid, right);
		}
		return array;
	}
	
	/**
	 * Merge.
	 *
	 * @param a the a
	 * @param p the p
	 * @param q the q
	 * @param r the r
	 */
	private static void merge (int [ ] a, int p, int q, int r) {
		int i = p, j = q+1, k = p;
		int [ ] temp = new int [r-p+1];
		for (int l = p; l <= r; l++) {
			temp[l-p] = a[l];
		}
		while (i <= q && j <= r) {
			if (temp[i-p] <= temp[j-p]) {
				a[k] = temp[i-p]; i++;
			} else {
			a[k] = temp[j-p]; j++;
			}
			k++;
		}
		if (j-1 == r){
			while (i <= q) {
				a[k] = temp[i-p]; 
				k++; 
				i++;
			}
		}	
	}

}

public class ResultadoBaldosasModificado {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int baldosas[] = {1, 2 ,5};
		int solar = 4;
		int nBaldosas = 3;
		} 

		 algoritmoVoraz(baldosas, solar);
		 
	}

	/**
	 * Algoritmo voraz.
	 *
	 * @param tamBaldosas the tam baldosas
	 * @param metros the metros
	 */
	private static void algoritmoVoraz (int[] tamBaldosas, int metros){
		
		int solucion[][] = new int [metros] [metros];
		
		int[] baldosas = mergesort(tamBaldosas, 0, tamBaldosas.length-1);
		
		int actual, size;
		int side = metros;
		actual = baldosas.length-1;
		size = baldosas[actual];
		int []puestas= new int[baldosas.length];
		for(int i = 0; i < side; i++) { 
			for(int j = 0; j < side; j++) {
				while(solucion[i][j]==0 && actual >=0) {
					size=baldosas[actual];
					if(cabe(size, i, j, solucion, side)) {
						for(int fila = i; fila < i + size; fila++) {
							for(int col = j; col <j + size; col++) {
								solucion[fila][col] = size;
								
							}
						}
						puestas[actual]++;
					}else {
						actual--;
					}
				}
			}
		}
		
		System.out.println();
		for(int k=0; k<solucion.length; k++) {
			for(int r=0; r<solucion.length; r++) {
				System.out.print(solucion[k][r]);
			}
			System.out.println();
		}
		System.out.println("\nLas baldosas puestas son las siguientes: ");
		for(int s=0; s<baldosas.length; s++) {
			System.out.println("De tamaño "+baldosas[s]+" se han puesto "+puestas[s]+" baldosas.");
			
		}

}
	
	/**
	 * Método para saber si cabe una baldosa en el espacio restante.
	 *
	 * @param size the size
	 * @param r the r
	 * @param c the c
	 * @param solucion1 the solucion 1
	 * @param lado the lado
	 * @return true, si cabe la baldosa
	 */
	private static boolean cabe (int size, int r, int c, int [][] solucion1, int lado){
		boolean fits = r + size <= lado && c + size <= lado; 
		if(fits){
		  for(int row = r; fits && row < r + size; row++){
			for(int col = c; fits && col < c + size; col++){
			  if(solucion1[row][col] != 0) {
				  fits = false;
			  }
			}
		  }
		}
		return fits;
	  }
	
	/**
	 * Mergesort.
	 *
	 * @param array the array
	 * @param left posicion del numero de la izquierda
	 * @param right the right
	 * @return el array de enteros ordenado
	 */
	private static int[] mergesort(int[] array, int left, int right){
		if (left < right) {
			int mid = (left+right)/2;
			mergesort (array, left, mid);
			mergesort (array, mid + 1, right);
			merge (array, left, mid, right);
		}
		return array;
	}
	
	/**
	 * Merge.
	 */
	private static void merge (int [ ] a, int p, int q, int r) {
		int i = p, j = q+1, k = p;
		int [ ] temp = new int [r-p+1];
		for (int l = p; l <= r; l++) {
			temp[l-p] = a[l];
		}
		while (i <= q && j <= r) {
			if (temp[i-p] <= temp[j-p]) {
				a[k] = temp[i-p]; i++;
			} else {
			a[k] = temp[j-p]; j++;
			}
			k++;
		}
		if (j-1 == r){
			while (i <= q) {
				a[k] = temp[i-p]; 
				k++; 
				i++;
			}
		}	
	}

}