Kocka
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 70\) points
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 un\(it-si\)zed cubes made out
of metal bars.
While observing the cube, an interesting problem came to his mind. Here follows the t\(wo-di\)mensional
version of the problem, since nobody likes problems involving 3D objects:
You’re given \(N\) × \(N\) 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 \(N\) rows he wrote how many empty field 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 numb\(er -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 4 \(N\) numbers in total, as he wrote \(N\) 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.
In test cases worth 40% of total points, it will hold that \(N\) ≤ 1000.
The first line contains a positive integer \(N\) (1 ≤ \(N\) ≤ 100 000), dimension of the square.
The second line contains \(N\) integers \(L\) {i} (-1 ≤ \(L\) < \(N\) ), numbers obtained by watching the square from
its left side, in order from 1 {st}{ } to \(N\) {th}{ } row.
The second line contains \(N\) integers \(R\) {i} (-1 ≤ \(R\) < \(N\) ), numbers obtained by watching the square from
its right side, in order from 1st to \(N\) {th}{ } row.
The second line contains \(N\) integers \(U\) {i} (-1 ≤ \(U\) < \(N\) ), numbers obtained by watching the square from
its top side, in order from 1 {st}{ } to \(N\) {th}{ } column.
The second line contains N integers \(D\) {i} (-1 ≤ \(D\) < \(N\) ), numbers obtained by watching the square from
its bottom side, in order from 1 {st}{ } to \(N\) {th}{ } column.
If it is possible to from a square which satisfies the given conditions, print “DA” (Croatian for yes,
without quotation marks), otherwise print “NE” (Croatian for no).
3
-1 2 0
-1 0 1
2 2 1
0 0 1
3
-1 0 1
-1 2 1
-1 2 -1
1 0 -1output
DA
NEClarification of the first test sample:
2
2
1
-1
-1
2
0
0
1
0
0
1
평가 및 의견
Kocka
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kocka