## COCI '18 Contest 2 #2 Kocka

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

I'm again in the cube!

I'm again in the cube!

While watching the kids' playground in the early morning hours, the author of this task caught sight of an interesting object: a cube made out of metal bars, composed of many unit-sized cubes made out of metal bars.

While observing the cube, an interesting problem came to his mind. Here follows the two-dimensional version of the problem, since nobody likes problems involving 3D objects:

You're given matrix (square for reference). Some of the fields in the square are blocked and some are empty. The author was watching the square from each of its 4 sides. Firstly, he looked at the square from its left side, and for each of its rows he wrote how many empty fields there were in the row in front of the first blocked field he could see. If there were no blocked fields in a row, he wrote down the number -1. Then he repeated the same procedure looking at the square from its right, top and bottom side, in that order.

By doing so, he wrote numbers in total, as he wrote numbers for each side of the square. However, unknown villains destroyed his square and the only thing left were the numbers he had written down. The author of the task wonders if those numbers make any sense, i.e. if it is possible to form a square for which the same sequence of numbers will be obtained by doing the described procedure.

#### Input Specification

The first line contains a positive integer , dimension of the square.

The second line contains integers , numbers obtained by watching the square from its left side, in order from to row.

The third line contains integers , numbers obtained by watching the square from its right side, in order from to row.

The fourth line contains integers , numbers obtained by watching the square from its top side, in order from to column.

The fifth line contains integers , numbers obtained by watching the square from its bottom side, in order from to column.

#### Output Specification

If it is possible to form a square which satisfies the given conditions, print DA (Croatian for yes), otherwise print NE (Croatian for no).

#### Scoring

In test cases worth 40% of total points, it will hold that .

#### Sample Input 1

3
-1 2 0
-1 0 1
2 2 1
0 0 1

#### Sample Output 1

DA

#### Sample Input 2

3
-1 0 1
-1 2 1
-1 2 -1
1 0 -1

#### Sample Output 2

NE