Fișierul intrare/ieșire	datorii.in, datorii.out	Sursă	OJI 2020 clasa a 8-a
Autor	Emanuela Cerchez	Adăugată de	Matteo.Verz • Matteoalexandru
Timp de execuție pe test	0.75 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Datorii

Notă: aceasta este problema originală, dată la OJI 2020, și nu problema dată special pentru concursul IQ Academy, care era modificată pentru a vedea cine citește enunțul.

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

Cerință

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.

Date de intrare

Fișierul de intrare datorii.in conține pe prima linie un număr natural C reprezentând cerința care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află un număr natural D care reprezintă numărul de înregistrări existente în lista datoriilor firmelor. Pe următoarele D linii sunt descrise datoriile firmelor, în forma specificată în enunț, câte o datorie pe o linie.

Date de ieșire

Fișierul de ieșire datorii.out va conține răspunsul la cerința C specificată în fișierul de intrare. Dacă C=1 fișierul va conține un număr natural, reprezentând numărul de firme distincte care apar în lista menționată. Dacă C=2 fișierul va conține pentru fiecare dintre firmele distincte din lista menționată câte un singur triplet de forma X SD SP, unde X este numele firmei, iar SD și SP au semnificația din enunț pentru firma X; tripletele vor fi scrise astfel încât numele firmelor să apară în ordine lexicografică, fiecare triplet pe câte o linie a fișierului, iar X, SD și SP vor fi separate prin câte un singur spațiu.

Restricții

• Există în total cel mult 6000 de firme distincte în lista menționată de datorii.
• Numele unei firme este format din maximum 20 de caractere (litere mari și mici ale alfabetului englez, cifre, spații); se face distincție între literele mari și literele mici în numele firmelor; nu există alte restricții referitoare la numele firmelor.
• Două firme distincte au nume distincte. O firmă nu poate avea datorii la ea însăși.
• În descrierea unei datorii (X > Y S) există un singur spațiu între X și >, un singur spațiu între > și Y, respectiv un singur spațiu între Y și S.
• 1 ≤ D ≤ 80000
• Sumele datorate de firme sunt numere naturale nenule ≤ 10⁶.
• Dacă X și Y sunt numele a două firme distincte, iar k (k ≥ 0) este valoarea maximă cu proprietatea că secvența formată din primele k caractere din X este identică cu secvența formată din primele caractere din Y, spunem că X precedă din punct de vedere lexicografic pe Y dacă X are doar k caractere sau dacă al (k+1)-lea caracter din X este mai mic decât al (k+1)-lea caracter din Y.
• Pentru teste valorând 30 de puncte cerința este 1.
• Pentru teste valorând 60 de puncte cerința este 2.
• Pentru teste valorând 40 de puncte D ≤ 1000.
• Pentru teste valorând 45 de puncte numele firmelor nu conțin spații.
• Se acordă 10 puncte din oficiu pentru rezolvarea exemplelor. Pomană de la comisie.

Exemplu