Datorii1

#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:

  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 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 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 ≤106.
  • 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.

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;
}