Diferențe pentru problema/hole între reviziile #1 si #6

hole

Hole

== include(page="template/taskheader" task_id="hole") ==

Poveste și cerință...

Un zid pătrat de mărime _N x N_ este construit din _N[^2^]/2_ cărămizi lipite una de alta. Fiecare cărămidă are mărimea 2 x 1. Cărămizile sînt numerotate de la 1 la _N[^2^]/2_. Unele cărămizi sînt așezate orizontal, altele sînt așezate vertical. În perete nu există găuri. În exemplul de mai jos fiecare pereche de pătrate cu același număr reprezintă o cărămidă,
 
!>problema/hole?hole.gif!
 
Trebuie să facem o gaură dreptunghiulară în zid pentru a introduce o fereastră. Gaura trebuie să respecte următoarele cerințe:
 
# Marginile să fie paralele cu marginile zidului
# Gaura nu trebuie să atingă nici una din marginile zidului (gaura trebuie să fie complet "înăuntrul" zidului)
# Cînd dăm gaura nu avem voie să spargem nici o cărămidă (toate marginile găurii trebuie să treacă numai prin margini ale cărămizilor)
 
h2. Cerință
 
Scrieți un program care determină gaura dreptunghiulară de arie maximă care îndeplinește cerințele date.

h2. Date de intrare

Fișierul de intrare $hole.in$ ...

Fișierul de intrare $hole.in$ conține pe prima linie numărul _N_ - mărimea laturilor zidului. Urmează _N_ rînduri a cîte _N_ întregi fiecare, care descriu configurația cărămizilor zidului. Dacă există mai mult de o soluție programul va afișa una singură, oricare din cele posibile.

h2. Date de ieșire

În fișierul de ieșire $hole.out$ ...

În fișierul de ieșire $hole.out$ programul vostru va scrie 5 numere separate prin spații - aria, linia și coloana colțului de sus-dreapta și linia și coloana colțului din dreapta-jos ale dreptunghiului găsit.

h2. Restricții

* $... ≤ ... ≤ ...$

* $3 ≤ _N_ ≤ 1000$
* În 45% din teste $_N_ ≤ 100$
* _N_ este număr par
* Colțul din stînga-sus al zidului are coordonate (1,1)

h2. Exemplu
table(example).

|_. hole.in |_. hole.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. hole.in |_. hole.out |_. Explicație |
| 6
1 1 4 4 13 14
2 3 3 5 13 14
2 6 7 5 12 12
9 6 7 10 10 15
9 8 8 11 11 15
16 16 17 17 18 18
| 8 2 2 5 3
| Datele corespund figurii de mai sus. Gaura dreptunghiulară maximă are suprafață 8.
Ea se obține eliminînd cărămizile 3, 6, 7 și 8.
|

== include(page="template/taskfooter" task_id="hole") ==