dd-mm-gggg iznos

Iznos je realan broj zaokružen na dve decimale.

Izlaz

Na standardni izlaz najpre ispisati maksimalan dnevni pazar, zaokružen na dve decimale, a zatim u narednim redovima datume kada je taj maksimalni iznos naplaćen.

Ako postoji više takvih datuma, treba ih ispisati redom od najstarijeg do najnovijeg.

Primer

Ulaz

5
03-07-2021 340.00
05-04-2021 285.50
03-07-2021 100.50
04-07-2021 270.00
05-04-2021 155.00

Izlaz

440.50
05-04-2021
03-07-2021

Ideja rešenja

Svaki fiskalni račun sadrži dva podatka: datum i iznos. Potrebno je da saberemo sve iznose koji pripadaju istom datumu.

Na primer, ako se pojave računi:

03-07-2021 340.00
03-07-2021 100.50

za taj datum ukupan pazar je:

340.00 + 100.50 = 440.50

Isto uradimo za svaki datum.

Za čuvanje ovih podataka veoma je pogodna struktura map. Kao ključ koristićemo datum, a kao vrednost ukupan pazar tog dana.

Na primer, sadržaj mape može izgledati ovako:

20210405 440.50
20210703 440.50
20210704 270.00

Pošto map održava ključeve sortirane, datumi će automatski biti poređani hronološki, pod uslovom da datum čuvamo u obliku yyyymmdd.

Zašto datum pretvaramo u oblik yyyymmdd?

Datum iz ulaza ima oblik:

dd-mm-gggg

Takav tekst nije pogodan za jednostavno leksikografsko sortiranje. Na primer:

05-04-2021
03-07-2021

Ako želimo da se datumi sortiraju po godini, zatim mesecu, pa danu, možemo ih pretvoriti u:

20210405
20210703

Sada važi isto pravilo kao kod normalnog poređenja datuma: prvo se poredi godina, zatim mesec, pa dan.

Zato se kao ključ mape koristi string oblika yyyymmdd.

Kako računamo novac?

Iznos je u zadatku dat sa dve decimale. Iako bismo mogli koristiti double, kod novca je sigurnije koristiti celobrojne vrednosti.

Na primer, iznos:

285.50

možemo posmatrati kao:

28550 centi

Tako se sve sabiranje obavlja pomoću tipa long long, bez problema sa zaokruživanjem koji mogu nastati pri računanju sa realnim brojevima.

Na kraju cente ponovo pretvaramo u dinare i cente prilikom ispisa.

Algoritam

1. Učitati broj računa n.
2. Za svaki račun učitati datum i iznos.
3. Datum pretvoriti iz oblika dd-mm-gggg u yyyymmdd.
4. Iznos pretvoriti u cente.
5. U mapi, za odgovarajući datum, dodati iznos na postojeći dnevni pazar.
6. Proći kroz mapu i pronaći najveći dnevni pazar.
7. Ponovo proći kroz mapu i ispisati sve datume sa tim pazarom.

Pošto je mapa sortirana po datumu, svi datumi sa maksimalnim pazarom biće automatski ispisani hronološki.

Kompletno C++ rešenje

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

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

using namespace std;

// Funkcija pretvara iznos oblika "285.50" u cente.
// Na primer:
// "285.50" -> 28550
long long uCente(string iznos)
{
    int tacka = iznos.find('.');

    // Deo pre decimalne tačke predstavlja cele dinare.
    long long dinari = stoll(iznos.substr(0, tacka));

    // Deo posle decimalne tačke predstavljaju cente.
    long long cente = stoll(iznos.substr(tacka + 1, 2));

    return dinari * 100 + cente;
}

// Funkcija pretvara datum iz oblika dd-mm-gggg
// u oblik yyyymmdd.
//
// Na primer:
// "05-04-2021" -> "20210405"
string uSortiraniDatum(string datum)
{
    string dan = datum.substr(0, 2);
    string mesec = datum.substr(3, 2);
    string godina = datum.substr(6, 4);

    return godina + mesec + dan;
}

// Funkcija vraća datum iz oblika yyyymmdd
// u originalni oblik dd-mm-gggg.
//
// Na primer:
// "20210405" -> "05-04-2021"
string izSortiranogDatuma(string datum)
{
    string godina = datum.substr(0, 4);
    string mesec = datum.substr(4, 2);
    string dan = datum.substr(6, 2);

    return dan + "-" + mesec + "-" + godina;
}

int main()
{
    int n;

    // Učitavamo broj računa.
    cin >> n;

    // Ključ mape je datum u obliku yyyymmdd.
    // Vrednost je ukupan dnevni pazar u centima.
    map<string, long long> dnevneZarade;

    for (int i = 0; i < n; i++)
    {
        string datum;
        string iznos;

        // Učitavamo datum i iznos jednog računa.
        cin >> datum >> iznos;

        // Pretvaramo datum u oblik pogodan za sortiranje.
        string sortiraniDatum = uSortiraniDatum(datum);

        // Pretvaramo iznos u cente.
        long long iznosCenti = uCente(iznos);

        // Dodajemo iznos ukupnom pazaru tog datuma.
        dnevneZarade[sortiraniDatum] += iznosCenti;
    }

    // Tražimo najveći dnevni pazar.
    long long maksimalnaZarada = 0;

    for (const auto &par : dnevneZarade)
    {
        if (par.second > maksimalnaZarada)
        {
            maksimalnaZarada = par.second;
        }
    }

    // Ispis maksimalnog dnevnog pazara.
    cout << maksimalnaZarada / 100
         << "."
         << setw(2) << setfill('0')
         << maksimalnaZarada % 100
         << endl;

    // Pošto je mapa sortirana po datumu,
    // svi datumi sa maksimalnom zaradom
    // biće ispisani hronološkim redom.
    for (const auto &par : dnevneZarade)
    {
        if (par.second == maksimalnaZarada)
        {
            cout << izSortiranogDatuma(par.first) << endl;
        }
    }

    return 0;
}

Objašnjenje koda

1. Učitavanje broja računa
Najpre učitavamo broj fiskalnih računa:

int n;
cin >> n;

Taj broj određuje koliko puta ćemo učitati datum i iznos.

2. Mapa za dnevne zarade
Za čuvanje podataka koristimo:

map<string, long long> dnevneZarade;

Ključ je datum, a vrednost je ukupna zarada tog datuma.

Na primer:

dnevneZarade["20210703"] = 44050;

znači da je 3. jula 2021. ostvaren dnevni pazar od 44050 centi, odnosno 440.50.

3. Pretvaranje datuma
Funkcija uSortiraniDatum() izdvaja dan, mesec i godinu pomoću funkcije substr().

Za datum:

03-07-2021

dobijamo:

20210703

Time se postiže da prirodan redosled stringova odgovara hronološkom redosledu datuma.

4. Pretvaranje novca u cente
Funkcija uCente() razdvaja cele dinare i cente.

Na primer:

"285.50"

postaje:

28550

Sve dnevne zarade se zato mogu sabirati tačno kao celi brojevi.

5. Sabiranje zarade istog datuma
Najvažnija naredba za formiranje dnevnog pazara je:

dnevneZarade[sortiraniDatum] += iznosCenti;

Ako datum još ne postoji u mapi, C++ će napraviti novi element sa početnom vrednošću 0, a zatim dodati iznos.

Ako datum već postoji, novi iznos će se samo dodati postojećem dnevnom pazaru.

Na primer, za:

03-07-2021 340.00
03-07-2021 100.50

mapa će na kraju sadržati:

20210703 -> 44050

6. Pronalaženje najvećeg dnevnog pazara
Kada su svi računi obrađeni, prolazimo kroz mapu:

for (const auto &par : dnevneZarade)
{
    if (par.second > maksimalnaZarada)
    {
        maksimalnaZarada = par.second;
    }
}

U paru par nalazi se:

par.first   // datum
par.second  // dnevna zarada

Kada pronađemo veću vrednost, čuvamo je u promenljivoj maksimalnaZarada.

7. Ispis maksimalnog iznosa
Pošto je novac sačuvan u centima, cele dinare dobijamo deljenjem sa 100, a cente ostatkom pri deljenju:

maksimalnaZarada / 100
maksimalnaZarada % 100

Za pravilno ispisivanje dve cifre za cente koristi se:

setw(2) << setfill('0')

Tako će se, na primer, 5 dinara i 7 centi ispisati kao:

5.07

8. Ispis svih datuma sa maksimalnom zaradom
Ponovo prolazimo kroz mapu i proveravamo:

if (par.second == maksimalnaZarada)

Ako je uslov ispunjen, ispisujemo odgovarajući datum.

Ovde je veoma važna osobina mape: njeni ključevi su sortirani. Pošto smo datum zapisali kao yyyymmdd, redosled ključeva je upravo hronološki redosled datuma.

Praćenje algoritma na primeru

Posmatrajmo račune:

03-07-2021 340.00
05-04-2021 285.50
03-07-2021 100.50
04-07-2021 270.00
05-04-2021 155.00

Posle pretvaranja datuma i sabiranja računa dobijamo:

05-04-2021 -> 285.50 + 155.00 = 440.50
03-07-2021 -> 340.00 + 100.50 = 440.50
04-07-2021 -> 270.00

Zbog načina na koji su ključevi mape zapisani, oni će biti poređani:

20210405
20210703
20210704

Najveća zarada je:

440.50

Dva datuma imaju tu zaradu. Mapa ih daje redom:

05-04-2021
03-07-2021

To je upravo traženi hronološki redosled.

Zašto je ovo rešenje bolje od sortiranja svih računa?

U izvornom rešenju prvo se svi računi sortiraju po datumu, zatim se formiraju zbirne dnevne zarade, a nakon toga se ponovo sortiraju po zaradi. Takav pristup zahteva više prolazaka i više programskog koda.

Još važnije, sortiranje samo po zaradi ne obezbeđuje automatski hronološki redosled datuma kada su zarade jednake. Zbog toga je potrebno dodatno voditi računa o redosledu.

Kod mape se svaki datum odmah objedinjuje, a mapa istovremeno održava datume sortirane. Zato nema potrebe za dodatnim sortiranjem datuma.

Česte greške

1. Posmatranje samo jednog računa
Zadatak traži ukupan dnevni pazar, a ne najveći pojedinačni račun. Zato sve račune istog datuma moramo sabrati.

2. Pogrešno sortiranje datuma
Ako datum čuvamo kao dd-mm-gggg, obično nije dovoljno jednostavno porediti stringove.

Zbog toga ga pretvaramo u:

yyyymmdd

3. Korišćenje double za novac
Realni brojevi nisu idealni za potpuno precizno sabiranje novčanih vrednosti. Pošto je iznos dat sa dve decimale, možemo sve iznose pretvoriti u cente i koristiti long long.

4. Ispis samo jednog datuma
Ako više dana ima isti maksimalni pazar, potrebno je ispisati sve takve datume.

5. Nevodjenje računa o hronološkom redosledu
Datume sa istom maksimalnom zaradom moramo ispisati od najstarijeg do najnovijeg.

U ovom rešenju to je rešeno korišćenjem mape sa ključevima u obliku yyyymmdd.

Vremenska i memorijska složenost

Neka je n broj fiskalnih računa, a d broj različitih datuma.

Svaki račun se obrađuje jednom, a umetanje ili pronalaženje elementa u map ima složenost O(log d).

Zato je ukupna vremenska složenost:

O(n log d)

Pošto u najgorem slučaju svaki račun može pripadati drugom datumu, možemo pisati i:

O(n log n)

Memorijska složenost je:

O(d)

jer čuvamo po jedan element za svaki različit datum.

Sažetak rešenja

Suština zadatka je u tome da račune sa istim datumom treba objediniti. Za svaki datum sabiramo sve njegove račune i dobijamo dnevni pazar.

map je veoma pogodna za ovaj zadatak zato što istovremeno omogućava povezivanje datuma sa dnevnom zaradom i održava datume sortiranim.

Datum zapisujemo u obliku yyyymmdd, a novac čuvamo u centima kao long long.

Na kraju:

1. pronalazimo najveći dnevni pazar,
2. zatim prolazimo kroz mapu i ispisujemo sve datume sa tim pazarom.

Ključna ideja može se zapisati ovako:

dnevneZarade[datum] += iznos;

Nakon toga samo tražimo najveću vrednost u mapi i ispisujemo sve ključeve koji imaju tu vrednost.

Povratak
|< Kvalifikacije za okružna takmičenja