Ambrosio SA


Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 3M

Author:
Problem types
Estructures de Dades, Matrius, Pensar!
Category
Codejam

Ambrosio, l’ambaixador d’Isabel Preysler, ha muntat una empresa de fer piràmides de Ferrero Rocher. Ara estan de modes les piràmides quadrades, en el qual es fan diversos tipus de quadrats. Per tant, el primer pis seria un quadrat d'1x1, el segon un de 3x3, el quart un de 5x5, etc.

Per a assegurar la qualitat, Ambrosio ha fet un sistema de visió per computador que consisteix a fer una foto desde dalt, i de cada àrea del quadrat que es veu, dir la distància a la càmera. En fer-se la foto desde dalt, es veu un quadrat, a on la casella del centre és la punta de la piràmide, i després es divideix en anells, cadascú representant un pis inferior. En l’exemple de la foto, el pis de dalt està en vermell, el segon en blau i la base en verd.

Una piràmide es considera ben feta si cada pis està més elevat que l’anterior, o, cosa equivalent, si totes les peces de Ferrero d’un anell estan a menys distància de la càmera que la del següent anell

Entrada

La primera línea és el nombre de casos.

Cada cas comença amb un nombre \(N\) que indica la mida de la matriu quadrada. Després \(N*N\) nombres que defineixen la piràmide de Ferreros vista desde dalt. \(N\) sempre serà senar i estarà entre 1 i 999

Sortida

Si la piràmide de Ferreros compleix els estrictes requeriments d’Ambrosio (no hi ha cap ferrero que estigui igual o més lluny de la càmara que un ferrero d’un pis inferior), es dirà “OK”. En cas contrari, “NO”.

Per cert, us heu fixat que la memòria d’aquest problema és molt més baixa que la que donem habitualment?

Exemple d'Entrada

4
5
5 5 5 5 5
5 3 3 3 5
5 3 1 3 5
5 3 3 3 5
5 5 5 5 5
5
5 5 5 5 5
5 3 3 3 5
5 3 1 5 5
5 3 3 3 5
5 5 5 5 5
5
8 8 8 8 7
9 4 5 6 7
9 3 2 5 7
9 4 5 6 7
7 8 9 7 8
5
8 8 8 8 7
9 4 5 6 7
9 7 2 5 7
9 4 5 6 7
7 8 9 7 8

Exemple de Sortida

OK
NO
OK
NO

Comments

There are no comments at the moment.