Fişierul intrare/ieşire:hole.in, hole.outSursăShumen 2014 juniori
AutorRusko ShikovAdăugată defrancuCristian Francu francu
Timp execuţie pe test5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Hole

Un zid pătrat de mărime N x N este construit din N2/2 cărămizi lipite una de alta. Fiecare cărămidă are mărimea 2 × 1. Cărămizile sînt numerotate de la 1 la N2/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ă,

Trebuie să facem o gaură dreptunghiulară în zid pentru a introduce o fereastră. Gaura trebuie să respecte următoarele cerinţe:

  1. Marginile să fie paralele cu marginile zidului
  2. Gaura nu trebuie să atingă nici una din marginile zidului (gaura trebuie să fie complet "înăuntrul" zidului)
  3. 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)

Cerinţă

Scrieţi un program care determină gaura dreptunghiulară de arie maximă care îndeplineşte cerinţele date.

Date de intrare

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.

Date de ieşire

Î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.

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)

Exemplu

hole.inhole.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici