Fișierul intrare/ieșire hole.in, hole.out Sursă Shumen 2014 juniori
Autor Rusko Shikov Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii