Baldosas P87829


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    1 3 3 3
    1 3 3 6
    1 1 3 9
    1 1 2 13
    

    Output

    AAA
    BBB
    CCC
    
    AAABBB
    CCCDDD
    EEEFFF
    
    !!!
    
    ABCDEFGHIJKLM
    NOPQRSTUVWXYZ
    
  • Input

    2 2 4 6
    3 4 12 12
    3 3 48 48
    

    Output

    AABBCC
    AABBCC
    DDEEFF
    DDEEFF
    
    AAAABBBBCCCC
    AAAABBBBCCCC
    AAAABBBBCCCC
    DDDDEEEEFFFF
    DDDDEEEEFFFF
    DDDDEEEEFFFF
    GGGGHHHHIIII
    GGGGHHHHIIII
    GGGGHHHHIIII
    JJJJKKKKLLLL
    JJJJKKKKLLLL
    JJJJKKKKLLLL
    
    !!!
    
  • Input

    3 1 3 5
    3 1 2 5
    1 20 15 15
    1 6 9 8
    4 3 7 12
    4 3 12 7
    2 3 9 6
    

    Output

    AAABC
    DDDBC
    EEEBC
    
    !!!
    
    !!!
    
    !!!
    
    AAAABBBBCCCC
    AAAABBBBCCCC
    AAAABBBBCCCC
    DDDEEEFFFGGG
    DDDEEEFFFGGG
    DDDEEEFFFGGG
    DDDEEEFFFGGG
    
    AAAABBB
    AAAABBB
    AAAABBB
    CCCCBBB
    CCCCDDD
    CCCCDDD
    EEEEDDD
    EEEEDDD
    EEEEFFF
    GGGGFFF
    GGGGFFF
    GGGGFFF
    
    AAABBB
    AAABBB
    CCCDDD
    CCCDDD
    EEEFFF
    EEEFFF
    GGHHII
    GGHHII
    GGHHII
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++