.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » linie

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
linie


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

Se consideră o tablă de şah de dimensiune n. Se ştie că în fiecare pătrăţel se găseşte câte o piesă de şah. Fiecare piesă de şah are o anumită importanţă, dată de o valoare scrisă pe ea. Valoarea piesei este un număr natural. Se doreşte separarea pieselor de şah printr-o linie frântă formată numai din segmente (laturi) ale pătrăţelelor tablei, în două regiuni (regiunea din stânga şi regiunea din dreapta) astfel încât:
• să nu existe două segmente orizontale pe aceeaşi dreaptă orizontală;
• să nu existe două segmente verticale pe aceeaşi linie de pătrăţele ale tablei;
• pe fiecare linie cu pătrăţele a tablei de şah există măcar un element atât în regiunea din stânga, cât şi în regiunea din dreapta;
• linia frântă începe pe prima linie de pătrăţele şi se termină pe ultima linie de pătrăţele;
• valoarea absolută a diferenţei dintre suma elementelor regiunii din stânga şi suma elementelor regiunii din dreapta este minimă.

Cerinţă

Se cere să se determine o linie frântă cu proprietăţile anterioare.

Date de intrare

Fişierul de intrare linie.in conţine pe prima linie numărul n. Pe fiecare dintre următoarele n linii se află câte n numere naturale separate prin câte un spaţiu, reprezentând elementele tabloului.

Date de ieşire

În fişierul de ieşire linie.out se va scrie pe prima linie suma elementelor regiunii din stânga. Pe cea de a doua linie se va scrie suma elementelor regiunii din dreapta. Pe cea de a treia linie se vor scrie n numere naturale separate prin câte un spaţiu. Al i-lea număr de pe linia 3 a fişierului de ieşire reprezintă indicele maxim de coloană al elementelor care se află pe tablă în regiunea din stânga pe linia i. În cazul în care există mai multe soluţii în fişier se va scrie una singură.

Restricţii

2 <= n < 13
Toate elementele tabloului sunt numere naturale <= 32000.

Exemple

linie.inlinie.outExplicaţii
3 1 2 5 3 5 1 4 2 1 12 12 2 1 2 Linia frântă este următoarea:



autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor