---

Tekst zadatka

Ana uči da sastavlja reči od slova. Danas želi da od slova koja ima na raspolaganju sastavi što više primeraka reči koju je smislila. Napisati program koji određuje koliko puta data reč može da se sastavi od slova date kolekcije.

Ulaz

U prvom redu standardnog ulaza nalazi se niska karaktera koja predstavlja kolekciju, a u drugom niska koja predstavlja reč. Obe niske se sastoje isključivo od malih slova engleske abecede i dužina im je do 50000 karaktera.

Izlaz

Na standardni izlaz ispisati jedan ceo broj, broj mogućih sastavljanja date reči.

Primer 1

Ulaz:
matematikaiprogramiranje
meta

Izlaz:
2

Primer 2

Ulaz:
nekavelikakolekcijaslova
kea

Izlaz:
3

Primer 3

Ulaz:
babanedanijevisesedapajenekogleda
deda

Izlaz:
1

---

Ideja rešenja

Da bi se reč sastavila jednom, za svako slovo reči mora postojati dovoljno primeraka tog slova u kolekciji. Zato najpre prebrojimo koliko puta se svako slovo pojavljuje u kolekciji, a koliko puta u reči.

Ako se slovo c u reči pojavljuje rec[c] puta, a u kolekciji kol[c] puta, onda to slovo „dozvoljava” najviše

kol[c] / rec[c] (celobrojno deljenje)

sastavljanja reči. Reč se može sastaviti onoliko puta koliko dozvoljava najograničenije slovo, pa je rezultat minimum tih količnika po svim slovima koja se pojavljuju u reči. Ako neko slovo reči uopšte ne postoji u kolekciji, količnik je 0, pa je i rezultat 0.

Slova reči koja se ne pojavljuju (rec[c] == 0) preskačemo, jer ne ograničavaju rezultat, a deljenje nulom ne sme da se desi.

Primer: za kolekciju matematikaiprogramiranje i reč meta imamo m: 3/1 = 3, e: 2/1 = 2, t: 2/1 = 2, a: 6/1 = 6. Najmanji količnik je 2, pa je odgovor 2.

---

Rešenje 1 u programskom jeziku C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int minkr;
    string s, r;
    int kol[26] = {0};
    int rec[26] = {0};

    cin >> s >> r;

    // Gornja granica: reč ne može da se sastavi više puta
    // nego što ukupan broj slova kolekcije dozvoljava.
    minkr = s.size() / r.size();

    for (char c1 : s)
    {
        int poz = c1 - 'a';
        kol[poz]++;
    }

    for (char c2 : r)
    {
        int poz1 = c2 - 'a';
        rec[poz1]++;
    }

    for (int i = 0; i < 26; i++)
    {
        if (rec[i] == 0)
        {
            continue;
        }

        if (rec[i] != 0 && kol[i] == 0)
        {
            minkr = 0;
            continue;
        }

        int t = kol[i] / rec[i];

        if (t < minkr)
        {
            minkr = t;
        }
    }

    cout << minkr << endl;

    return 0;
}

Objašnjenje rešenja 1

Program koristi dva niza od po 26 elemenata, po jedan brojač za svako slovo od 'a' do 'z'. Izraz c1 - 'a' pretvara slovo u indeks: 'a' daje 0, 'b' daje 1 i tako dalje. Zatim se za svako slovo reči računa količnik kol[i] / rec[i] i pamti najmanji.

Zanimljiva je početna vrednost minkr = s.size() / r.size(). Reč dužine m ne može da se sastavi više od n / m puta iz n slova, pa je to ispravna gornja granica i rešenje daje tačne rezultate.

Nedostaci rešenja 1 i šta treba popraviti

• Rešenje je tačno i dovoljno brzo, ali ima nekoliko stvari koje treba ispraviti radi stila i sigurnosti.
• Kada se nađe slovo koga nema u kolekciji, odgovor je sigurno 0, pa umesto continue treba koristiti break. Petlja tada nema razloga da nastavi.
• Uslov rec[i] != 0 u drugom if je suvišan, jer je slučaj rec[i] == 0 već preskočen.
• Ako bi reč bila prazna, s.size() / r.size() bi bilo deljenje nulom. Po uslovu zadatka to se ne dešava, ali u opštem slučaju treba proveriti.
• U originalnoj verziji nedostajalo je #include <string>. Neki kompajleri ga uključe kroz <iostream>, ali na to ne treba računati; ovde je dodat.

---

Rešenje 2 u programskom jeziku C++

#include <iostream>
#include <string>
#include <climits>    // za INT_MAX
#include <algorithm>  // za min

using namespace std;

int main()
{
    int minkr = INT_MAX;
    string s, r;
    int kol[26] = {0};
    int rec[26] = {0};

    // Učitavanje niski
    cin >> s >> r;

    // Brojanje slova u kolekciji
    for (char c1 : s)
    {
        kol[c1 - 'a']++;
    }

    // Brojanje slova u reči
    for (char c2 : r)
    {
        rec[c2 - 'a']++;
    }

    // Pronalazak minimalnog broja puta koliko se reč može sastaviti
    for (int i = 0; i < 26; i++)
    {
        if (rec[i] > 0)
        {
            if (kol[i] == 0)
            {
                minkr = 0;  // Nedostaje slovo iz reči
                break;
            }
            minkr = min(minkr, kol[i] / rec[i]);
        }
    }

    // Ispis rezultata
    cout << minkr << endl;

    return 0;
}

Ispravke u odnosu na staru verziju rešenja 2

• U staroj verziji je pisalo using namespacestd; (bez razmaka). Takav kod se ne kompajlira; ispravno je using namespace std;.
• Dodato je #include <algorithm> za funkciju min i #include <string> za tip string.

Objašnjenje važnih delova programa

• int minkr = INT_MAX; postavlja početni minimum na najveću moguću vrednost tipa int, pa će ga prvi izračunati količnik sigurno zameniti.
• string s, r; čuvaju kolekciju i reč, a nizovi kol i rec broj pojavljivanja svakog slova.
• cin >> s >> r; učitava obe niske. Pošto niske ne sadrže razmake, cin >> je dovoljno.
• kol[c1 - 'a']++ povećava brojač slova c1.
• U poslednjoj petlji se za svako slovo koje se pojavljuje u reči računa kol[i] / rec[i], a min čuva najmanju vrednost. Ako slova nema u kolekciji, odmah se postavlja 0 i petlja se prekida pomoću break.
• Pošto reč sadrži bar jedno slovo, bar jednom se uđe u if (rec[i] > 0), pa se INT_MAX nikad ne ispisuje.

---

Rešenje 3: brojanje pomoću unordered_map

Na staroj stranici rešenje 3 je bilo doslovna kopija rešenja 2, iako je tekst ispod njega opisivao rešenje sa unordered_map. Ovde je prikazano upravo to rešenje, da bi opis i kod bili usklađeni.

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
    string s, r;
    cin >> s >> r;

    // Ključ je slovo, a vrednost broj njegovih pojavljivanja.
    unordered_map<char, int> kol, rec;

    for (char c : s)
    {
        kol[c]++;
    }

    for (char c : r)
    {
        rec[c]++;
    }

    int minkr = INT_MAX;

    // Prolazimo samo kroz slova koja se pojavljuju u reči.
    for (const auto& par : rec)
    {
        char slovo = par.first;
        int potrebno = par.second;

        auto it = kol.find(slovo);
        int dostupno = (it == kol.end()) ? 0 : it->second;

        minkr = min(minkr, dostupno / potrebno);

        if (minkr == 0)
        {
            break;  // Bolji rezultat od 0 nije moguć.
        }
    }

    cout << minkr << endl;

    return 0;
}

Objašnjenje rešenja 3

• unordered_map<char, int> čuva par slovo–broj pojavljivanja, pa nema računanja indeksa c - 'a'.
• Petlja prolazi samo kroz slova koja postoje u reči, pa nije potrebna provera rec[i] > 0.
• kol.find(slovo) proverava da li slovo postoji u kolekciji. Za slovo koga nema, dostupan broj je 0, pa je i rezultat 0.
• Ovo rešenje radi i kada bi ulaz sadržao velika slova, cifre ili druge znakove, dok bi nizovi od 26 elemenata u tom slučaju dobili indeks van opsega.

Da li je rešenje 3 brže?

Nije. Za ovaj zadatak, gde ulaz sadrži samo 26 malih slova, niz od 26 elemenata (rešenja 1 i 2) je jednostavniji i nešto brži od unordered_map, jer pristup nizu ne zahteva računanje heša. Stara tvrdnja da je rešenje 3 „optimizovano” nije tačna; ono je opštije, a ne brže. Za takmičenja je rešenje 2 najbolji izbor.

---

Dodatni primeri

Primer 1

Ulaz:
abcdeabcdeabcde
abc

Izlaz:
3

Kolekcija ima 15 slova: niska abcde ponovljena je 3 puta, pa svako od slova a, b i c postoji po 3 puta. Svako od njih reč koristi jednom, pa je odgovor 3.

Primer 2

Ulaz:
xyzxyzxyz
xyzz

Izlaz:
1

Kolekcija ima po 3 slova x, y i z. Reč xyzz traži po jedno x i y i dva slova z. Količnici su x: 3/1 = 3, y: 3/1 = 3, z: 3/2 = 1, pa je odgovor 1. (Na staroj stranici je pogrešno pisalo da je izlaz 2; za drugo sastavljanje bila bi potrebna četiri slova z, a ima ih samo tri.)

Primer 3

Ulaz:
abcdefgh
ijk

Izlaz:
0

Slova i, j i k ne postoje u kolekciji, pa se reč ne može sastaviti nijednom.

Primer 4

Ulaz:
aabbcc
abcabc

Izlaz:
1

Kolekcija ima po 2 slova a, b i c, a reč abcabc svako od njih koristi dva puta, pa se može sastaviti tačno jednom.

---

Složenost rešenja

• Sva tri rešenja imaju vremensku složenost O(n + m), gde je n dužina kolekcije, a m dužina reči. Svaka niska se prolazi jednom, a završna petlja ima najviše 26 koraka.
• Dodatna memorija je O(1): dva niza od 26 brojeva ili dve mape sa najviše 26 ključeva.
• Za najveći ulaz od 50000 karaktera sva tri rešenja rade za nekoliko milisekundi, pa prolaze sve testove po vremenu.
• Rezultat ne može biti veći od 50000, pa je tip int dovoljan.

Zaključak

Zadatak pokazuje tehniku brojanja pojavljivanja (histogram slova) i pronalaženja najograničenijeg resursa pomoću minimuma količnika. Ista ideja se koristi u igrama sa slovima kao što je Scrabble, ali i u svakom problemu gde se od ograničenih zaliha pravi što više istih proizvoda. Posebno obratite pažnju na celobrojno deljenje i na slučaj kada neko slovo potpuno nedostaje.

---

---