Datum sa najvećom zaradom - rešenje

11. DATUM SA NAJVEĆOM ZARADOM - REŠENJE

TEKST ZADATKA. Kvalifikacije za okružna takmičenja

Ovde će biti pokazana dva načina rešavanja, jedan je sa upotrebom dinamičkih nizova - vektora, a drugi je primenom rečnika podataka-mapa. Prvi način nije dovoljno efikasan za veliki broj podataka i u tom slučaju bi se dobila greška prilikom testiranja TLE(timeline exception). Međutim, rešavanjem na ovaj način bi prošlo oko 70% test primera. Drugi način je efikasan i za veliki broj podataka.

I način rešavanja - upotrebom dinamičkog niza

Za upotrebu vektora možete koristiti sledeći članak Dinamički niz-vectorDinamički niz-vector

Uputstvo:

Učitati podatke kao stringove red po red. Iz stringa izdvojiti prvo datum kao poseban string i zaradu posebno. Smestiti u dva niza. Datum prepraviti tako da prvo sadrži godinu, zatim mesec i na kraju dan, da bi lakše moglo da se izvrši sortiranje. Sortirati oba niza po datumu, od najstarijeg ka najnovijem datumu. Nizove prepisati u nove nizove, ali tako da datumi budu jedinstveni(ponavljaju se samo po jedanput), a zarada, koja odgovara tom datumu da bude u istoj poziciji samo u drugom nizu. Pri tome treba da bude zbir zarada sa istim datumom. Na kraju ispisati, prvi element niza zarade, jer je prvi element, zapravo najveća ostvarena zarada. Posle toga ispisati početne elemente niza sa datumima onoliko puta koliko ima datuma sa maksimalnom zaradom.

Rešenje:

Prvo treba uključiti potrebna zaglavlja:


#include < iostream >


#include< vector >

#include< string >

#include< iomanip >

Zatim unutar main metode, kreiramo vektore kao i ostale potrebne podatke


int n,ind=0;//n-broj stavki na racunu

      cin>>n; //Ucitavanje n

   
     cin.ignore();//Prazni string buffer

 
    vector< string >datumiSvi;// datumi koji se izdvajaju iz ucitanih redova 

    vector< string >datumi; //jedinstveni datumi

    vector< string >istiDatumi;

    vector< double >novac; //zarada izdvojena iz ucitanih redova

    vector< double >pazar;

    string line;  //jedan ucitani red

    int pozicije[2]= {2,5}; //pozicije na kojima se nalaze karakteri za razdvajanje pod stringova

Unutar petlje se vrši učitavanje po jednog reda, a zatim razdvajanje datuma i zarade i njihovo smeštanje u posebne nizove.


while(getline(cin,line)) //ucitava sledeci red sa standardnog ulaza

    {



        int poz=line.find(" ");// space karakter se koristi za razdvajanje unetog reda teksta na datum i zaradu

        string datum=line.substr(0,poz);//izdvaja datum

        string dd=datum.substr(0,pozicije[0]);//izdvaja dan iz datuma


        string mm=datum.substr(pozicije[0]+1,2);//izdvaja mesec iz datuma

        string yyyy=datum.substr(6);// izdvaja godinu iz datuma

        string datumKontra=yyyy+mm+dd;//pise datum u obliku "yyyymmdd"

  
        double zarada=stod(line.substr(poz+1));//izdvaja zaradu kao string, a zatim pretvara u double podatak

        datumiSvi.push_back(datumKontra); //dodaje datum na kraj vektora "datumiSvi"

        novac.push_back(zarada); //dodaje zaradu na kraj vektora "novac"

        ind++; //povecava broj ciklusa za 1

        if(ind==n)break; // prekida petlju kada se ucita "n" redova


    }

Zatim se učitani vektori sortiraju. Ovde je za sortiranje koriscena metoda izbora. Algoritam možete pogledati na webstrani: Sortiranje nizova


//sortiranje metodom izbora

    for(int i=0; i < datumiSvi.size()-1; i++)

    {


        for(int j=i+1; j < datumiSvi.size(); j++)

        {


            string d1=datumiSvi[j];

            string d2=datumiSvi[i];

            bool premestanje=d1 < d2;

            if(premestanje)

            {


                double b=novac[i];

                novac[i]=novac[j];

                novac[j]=b;

                string a=datumiSvi[i];

                datumiSvi[i]=datumiSvi[j];

                datumiSvi[j]=a;


            }


        }


    }

Sledeće što treba uraditi je sabrati sve zarade u toku istog datuma i formirati dva nova niza zarade i datuma, tako da se svaki datum pojavljuje samo jednom i da u drugom nizu, na odgovarajućoj poziciji bude zbirna zarada za odgovarajući datum.


/*racunanje zbirne zarade*/

    string pretDatum=""; //prethodni datum

    for(int i=0,dan=-1; i < datumiSvi.size(); i++) /*prolazak kroz ucitani niz sa svim datumima*/

    {


        string datum=datumiSvi[i]; /*izdvojen datum na tekucoj poziciji niza*/

        double nov=novac[i]; /*izdvojena zarada iz niza zarada na tekucoj poziciji*/

        if(datum != pretDatum) /*ako se datum razlikuje od prethodnog u nizu*/

        {


            dan++; /*povecava poziciju prepisanog niza samo ako se datum razlikuje od prethodnog*/

            datumi.push_back(datum); /*dodaje datum u nov vektor za datume(jedinstvene)*/

            pazar.push_back(nov); /* dodaje zaradu u nov niz */

            

        }

        else /*ako su datumi jednaki */

        {

            
            pazar[dan]=pazar[dan] + nov; /*ako je rec o istom datumu, sabiraju se zarade */


        }

        pretDatum = datum; /*tekuci datum postaje prethodni za sledeci ciklus */


    }

Zatim se novi nizovi sortiraju, po zaradi, od najvece ka najmanjoj.


 /*sortiranje po zaradi, opadajuce */

    for(int i=0; i < pazar.size()-1; i++)

    {


        for(int j=i+1; j < pazar.size(); j++)

        {


            if(pazar[j] > pazar[i])

            {


                double b=pazar[i];

                pazar[i]=pazar[j];

                pazar[j]=b;

                string a=datumi[i];

                datumi[i]=datumi[j];

                datumi[j]=a;


            }



        }


    }

Ostaje još da se ispiše najveća zarada, kao i svi datumi sa tom najvećom zaradom.


 double pret=-1;

    
    for(int i = 0; i < pazar.size(); i++)

    {


        double nov=pazar[i];

        if(i==0)


            cout <<  fixed << setprecision(2) << nov << endl;


        if(i>0 && nov!=pret)break;


        string god=datumi[i].substr(0,4);


        string mes=datumi[i].substr(4,2);

        string dan=datumi[i].substr(6,2);

        cout << dan + "-" + mes + "-" + god << endl;


        pret=nov;


    }

Posebna metoda za sortiranje, sa nešto efikasnijim algoritmom

Ako malo bolje napišemo prethodni kod, sa upotrebom posebne metode za sortiranje i za algoritam sortiranja koristimo metodu umetanja, koja se brže izvršava nego metoda izbora, kod bi bio:

#include < iostream >
#include < vector >
#include < string >
#include < iomanip >

using namespace std;
void sortiranje(vector &datumiSvi, vector &novac)
{

//sortiranje niza metodom umetanja
int j;
for(int i=1; i < datumiSvi.size(); i++)
{

string b=datumiSvi[i];
double a=novac[i];
for(j=i-1; j>=0; j--)
{

if(datumiSvi[j] > b)
{

datumiSvi[j+1]=datumiSvi[j];
novac[j+1]=novac[j];

}
else break;

}
datumiSvi[j+1]=b;
novac[j+1]=a;

}

int main()
{

int n,ind=0;
cin >> n;
cin.ignore();
vector < string > datumiSvi;
vector < string > datumi;
vector < string > istiDatumi;
vector < double >novac;
vector < double >pazar;
string line;
int pozicije[2]= {2,5};
while(getline(cin,line))
{

int poz=line.find(" ");
string datum=line.substr(0,poz);
string dd=datum.substr(0,pozicije[0]);
string mm=datum.substr(pozicije[0]+1,2);
string yyyy=datum.substr(6);
string datumKontra=yyyy+mm+dd;
double zarada=stod(line.substr(poz+1));
datumiSvi.push_back(datumKontra);
novac.push_back(zarada);
ind++;
if(ind==n)break;

}
//sortiranje
sortiranje(datumiSvi,novac);

//racunanje zarade
string pretDatum="";
for(int i=0, dan=-1; i < datumiSvi.size(); i++)
{

string datum=datumiSvi[i];
double nov=novac[i];
if(datum!=pretDatum)
{

dan++;
datumi.push_back(datum);
pazar.push_back(nov);

}
else
{

pazar[dan]=pazar[dan]+nov;

}
pretDatum=datum;

}
//sortiranje po zaradi
for(int i=0; i < pazar.size()-1; i++)
{

for(int j=i+1; j < pazar.size(); j++)
{

if(pazar[j] > pazar[i])
{

double b=pazar[i];
pazar[i]=pazar[j];
pazar[j]=b;
string a=datumi[i];
datumi[i]=datumi[j];
datumi[j]=a;

}

}
double pret=-1;
/* ispis */
for(int i=0; i < pazar.size(); i++)
{

double nov=pazar[i];
if(i==0)

cout << fixed << setprecision(2) << nov << endl;

if(i>0 && nov!=pret)break;
string god=datumi[i].substr(0,4);
string mes=datumi[i].substr(4,2);
string dan=datumi[i].substr(6,2);
cout << dan + "-" + mes + "-" + god << endl;
pret=nov;

}
return 0;

}

II način rešavanja - upotrebom rečnika podataka

Mapa se ovde koristi za smeštaj parova podataka ključa i vrednosti. Kao ključ se koriste datumi, a kao vrednosti zarade. Ono što je potrebno znati o mapama naći ćete na sledećem linku: Rečnik podataka-mape u C++

Da bi koristili mape potrebno je uključiti zaglavlje "map". Osim "map", postoji i multimap. Dok "map" tip podatka smešta samo jedinstvene ključeve, u našem slučaju datume, "multimap" može ponavljati ključeve. U ovom primeru je pogodnije koristiti "map". Ono što takođe treba imati u vidu je da su ključevi u mapi sortirani po rastućem redosledu. Da bi bili sortirani po opadajućem redosledu, kao treći parametar se uvodi komparator cmp koji je definisan kao funkcija koja vraća logički podatak bool.

Rešenje:

#include < iostream >
#include < vector >
#include < string >
#include< map >
#include< algorithm >
#include < functional >
#include < iomanip >

using namespace std;
// Comparator function to sort pairs
// according to second value
bool cmp(pair< string, double >& a, pair< string, double >& b)
{

return a.second > b.second;

}

int main()
{

int n,ind=0;
cin >> n;
cin.ignore();
map < string, double > dnevneZarade;
string line;
int pozicije[2]= {2,5};
while(getline(cin,line))
{

int poz=line.find(" ");
string datum=line.substr(0,poz);
string dd=datum.substr(0,pozicije[0]);
string mm=datum.substr(pozicije[0]+1,2);
string yyyy=datum.substr(6);
string datumKontra=yyyy+mm+dd;
double zarada=stod(line.substr(poz+1));
map<string,double >::iterator itKey;
itKey=dnevneZarade.find(datumKontra);//Trazi poziciju istog datuma u mapi, ako ga ima
if(itKey == dnevneZarade.end())//ako je pronasao isti datum
{

dnevneZarade.insert(pair<string,double>(datumKontra,zarada));

}
else
{

itKey->second += zarada;

}
ind++;
if(ind==n)break;

}
//ispisivanje podataka smeštenih unutar mape
map < string, double>::iterator itr;
// Deklarisanje vektora parova iz mape
vector < pair< string, double > > A;
// Copy key-value pair from Map
// to vector of pairs
for (auto& it : dnevneZarade)
{

A.push_back(it);

}
sort(A.begin(),A.end(),cmp);
vector < pair< string, double > >::iterator itA;
vector<pair < string, double>>::iterator itrPre=A.begin();
int i=0;
vector < pair< string, double > >::iterator itrR;
for(itrR = A.begin(); itrR !=A.end(); ++itrR )
{

if(i==0)

cout << fixed << setprecision(2) << itrR->second << endl;

double zarada=itrR->second;
double zaradaPret=itrPre->second;
if(i>0 && zarada != zaradaPret)

break;

string datum=itrR->first;
string god=datum.substr(0,4);
string mes=datum.substr(4,2);
string dan=datum.substr(6,2);
cout << dan + "-" + mes + "-" + god << endl;
zaradaPret=zarada;

}
return 0;

}

Povratak
|< Kvalifikacije za okružna takmičenja

11. DATUM SA NAJVEĆOM ZARADOM - REŠENJE

I način rešavanja - upotrebom dinamičkog niza

Uputstvo:

Rešenje:

Posebna metoda za sortiranje, sa nešto efikasnijim algoritmom

II način rešavanja - upotrebom rečnika podataka

Rešenje:

Podešavanja kolačića