Tiles P87829


Statement
 

pdf   zip

thehtml

Your task is to write a program that tiles a rectangle f × c with tiles a × b. For each one of the 26 uppercase letters, there exactly is a vertical tile and a horizontal tile available, of which can be used at most one. For instance, if a = 1 and b = 3, we can use at most one of these two tiles:

The rectangle must be totally covered, and any piece of the used tiles can be left. If there are more than a way to tile, your prorgram must find the less in alphabetical order, reading from top to bottom and from left to right. In the case that does not exist any possible way, your program must indicate it.

Input

The input consists of a series of lines, each one with a, b, f and c in this order. All the numbers are between 1 and 50.

Output

For each line of the input, your program must print the least lexicographically tiling, or "!!!" if does not exist any. Separate the answers with a line in white.

Scoring

  • TestA:  ‍15 Points ‍

    Some test cases will exclusively contain cases like the ones in the instance of input 1, in which a = 1, and where f and c are multiples of b.

  • TestB:  ‍20 Points ‍

    Some test cases will also contain cases like the ones in the instance of input 2, in which f and c are multiples of a and b.

  • TestC:  ‍65 Points ‍

    Other test cases will contain cases of every kind.

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
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++