COCI '19 Contest 6 #4 Skandi

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 10.0s
Memory limit: 512M

Problem types

Dragica is a captain of a local semi-professional bowling team, she is a passionate chef and probably one of the best crossword puzzle solvers in Croatia. A crossword puzzle consists of N \times M squares arranged in N rows and M columns. Some of the squares are empty (and should be filled with letters by answering questions) and some of the squares are filled. Filled squares contain at most two questions which should either be answered horizontally to the right or vertically downwards. The answers to the questions are written in the empty squares before until we reach the crossword bound or an initially-filled square. An initially-filled square contains a horizontal question if a square to the right exists and is empty. Analogously, an initially-filled square contains a vertical question if a square beneath it exists and is empty.

Dragica usually knows all the answers to the crossword puzzle questions, but wishes to read and answer as few questions as possible and still solve the entire crossword puzzle. Help her achieve her goal.

Input

The first line contains integers N and M (2 \le N, M \le 500) from the task description.

Each of the next N lines contain M characters 0 or 1, where 0 denotes an empty square which should be filled by answering a question and 1 denotes an initially filled square which may contain at most two questions as explained in the task description. The first row and first column will be filled with 1 characters.

It is guaranteed that there will be at least one character 0 in the input.

Output

In the first line, you should output the minimal number of questions that can be answered in order to solve an entire crossword puzzle. Let's denote that number with X.

Each of the next X lines should describe one question that should be answered. The question description should be printed in the format R C direction, where R is the row number of the question, C is the column number of the question and direction is either DESNO (Croatian for RIGHT) or DOLJE (Croatian for DOWN) depending on whether Dragica should answer the vertical or horizontal question.

If there are multiple solutions, output any of them.

Scoring

Subtask Score Constraints
1 18 There will be at most 9 squares with 1
2 32 N \le 500 and M \le 10
3 60 No additional constraints.

If your solution outputs the first line correctly on each test case of a subtask, but it fails to correctly output the other lines in some test case, you will score 50\% of the allocated points for that subtask.

Sample Input 1

4 5
11111
10000
10000
10000

Sample Output 1

3
2 1 DESNO
3 1 DESNO
4 1 DESNO

Sample Input 2

6 4
1111
1011
1000
1011
1010
1000

Sample Output 2

4
1 2 DOLJE
4 4 DOLJE
5 3 DOLJE
3 1 DESNO

Sample Input 3

9 8
11111111
10000000
10001000
10010001
11100001
10100110
10001000
10100001
10010001

Sample Output 3

14
5 2 DOLJE
5 8 DOLJE
8 3 DOLJE
2 1 DESNO
3 1 DESNO
3 5 DESNO
4 1 DESNO
4 4 DESNO
5 3 DESNO
6 3 DESNO
7 1 DESNO
7 5 DESNO
8 3 DESNO
9 4 DESNO

Explanation of Sample Output 3

An example of a real crossword puzzle which is equivalent to the one described in this example is given on the next page. Initially-filled squares are colored black and those squares that contain at least one question are enumerated. Below the puzzle, you can see the questions that should be solved to-the-right (column "across") and those that should be solved downwards (column "down"). Note that some initially-filled squares contain no questions, some contain a single question (e.g. 8 and 13), while some contain two questions (e.g. 10 and 12). In order to solve this crossword puzzle, you need to know the answers to at least 14 questions that are listed in the output. Can you solve it?

1234567
8
910
1112
131415
16171819
2021
2223
2425
Across:

8. Father of dynamic programming, Richard
9. Frames per second
10. Exclamation when bullfighting
11. chr(115) * 2 in Python
12. Internet of things
14. Croatian version of COCI
16. Lexicographically smallest word
17. International system of units
19. Fictional character from James Bond
20. Balkan olympiad in informatics
21. Contest on Topcoder
22. Boron
23. Special pointer in C
24. Artificial intelligence
25. Popular encryption algorithm
Down:

1. Breadth first search
2. Machine epsilon constant
3. Unix command (contents of a directory)
4. Sixteenth letter of Croatian alphabet
5. REM hit - Man on the ____
6. Plural of altus
7. Croatian negation
10. International olympiad in informatics
12. Croatian computer science association
13. Palindromic pop-group from Sweden
15. Sqrt decomposition algorithm
17. Oxygen
18. Bad news when submitting a solution
19. Clear screen in QBasic
21. Last and first vowel
23. Iodine

Comments

There are no comments at the moment.