#3437
Î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țe
Cunoscând lista cu datoriile firmelor, scrieți un program care să rezolve următoarele cerințe:
- determină numărul de firme distincte care apar în această listă;
- 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, undeSDreprezintă suma totală a datoriilor pe care firma le are către alte firme, iarSPeste totalul sumelor pe care firma trebuie să le primească de la alte firme.
Date de intrare
Fișierul de intrare datorii1.in conține pe prima linie un număr natural C reprezentând cerința care
trebuie să fie rezolvată (1 su 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 și precizări
- Există în total cel mult
6000de firme distincte în lista menționată de datorii. - Numele unei firme este format din maximum
20de 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 întreXși>, un singur spațiu între>șiY, respectiv un singur spațiu întreYșiS. 1 ≤ D ≤ 80000- Sumele datorate de firme sunt numere naturale nenule
≤106. - Dacă
XșiYsunt numele a două firme distincte, iark(k≥0) este valoarea maximă cu proprietatea că secvența formată din primelekcaractere dinXeste identică cu secvența formată din primele caractere dinY, spunem căXprecedă din punct de vedere lexicografic peYdacăXare doarkcaractere sau dacă alk+1-lea caracter dinXeste mai mic decât alk+1-lea caracter dinY. - Pentru teste valorând 30 de puncte cerinţa este
1. Pentru teste valorând 60 de puncte cerinţa este2.
Pentru teste valorând 40 de puncteD≤1000. Pentru teste valorând 45 de puncte numele firmelor nu
conțin spaţii.
Exemplul 1
datorii.in
1 4 Vasile Inc > Anatolia 100 ana > Anatolia 10 ana > Vasilescu Inc 5 Popa25 PF > Anatolia 30
datorii.out
5
Exemplul 2
datorii.in
2 5 Vasile Inc > Anatolia 100 ana > Anatolia 10 ana > Vasilescu Inc 5 Popa25 PF > Anatolia 30 Popa25 PF > ana 50
datorii.out
Anatolia 0 140 Popa25 PF 80 0 Vasile Inc 100 0 Vasilescu Inc 0 5 ana 15 50
Indicații de rezolvare
Autor: prof. Emanuela Cerchez, Colegiul Naţional “Emil Racoviţă” Iaşi
Vom citi datoriile firmelor succesiv, linie cu linie, într-un şir de caractere s.
Suntem interesaţi doar de firmele distincte, ca urmare vom reţine evidenţa firmelor distincte într-un vector F. O firmă va fi o structură cu 3 câmpuri (un şir de caractere reprezentând numele acesteia şi două numere naturale SD şi SP, reprezentând totalul datoriilor firmei către alte firme, respectiv suma totală pe care firma trebuie să o primească de la alte firme).
Vom prelucra şirul s, care reprezintă o datorie, în scopul de a extrage numele celor două firme (X şi Y) şi suma datorată S. Deoarece numele firmelor pot conţine şi ele cifre, vom parcurge şirul s de la sfârşit către început, construind suma S, din cifrele întâlnite până la primul spaţiu. Eliminăm din şirul s suma S, prin trunchierea acestuia. Şirul s va avea acum forma X > Y. Separăm şirul s în două subşiruri (unul care să reprezinte numele firmei X, celălalt numele firmei Y), ştiind că cele două nume sunt separate prin >. Vom căuta numele firmei X în vectorul F. Dacă acesta există deja în vectorul F, doar adăugăm suma S la câmpul SD al firmei cu numele X. Dacă nu există o firmă cu numele X, o adăugăm în vectorul F, iniţializând SD cu S şi SP cu 0.
În mod similar procedăm cu firma Y: o căutăm în vectorul F; dacă există deja adăugăm suma S la câmpul SP al firmei cu numele Y; dacă nu există o firmă cu numele Y, o adăugăm la vectorul F şi iniţializăm câmpul SD cu 0, iar SP cu S.
Căutarea numelui unei firme se poate face secvenţial în vectorul F, dar în acest caz se obţine punctaj parţial, din cauza depăşirii timpului de execuţie.
Observaţie: pentru teste valorând 45 de puncte, numele firmelor nu conţin spaţii şi deci etapa de prelucrare a şirului s este eliminată, citind separat X, Y, S.
Pentru un algoritm eficient, va fi necesar să facem o căutare binară în vectorul F. Pentru ca acest lucru să fie posibil, ar trebui ca, la fiecare pas, vectorul F să fie deja sortat lexiicografic după numele firmelor. Pentru aceasta, vom face o sortare prin inserare. Mai exact, de fiecare dată când adăugăm o nouă firmă în vectorul F, căutăm locul corect şi o inserăm direct în poziţia corectă, astfel încât F să rămână sortat.
#include <fstream>
#include <cstring>
#define LGMAX 21
#define LMAX 100
#define NMAX 6002
using namespace std;
ifstream fin("datorii.in");
ofstream fout("datorii.out");
struct firma
{
char nume[LGMAX];
long long int SD, SP;
} ;
int n, D, cerinta, lg;
firma F[NMAX];
char s[LMAX];
int cauta(char * s);
int main()
{int i, j, nr, p10, poz1, poz2;
char *p, c;
fin>>cerinta>>D;fin.get(c);
for (i=0; i<D; i++)
{
fin.getline(s,LMAX);
lg=strlen(s);
nr=0; p10=1;
for (j=lg-1; s[j]>='0' && s[j]<='9'; j--)
{
nr=nr+p10*(s[j]-'0');
p10*=10;
}
s[j]=0;
p=strchr(s,'>');
*(p-1)=0;
poz1=cauta(s); F[poz1].SD+=nr;
poz2=cauta(p+2); F[poz2].SP+=nr;
}
if (cerinta==1)
fout<<n<<'\n';
else
for (i=1; i<=n; i++)
fout<<F[i].nume<<' '<<F[i].SD<<' '<<F[i].SP<<'\n';
fout.close();
return 0;
}
int cauta(char * s)
{int st=0, dr=n+1, mij, i;
while (dr-st>1)
{
mij=(st+dr)/2;
if (strcmp(F[mij].nume,s)<0) st=mij;
else dr=mij;
}
if (dr<=n && strcmp(F[dr].nume,s)==0) return dr;
for (i=n; i>=dr; i--) F[i+1]=F[i];
n++;
F[dr].SD=F[dr].SP=0;
strcpy(F[dr].nume,s);
return dr;
}
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cctype>
#define MaxF 3001
using namespace std;
ifstream citeste("datorii.in");
ofstream scrie("datorii.out");
struct firma
{
char nume[21];
long long SP, SD;
};
int C, D;
firma v[62][MaxF];
int nrFirme = 0;
int nrF[62] = {0};
int apartine(char*);
int main()
{
char linie[500], numeFirma1[21], numeFirma2[21];
int i, j;
int suma;
int poz;
firma tmp;
int lista;
//citesc datele de intrare
citeste >> C >> D;
citeste.get();
for(i = 1; i <= D; ++i)
{
citeste.get(linie,500);
citeste.get();
//extrageDate(linie, numeFirma1, numeFirma2, suma);
//extrag datele
char *cuv,ii;
int z = 1;
ii = strlen(linie) - 1;
suma = 0;
while ( 48 <= linie[ii] && linie[ii] <= 57)
{
suma = suma + z * (linie[ii]-48);
z *= 10;
ii--;
}
ii++;
linie[ii-1] = '\0';
cuv = strchr(linie, '>');
strncpy(numeFirma1, linie, cuv - linie - 1);
numeFirma1[cuv - linie - 1] ='\0';
strcpy(numeFirma2, cuv+2);
//pun firmele la locul lor
poz = apartine(numeFirma1);
if(isdigit(numeFirma1[0]))
lista = numeFirma1[0] - '0';
else
if(isupper(numeFirma1[0]))
lista = 10 + numeFirma1[0] - 'A';
else
lista = 36 + numeFirma1[0] - 'a';
if(poz)
v[lista][poz].SD += suma;
else
{
nrFirme++;
nrF[lista]++;
strcpy(v[lista][nrF[lista]].nume,numeFirma1);
v[lista][nrF[lista]].SP = 0;
v[lista][nrF[lista]].SD = suma;
//mut firma la locul ei
for(j = nrF[lista]; j>1 && strcmp(v[lista][j].nume, v[lista][j-1].nume) < 0; j--)
tmp = v[lista][j], v[lista][j] = v[lista][j-1], v[lista][j-1] = tmp;
}
poz = apartine(numeFirma2);
if(isdigit(numeFirma2[0]))
lista = numeFirma2[0] - '0';
else
if(isupper(numeFirma2[0]))
lista = 10 + numeFirma2[0] - 'A';
else
lista = 36 + numeFirma2[0] - 'a';
if(poz)
v[lista][poz].SP += suma;
else
{
nrFirme++;
nrF[lista]++;
strcpy(v[lista][nrF[lista]].nume,numeFirma2);
v[lista][nrF[lista]].SP = suma;
v[lista][nrF[lista]].SD = 0;
//mut firma la locul ei
for(j = nrF[lista]; j>1 && strcmp(v[lista][j].nume, v[lista][j-1].nume) < 0; j--)
tmp = v[lista][j], v[lista][j] = v[lista][j-1], v[lista][j-1] = tmp;
}
}
if( C == 1)
{
scrie << nrFirme <<'\n';
}
else
{
for(i = 0; i < 62; ++i)
if(nrF[i])
for(j = 1; j <= nrF[i]; ++j)
scrie << v[i][j].nume << " " << v[i][j].SD << " " << v[i][j].SP << '\n';
}
citeste.close();
scrie.close();
return 0;
}
int apartine(char *denumire)
{
int st, dr, mij;
int lista;
if(isdigit(denumire[0]))
lista = denumire[0] - '0';
else
if(isupper(denumire[0]))
lista = 10 + denumire[0] - 'A';
else
lista = 36 + denumire[0] - 'a';
st = 1; dr = nrF[lista];
while(st <= dr)
{
mij = (st + dr)/2;
if(strcmp(v[lista][mij].nume, denumire) == 0)
return mij;
else
if(strcmp(v[lista][mij].nume, denumire) < 0)
st = mij + 1;
else
dr = mij - 1;
}
return 0;
}