P8296 [COCI 2012/2013 #2] KRIZALJKA
Background
**The score for this problem follows the original COCI setting, with a full score of $80$.**
Description
Do you like playing crossword puzzles? If so, you may know the traditional beginner puzzle shown below:
***
- Horizontally:
1. A device used to cool a computer
2. Solid water
3. Used to obtain
- Vertically:
1. A small, soft, sweet fruit
2. A powerful playing card
3. A fisherman's tool
***
Given six three-letter words, you need to place them into a $3 \times 3$ grid so that these words all appear both horizontally and vertically.
Input Format
The input consists of $6$ lines, each containing a three-letter word in uppercase letters. They are guaranteed to be given in lexicographical order.
Output Format
If no solution exists, output $0$. Otherwise, output a $3 \times 3$ matrix of letters in three lines.
If multiple solutions exist, output the solution with the smallest lexicographical order of the nine characters formed by concatenating each row end-to-end.
Explanation/Hint
Translated by ChatGPT 5