Zadatak Slovarica rešenje

9. SLOVARICA REŠENJE

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

U ovom zadatku, cilj je da se iz kolekcije dostupnih slova sastavi što više primeraka određene reči. Problem se fokusira na efikasno brojanje pojavljivanja slova i primenu algoritama za pronalaženje minimalnog broja ponavljanja reči, koristeći jednostavne operacije poput deljenja. Ovakvi algoritmi su korisni u svakodnevnim problemima optimizacije, kao što su kreiranje reči ili resursa od ograničenih zaliha, te predstavljaju osnovu za složenije izazove u oblasti algoritama.

Rešenje

#include <iostream>

using namespace std;

int main()
{

int minkr;
string s,r;
int kol[26]= {0};
int rec[26]= {0};
cin>>s>>r;

//maksimalan broj pojavljivanja
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;
}

Program koristi dva niza (od po 26 elemenata) za brojanje pojavljivanja svakog slova u kolekciji i reči. Prvo se prolazi kroz oba stringa i broje se slova. Zatim se za svako slovo iz reči izračunava koliko puta ono može biti korišćeno iz kolekcije. Na kraju, minimalan broj pojavljivanja bilo kog slova predstavlja broj mogućih ponavljanja cele reči. Ova metoda efikasno koristi deljenje i linearno prolazi kroz podatke, što je dovoljno brzo za zadati opseg (do 50.000 karaktera).

Rešenje 2

#include <iostream>
#include <climits> // za INT_MAX

using namespace std;

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

// Učitavanje niske
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; // Ako nedostaje slovo iz reči
break;
}
minkr = min(minkr, kol[i] / rec[i]);
}
}

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

return 0;
}

Struktura koda

Uključivanje biblioteka:

#include <iostream>
#include <climits>

Ove biblioteke omogućavaju korišćenje ulazno-izlaznih funkcija i definiciju maksimale celobrojne vrednosti (INT_MAX), što je korisno za inicijalizaciju minimalnog broja ponavljanja.

2. Deklaracija varijabli:

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

Varijable s i r predstavljaju kolekciju slova i reč, dok nizovi kol i rec čuvaju broj pojavljivanja svakog slova (od 'a' do 'z'). minkr služi za praćenje minimalnog broja reči koje se mogu sastaviti.
3. Učitavanje ulaza:

cin >> s >> r;

Ovaj deo koda učitava korisnički unos za kolekciju i reč.
4. Brojanje slova u kolekciji i reči:

for (char c1 : s) {
kol[c1 - 'a']++;
}
for (char c2 : r) {
rec[c2 - 'a']++;
}

Petlje prolaze kroz svaki karakter u kolekciji i reči, povećavajući broj pojavljivanja u odgovarajućem nizu.
5. Pronalazak minimalnog broja reči:

for (int i = 0; i < 26; i++) {
if (rec[i] > 0) {
if (kol[i] == 0) {
minkr = 0; // Ako nedostaje slovo iz reči
break;
}
minkr = min(minkr, kol[i] / rec[i]);
}
}

Ova petlja određuje koliko puta se svako slovo iz reči može koristiti na osnovu njegovog broja u kolekciji, ažurirajući minkr na osnovu najograničenijeg slova.
6. Ispis rezultata:

cout << minkr << endl;

Na kraju, program ispisuje minimalan broj reči koje mogu biti sastavljene na osnovu dostupnih slova.

Dodatni primeri

Primer 1
- Ulaz: abcdeabcdeabcde
  Reč: abc
- Izlaz: 3
- Objašnjenje: U kolekciji imamo 15 slova abcde, a reč abc se može sastaviti 3 puta (5 slova a, 5 slova b, i 5 slova c).
Primer 2
- Ulaz: xyzxyzxyz
  Reč: xyzz
- Izlaz: 2
- Objašnjenje: U kolekciji imamo 9 slova, od kojih možemo koristiti 2 slova x, 2 slova y, i 3 slova z, što omogućava sastavljanje reči xyzz dva puta.
Primer 3
- Ulaz: abcdefgh
  Reč: ijk
- Izlaz: 0
- Objašnjenje: S obzirom na to da reč sadrži slova i, j, i k, koja se ne nalaze u kolekciji, reč se ne može sastaviti nijednom.
Primer 4
- Ulaz: aabbcc
  Reč: abcabc
- Izlaz: 1
- Objašnjenje: U kolekciji imamo po 2 slova a, b, i c, što omogućava sastavljanje reči abcabc samo jednom.

Završna napomena

Ovo rešenje ima široku primenu u realnim situacijama. Na primer, u pretraživačima reči, ovakvi algoritmi mogu pomoći u optimizaciji pretrage reči koje se mogu formirati iz datih slova, što je korisno za igrače scrabble-a ili sličnih igara. Takođe, može se koristiti u generisanju kombinacija reči u aplikacijama za učenje jezika, gde je važno odabrati odgovarajuće reči iz ograničenog skupa slova. Razumevanje ovih koncepata pomaže u razvoju efikasnijih algoritama za obradu teksta i optimizaciju resursa.

Pogledajmo sad poboljšano i optimizovano rešenje:

Rešenje 3

Rešenje 3 donosi nekoliko poboljšanja u odnosu na rešenje 2. Ključna razlika je u upotrebi biblioteke <climits> i konstante INT_MAX za inicijalizaciju promenljive minkr. Ovo omogućava da se minimalna vrednost ispravno ažurira čak i u slučajevima kada se prvi put obrađuju slova, čineći kod robusnijim. Takođe, struktura koda je optimizovana kako bi bila jasnija, s fokusom na tačno postavljanje minimalnog broja ponavljanja, što poboljšava čitljivost i održivost rešenja.
Objašnjenje:

unordered_map se koristi za efikasno brojanje slova u kolekciji i reči.
Nakon što izbrojimo pojavljivanja slova, prolazimo kroz slova reči i računamo koliko puta možemo koristiti svako slovo iz kolekcije. Koristimo deljenje broja slova u kolekciji sa brojem slova u reči.
Rezultat je minimalan broj reči koje možemo sastaviti, jer je najograničenije slovo ključni faktor.

Poređenje složenosti rešenja:
Prvo rešenje ima vremensku složenost O(n+m)O(n + m)O(n+m), gde su nnn i mmm dužine kolekcije i reči. Iako ovo rešenje efikasno prolazi kroz oba niza, drugo rešenje dodatno poboljšava stabilnost i robustnost koristeći konstantu INT_MAX, čime se osigurava da se minimalna vrednost pravilno postavi. Obe verzije koriste linearnu složenost, ali treće rešenje dodatno optimizuje jasnost i održivost koda, bez promene same složenosti O(n+m)O(n + m)O(n+m).

Prethodno
|< Kvalifikacije za okružna takmičenja

Sledeće
Opštinska takmičenja >|