Baldosas P87829

Hacer un programa que embaldose un rectángulo f × c con baldosas a × b. Para cada una de las 26 letras mayúsculas, hay exactamente una baldosa vertical y una baldosa horizontal disponible, de las cuales se puede usar como mucho una. Por ejemplo, si a = 1 y b = 3, podemos usar como máximo una de estas dos baldosas:

El rectángulo debe quedar cubierto en su totalidad, y no puede sobrar ningún trozo de las baldosas usadas. Si hay más de una posible manera de embaldosar, vuestro programa debe encontrar la menor en orden alfabético, leyendo de arriba a abajo y de izquierda a derecha. En el caso de que no exista ninguna manera posible, vuestro programa lo tiene que indicar.

Entrada

La entrada consiste en una serie de lineas, cada una con a, b, f y c en este orden. Todos los números están entre 1 y 50.

Salida

Para cada linea de la entrada, hay que escribir el embaldosado menor lexicográficamente, o bien "!!!" si no existe ninguno. Separar las respuestas con una linea en blanco.

Puntuación

• TestA:  ‍15 Puntos ‍

  Algunos juegos de pruebas contendrán exclusivamente casos como los del ejemplo de entrada 1, en los que a = 1, y tanto f como c son múltiplos de b.

• TestB:  ‍20 Puntos ‍

  Algunos juegos de pruebas contendrán además casos como los del ejemplo de entrada 2, en los que tanto f como c son múltiplos de a y de b.

• TestC:  ‍65 Puntos ‍

  Otros juegos de pruebas contendrán casos de todo tipo.