Avem o placă pătrată cu latura de N unităţi (N - par). Ea este împărţită în N*N pătrate cu latura 1. De pe al doilea şi penultimul rând lipsesc cele două pătrate de la mijloc. De pe al treilea şi antepenultimul rând lipsesc cele 4 pătrate din mijloc, şi aşa mai departe. Iată cum arată placa de dimensiune 8 (pătratele marcate cu x lipsesc).
Cerinţă
Dorim să plasăm în pătratele rămase cât mai multe dominouri de dimensiuni 2X1 (sau 1X2, adică dominourile pot fi rotite).
Date de intrare
Fişierul de intrare romb.in are pe prima linie un singur număr natural N, dimensiunea plăcii.
Date de ieşire
Pe prima linie a fişierului romb.out se va găsi un singur număr M care reprezintă numărul maxim de dominouri ce pot fi plasate pe placă. Pe fiecare dintre următoarele N linii se găsesc câte N numere naturale, separate prin câte un spaţiu, reprezentând configuraţia plăcii acoperite. În pătratele lipsă se va scrie -1. În pătratele rămase neacoperite se va scrie 0. În pătratele ocupate de dominoul plasat primul se va scrie 1, în cele ocupate de dominoul plasat al doilea se va scrie 2, şi asa mai departe până la scrierea valorii M (în pătratele ocupate de ultimul domino plasat).
Restricţii
4 <= N <= 200, N par
Dominourile nu se pot suprapune parţial sau total
Dominourile trebuie plasate strict în interiorul plăcii
Este acceptată orice configuraţie corectă
Pentru afişarea corectă doar a numărului maxim de dominouri se acordă 20% din punctaj
