시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 16 | 5 | 4 | 66.667% |
You work at a company producing word clocks. These are clocks which, instead of an ordinary clock face, have a grid of letters that is used to display time. Inside the clock are LEDs, one behind each letter, which are lit up in such a way that the illuminated letters spell out the current time as a sentence. See the example below:
Figure J.1: Example word clock displaying the time 3:15. Note that for efficiency reasons, words are allowed to overlap, e.g. FIVE and EIGHT.
Recently your company decided to go international, and you have been tasked with designing the clock faces for various languages. For this purpose, the team of translators has already compiled a list of all the words needed to tell the time and arranged them into groups according to their position in the sentence (e.g. in the above example the numbers from ONE to TWELVE form such a group, as do the words PAST and TO). This means that you won’t have to worry about grammar, as you will only consider a single group at a time.
Given such a group of words and the size of a subgrid, find a way to place all words in the grid or determine that this is impossible. Words have to be written from left to right and are not allowed to wrap from one line to another.
The input consists of:
If there is no solution, print impossible. Otherwise print h lines, each with w uppercase letters, the grid of the word clock. If there is more than one solution, any will be accepted.
5 10 12 ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN ELEVEN TWELVE
FIVEIGHTWO AONEFSEVEN TWELVEFOUR THREELEVEN TENINEQSIX
5 10 12 EIN ZWEI DREI VIER FUENF SECHS SIEBEN ACHT NEUN ZEHN ELF ZWOELF
ZWOELFUENF SECHSIEBEN JZEHNEUNYP DREINSZWEI VIERQACHTC
5 10 12 UNO DUE TRE QUATTRO CINQUE SEI SETTE OTTO NOVE DIECI UNDICI DODICI
impossible