Lista de probleme 2

Se consideră A un tablou bidimensional cu n linii, n coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul (lin, col, k), este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu |k|, definită astfel:

  1. Pentru k>0, zona este compusă din k linii:
    • pe prima linie a zonei se află elementele A[lin][col], A[lin][col+1], …, A[lin][col+k-1];
    • pe a doua linie a zonei se află elementele A[lin+1][col], A[lin+1][col+1], …, A[lin+1][col+k-2];
    • pe a treia linie a zonei se află elementele A[lin+2][col], A[lin+2][col+1], …, A[lin+2][col+k-3];
    • pe ultima linie a zonei se află elementul A[lin+k-1][col].
  2. Pentru k<0, zona este compusă din |k|=-k linii:
    • pe prima linie a zonei se află elementul A[lin-|k|+1][col];
    • pe a doua linie a zonei se află elementele A[lin-|k|+2][col-1], A[lin-|k|+2][col];
    • pe ultima linie a zonei se află elementele A[lin][col-|k|+1], A[lin][col-|k|+2],…, A[lin][col].

Suma elementelor ce compun o zonă triunghiulară se numește suma zonei.

Scrieţi un program care, cunoscând tabloul A şi Q zone triunghiulare, determină cea mai mare dintre sumele zonelor.

Într-o țară îndepărtată, economia este în criză. Cea mai mare problemă este lipsa de capital care creează blocaje financiare. De exemplu, o firmă X poate avea datorii către o firmă Y pe care nu le poate plăti, deoarece o altă firmă Z are datorii către firma X pe care nu le-a plătit, ş.a.m.d.

Există o listă cu toate datoriile firmelor sub forma următoare:

X > Y S

cu semnificaţia “firma X datorează firmei Y suma S”. Este posibil ca X să aibă mai multe datorii la firma Y (în funcţie de contractele derulate împreună) sau chiar ca X să aibă datorii la Y și Y să aibă datorii la X.

Cunoscând lista cu datoriile firmelor, scrieți un program care să rezolve următoarele cerințe:

  1. determină numărul de firme distincte care apar în această listă;
  2. realizează o situație financiară a firmelor distincte din această listă, scrise în ordine lexicografică; pentru fiecare firmă se vor determina două valori SD SP, unde SD reprezintă suma totală a datoriilor pe care firma le are către alte firme, iar SP este totalul sumelor pe care firma trebuie să le primească de la alte firme.