ZADATAK: ROTATOR SLOVA(DRŽAVO TAKMIČENJE IZ INFORMATIKE, 7. RAZRED - REŠENJE
Tekst zadatka:
Kada se pritisne taster na tastaturi, prvo slovo svake reči u tekstu se premesti na poslednje mesto te reči.
Koliko je puta potrebno pritisnuti taster da bi se rečenica vratila u početno stanje?
Ulaz
Sa standardnog ulaza se učitava jedna linija teksta koja je sastavljena od malih slova engleske abecede i
razmaka i ima najviše 106 karaktera. Svi primeri su takvi da se rečenica vraća u prvobitno stanje
nakon najviše 1018 pritisaka tastera.
Izlaz
Na standardni izlaz ispisati najmanji broj pritisaka tastera (veći od 0)
potrebnih da se rečenica vrati u prvobitno stanje.
Primer 1
Ulaz
mala sirena zivi na dnu mora
Izlaz
12
Objašnjenje
Pritiscima tastera dobijaju se naredne rečenice
mala sirena zivi na dnu mora
alam irenas iviz an nud oram
lama renasi vizi na udn ramo
amal enasir iziv an dnu amor
mala nasire zivi na nud mora
alam asiren iviz an udn oram
lama sirena vizi na dnu ramo
amal irenas iziv an nud amor
mala renasi zivi na udn mora
alam enasir iviz an dnu oram
lama nasire vizi na nud ramo
amal asiren iziv an udn amor
mala sirena zivi na dnu mora
Primer 2
Ulaz
sestaci sedmaci i osmaci vole informatiku
Izlaz
924
Primer 3
Ulaz
dada tata i mama
Izlaz
2
Napomena: U 50% test-primera reči nisu periodične. U 60% test-primera sve reči su kraće od 100 karaktera.
*/
/* Funkcija koja određuje, da li poslata reč može da se podeli na manje podstringove tačno d puta
* parametri:
* string rec-reč koja se ispituje
* int d-dužina grupe karaktera koji treba da se periodično ponavljaju u ispitivanoj reči
Kada se pritisne taster na tastaturi, prvo slovo svake reči u tekstu se premesti na poslednje mesto te reči.
Koliko je puta potrebno pritisnuti taster da bi se rečenica vratila u početno stanje?
Ulaz
Sa standardnog ulaza se učitava jedna linija teksta koja je sastavljena od malih slova engleske abecede i
razmaka i ima najviše 106 karaktera. Svi primeri su takvi da se rečenica vraća u prvobitno stanje
nakon najviše 1018 pritisaka tastera.
Izlaz
Na standardni izlaz ispisati najmanji broj pritisaka tastera (veći od 0)
potrebnih da se rečenica vrati u prvobitno stanje.
Primer 1
Ulaz
mala sirena zivi na dnu mora
Izlaz
12
Objašnjenje
Pritiscima tastera dobijaju se naredne rečenice
mala sirena zivi na dnu mora
alam irenas iviz an nud oram
lama renasi vizi na udn ramo
amal enasir iziv an dnu amor
mala nasire zivi na nud mora
alam asiren iviz an udn oram
lama sirena vizi na dnu ramo
amal irenas iziv an nud amor
mala renasi zivi na udn mora
alam enasir iviz an dnu oram
lama nasire vizi na nud ramo
amal asiren iziv an udn amor
mala sirena zivi na dnu mora
Primer 2
Ulaz
sestaci sedmaci i osmaci vole informatiku
Izlaz
924
Primer 3
Ulaz
dada tata i mama
Izlaz
2
Napomena: U 50% test-primera reči nisu periodične. U 60% test-primera sve reči su kraće od 100 karaktera.
*/
/* Funkcija koja određuje, da li poslata reč može da se podeli na manje podstringove tačno d puta
* parametri:
* string rec-reč koja se ispituje
* int d-dužina grupe karaktera koji treba da se periodično ponavljaju u ispitivanoj reči
Pošto svakoj reči, pri premeštanju slova sa početka na kraj reči treba uraditi premeštanje onoliko puta koliko ta reč ima slova, treba napraviti prvo niz brojeva čije vrednosti predstavljaju dužine tih reči. Da bi našli onaj broj ponavljanja, koji će sve reči dovesti u prvobitno stanje, potrebno je naći najmanji zajednički sadržalac tih brojeva. Ovo bi zadovoljilo 50% test primera, jer u slučaju da unutar reči možemo izdvojiti karaktere koji se periodično ponavljaju ceo broj puta npr. k puta, onda bi se ta reč dovela u prvobitno stanje posle d/k puta, gde je d dužina reči. Pogledajmo na sledećem primeru:
Reč damdam ima d=6 karaktera, ali se karakteri dam onavljaju tačno k=2 puta. Posle d/k=6/2=3 premeštanja bilo bi:
1. amdamd
2. mdamda
3. damdam
To znači da treba pronaći dodatno da li se može iz date reči izdvojiti niz karaktera, koji se međusobno ponavljaju.
Sledeće rešenje nije najbolje moguće ali će zadovoljiti 90% test primera:
Prvo se unutar main metode učita red teksta u promenljivu text. Zatim se uvede stream podataka T klase sstream iz istoimenog zaglavlja i tekst prebaci u taj tok(stream) podataka.
Kroz while petlju, i korišćenjem getline() funkcije sa 3 parametra se iz toka čita niz karaktera do blanko karaktera, što znači u svakom ciklusu po jedna reč se izdvaja i smešta u promenljivu rec.
Zatim se unutar iste petlje formira niz dužina reči.
Za određivanje dužine reči ili dela reči, ako se periodično ponavlja koristi se funkcija duzinaPeriodicneReci().
Za kreiran niz duzineReci određuje se najmanji zajednički sadržalac pomoću funkcije NZS. Određivanje NZS-a i NZD-a(najvećeg zajedničkog delioca pomoću Euklidovog algoritma je opisana na webstrani: Euklidov algoritam
Za određivanje NZS sa više brojeva, računa se prvo NZS za prva dva broja, zatim se uzima sledeći iz niza i računa nzs za prethodno izračunat NZS i taj novi broj itd.
Najmanji zajednički sadržalac brojeva a i b se izračunava kao količnik proizvoda brojeva a i b i NZD(a,b), gde je NZD najveći zajednički delilac brojeva a i b. Za to izračunavanje je u ovom kodu napravljena posebna funkcija.
Kompletan kod je prikazan u nastavku:
Reč damdam ima d=6 karaktera, ali se karakteri dam onavljaju tačno k=2 puta. Posle d/k=6/2=3 premeštanja bilo bi:
1. amdamd
2. mdamda
3. damdam
To znači da treba pronaći dodatno da li se može iz date reči izdvojiti niz karaktera, koji se međusobno ponavljaju.
Sledeće rešenje nije najbolje moguće ali će zadovoljiti 90% test primera:
Prvo se unutar main metode učita red teksta u promenljivu text. Zatim se uvede stream podataka T klase sstream iz istoimenog zaglavlja i tekst prebaci u taj tok(stream) podataka.
Kroz while petlju, i korišćenjem getline() funkcije sa 3 parametra se iz toka čita niz karaktera do blanko karaktera, što znači u svakom ciklusu po jedna reč se izdvaja i smešta u promenljivu rec.
Zatim se unutar iste petlje formira niz dužina reči.
Za određivanje dužine reči ili dela reči, ako se periodično ponavlja koristi se funkcija duzinaPeriodicneReci().
Za kreiran niz duzineReci određuje se najmanji zajednički sadržalac pomoću funkcije NZS. Određivanje NZS-a i NZD-a(najvećeg zajedničkog delioca pomoću Euklidovog algoritma je opisana na webstrani: Euklidov algoritam
Za određivanje NZS sa više brojeva, računa se prvo NZS za prva dva broja, zatim se uzima sledeći iz niza i računa nzs za prethodno izračunat NZS i taj novi broj itd.
Najmanji zajednički sadržalac brojeva a i b se izračunava kao količnik proizvoda brojeva a i b i NZD(a,b), gde je NZD najveći zajednički delilac brojeva a i b. Za to izračunavanje je u ovom kodu napravljena posebna funkcija.
Kompletan kod je prikazan u nastavku:
#include <iostream>
#include<string>
#include <sstream>
#include<vector>
using namespace std;
/*
*/
bool deliRec(int d,string rec)
{
bool rez=true;
int duz=rec.length();
int poz=0;
string pDeoT=rec;
int i=0;
while(poz < duz)
{
string deoT=rec.substr(poz,d);
// cout<<deoT<<endl;
if(i != 0 && deoT != pDeoT)
{
rez=false;
break;
}
poz += d;
pDeoT = deoT;
i++;
}
return rez;
}
/*Funkcija koja određuje dužinu grupe karaktera koji se periodično ponavljaju ceo broj puta u ispitivanoj reči
* parametar:
* string rec- reč koja se ispituje
*/
int duzinaPeriodicneReci(string rec)
{
int duz=rec.length();
// cout<<"Duzina reci koja se obradjuje je: "<<duz<<endl;
int del=1;
int rduz=del;
while( !deliRec(del,rec)) //Prvi put kad naidje da rec moze da se podeli na slogove date duzine
{
/*trazi sledeci delilac*/
do
{
del++;
}
while(duz%del != 0);
/*Ako je delilac pamti ga kao moguci za podelu reci*/
if(duz%del == 0)
{
rduz = del;
}
if(del > duz/2)
{
rduz=duz;
break;
}
}
return rduz;
}
/*Funkcija za određivanje najvećeg zajedničkog delioca za brojeve x i y upotrebom Euklidovog algoritma*/
int NZD(int x, int y)
{
int a,b,nzd,temp;
a = (x>y)?x:y; //Veći izmeću x i y
b = (y>x)?x:y; //Manji izmeću x i y
while(b != 0)
{
temp = a;
a = b;
b = temp%b;
}
nzd = a;
return nzd;
}
/*Funkcija koja određuje najmanji zajednički sadržalac za brojeve u nizu "brojevi"*/
int NZS(vector<int> brojevi)
{
int nzd = 1;
int nzs = 1;
int preth;
for(size_t i = 0; i < brojevi.size(); i++)
{
if(i == 0)
{
nzs = brojevi[i];
preth=nzs;
}
else
{
nzd = brojevi[i];
// cout<<"nzd za "<<preth<<" i "<<nzd<<" je: ";
nzs=nzd*preth;
nzd=NZD(preth,nzd);
// cout<<nzd<<endl;
// cout<<" Dok je nzs=";
nzs=nzs/nzd;
preth=nzs;
// cout<<nzs<<endl;
}
}
return nzs;
}
int main()
{
string text;
string termin=" ";
string rec="";
getline(cin,text);
// cout<<text<<endl;
stringstream T=stringstream(text);
int n=0;
int nzs=-1;
vector<int>duzineReci;
while(getline(T,rec,' '))
{
// cout<<rec<<endl;
// int duzina=rec.length();
int duzina=duzinaPeriodicneReci(rec);
duzineReci.push_back(duzina);
n++;
}
// cout << "tekst ima "<<n<<" reci"<<endl;
nzs=NZS(duzineReci);
cout<<nzs<<endl;
return 0;
}
#include<string>
#include <sstream>
#include<vector>
using namespace std;
/*
*/
bool deliRec(int d,string rec)
{
bool rez=true;
int duz=rec.length();
int poz=0;
string pDeoT=rec;
int i=0;
while(poz < duz)
{
string deoT=rec.substr(poz,d);
// cout<<deoT<<endl;
if(i != 0 && deoT != pDeoT)
{
rez=false;
break;
}
poz += d;
pDeoT = deoT;
i++;
}
return rez;
}
/*Funkcija koja određuje dužinu grupe karaktera koji se periodično ponavljaju ceo broj puta u ispitivanoj reči
* parametar:
* string rec- reč koja se ispituje
*/
int duzinaPeriodicneReci(string rec)
{
int duz=rec.length();
// cout<<"Duzina reci koja se obradjuje je: "<<duz<<endl;
int del=1;
int rduz=del;
while( !deliRec(del,rec)) //Prvi put kad naidje da rec moze da se podeli na slogove date duzine
{
/*trazi sledeci delilac*/
do
{
del++;
}
while(duz%del != 0);
/*Ako je delilac pamti ga kao moguci za podelu reci*/
if(duz%del == 0)
{
rduz = del;
}
if(del > duz/2)
{
rduz=duz;
break;
}
}
return rduz;
}
/*Funkcija za određivanje najvećeg zajedničkog delioca za brojeve x i y upotrebom Euklidovog algoritma*/
int NZD(int x, int y)
{
int a,b,nzd,temp;
a = (x>y)?x:y; //Veći izmeću x i y
b = (y>x)?x:y; //Manji izmeću x i y
while(b != 0)
{
temp = a;
a = b;
b = temp%b;
}
nzd = a;
return nzd;
}
/*Funkcija koja određuje najmanji zajednički sadržalac za brojeve u nizu "brojevi"*/
int NZS(vector<int> brojevi)
{
int nzd = 1;
int nzs = 1;
int preth;
for(size_t i = 0; i < brojevi.size(); i++)
{
if(i == 0)
{
nzs = brojevi[i];
preth=nzs;
}
else
{
nzd = brojevi[i];
// cout<<"nzd za "<<preth<<" i "<<nzd<<" je: ";
nzs=nzd*preth;
nzd=NZD(preth,nzd);
// cout<<nzd<<endl;
// cout<<" Dok je nzs=";
nzs=nzs/nzd;
preth=nzs;
// cout<<nzs<<endl;
}
}
return nzs;
}
int main()
{
string text;
string termin=" ";
string rec="";
getline(cin,text);
// cout<<text<<endl;
stringstream T=stringstream(text);
int n=0;
int nzs=-1;
vector<int>duzineReci;
while(getline(T,rec,' '))
{
// cout<<rec<<endl;
// int duzina=rec.length();
int duzina=duzinaPeriodicneReci(rec);
duzineReci.push_back(duzina);
n++;
}
// cout << "tekst ima "<<n<<" reci"<<endl;
nzs=NZS(duzineReci);
cout<<nzs<<endl;
return 0;
}