Niz \(1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,\ldots,\) koji se sastoji od nula i jedinica, gradi se na sledeći način: prvi element je 1; drugi se dobija logičkom negacijom prvog \(NOT(1)=0\), treći i četvrti logičkom negacijom prethodna dva \(NOT(1)=0\), \(NOT(0)=1\), peti, šesti, sedmi i osmi logičkom negacijom prva četiri – dobija se \(0,1,1,0\) itd. Dakle, krenuvši od jednočlanog segmenta \(1\), svakom početnom segmentu koji je dužine \(2^k\) (\(k\) uzima vrednosti \(0, 1, 2, \ldots\)) dopisuje se segment iste dužine dobijen logičkom negacijom svih elemenata početnog segmenta. Za zadato \(n\) odrediti \(n\)-ti član niza (brojanje kreće od 1).
U prvoj liniji standardnog ulaza nalazi se prirodan broj \(n\) (\(1 \leq n \leq 10^9\)).
Na standarnom izlazu prikazati cifru (0 ili 1) na poziciji \(n\)
15
0
1234
0
12345678
1
Formulacija zadatka sugeriše rešenje u kome bi se počev od zadatog prvog elementa \(x_1 = 1\) redom formirali segmenti po zadatim pravilima \((x_2)\), \((x_3, x_4)\), \((x_5 \ldots x_8), (x_9 \ldots x_{16}), (x_{17} \ldots x_{32}),\ldots\). Dakle, elementi tekućeg segmenta se formiraju negacijom prethodno formiranih elemenata \(x_1 \ldots x_k\), koji su na rastojanju \(k\), gde je \(k\) stepen broja 2 (uvećava se duplo nakon svakog prepisanog segmenta).
Složenost ovog pristupa je \(O(n)\).
Ovo upisivanje se može realizovati pomoću ugnežđenih petlji gde unutrašnja petlja duplira sadržaj niza, a spoljašnja kontroliše koliko puta sadržaj treba duplirati (dodatno osiguravajući da se upisivanje prekine kada se popuni potrebnih \(n\) elemenata niza).
bool Morzeov(int n) {
// Morzeov niz
vector<bool> a(n+1);
a[1] = true;
int upisano = 1; // broj upisanih elemenata
int duzina = 1; // duzina segmenta koji se trenutno negira
while (upisano < n) {
// negiramo segment trenutne duzine
// prekidamo petlju ranije ako tokom toga dostignemo n upisanih elemenata
for (int i = 1; i <= duzina && upisano < n; i++) {
a[duzina + i] = !a[i];
upisano++;
}
// naredni segment koji treba negirati je duplo duzi
duzina *= 2;
}
// upisano je n elemenata niza, pa ocitavamo rezultat
return a[n];
}#include <iostream>
#include <vector>
using namespace std;
bool Morzeov(int n) {
// Morzeov niz
vector<bool> a(n+1);
a[1] = true;
int upisano = 1; // broj upisanih elemenata
int duzina = 1; // duzina segmenta koji se trenutno negira
while (upisano < n) {
// negiramo segment trenutne duzine
// prekidamo petlju ranije ako tokom toga dostignemo n upisanih elemenata
for (int i = 1; i <= duzina && upisano < n; i++) {
a[duzina + i] = !a[i];
upisano++;
}
// naredni segment koji treba negirati je duplo duzi
duzina *= 2;
}
// upisano je n elemenata niza, pa ocitavamo rezultat
return a[n];
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Niz se može popuniti i pomoću samo jedne petlje u kojoj se vrši prepisivanje elemenata dok se ne upiše njih \(n\) tako što se na mesto \(i\) prepisuje element sa pozicijje \(i-k\), uvećavajući stepen dvojke \(k\) kada se ceo prethodni podsegment prepiše.
bool Morzeov(int n) {
// Morzeov niz
vector<bool> a(n+1);
a[1] = true;
// rastojanje elemenata koji se negiraju
int k = 1;
// popunjavamo niz zakljucno sa pozicijom n
for (int i = 2; i <= n; i++) {
// negiramo odgovarajuci element
a[i] = !a[i - k];
// negirali smo ceo segment, pa prelazimo na sledeci
if (i == 2 * k)
k *= 2;
}
// upisano je n elemenata niza, pa ocitavamo rezultat
return a[n];
}#include <iostream>
#include <vector>
using namespace std;
bool Morzeov(int n) {
// Morzeov niz
vector<bool> a(n+1);
a[1] = true;
// rastojanje elemenata koji se negiraju
int k = 1;
// popunjavamo niz zakljucno sa pozicijom n
for (int i = 2; i <= n; i++) {
// negiramo odgovarajuci element
a[i] = !a[i - k];
// negirali smo ceo segment, pa prelazimo na sledeci
if (i == 2 * k)
k *= 2;
}
// upisano je n elemenata niza, pa ocitavamo rezultat
return a[n];
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Direktna rešenja zadatka podrazumevaju formiranje svih elemenata niza koji prethode \(n\)-tom članu. Da bi se izračunao 2001. član mora se izračunati svih 2000 prethodnih članova.
Uočimo sledeće, kako bismo problem rešili bez korišćenja niza i bez izračunavanja svih članova niza koji prethode \(n\)-tom: formiranje elemenata segmenta na osnovu prethodnog postupka, znači da se svaki put dužina niza udvaja, tj. predstavlja stepen broja 2.
Prilikom negiranja početnog segmenta dobijamo da je \(x_2 = \mathit{NOT}(x_1)\). U ovom slučaju važi da je \(x_n = \mathit{NOT}(x_{n-1})\).
Negiranjem narednog segmenta dobijamo da je \(x_3 = \mathit{NOT}(x_1)\) i \(x_4 = \mathit{NOT}(x_2)\). U ovom slučaju važi da je \(x_n = \mathit{NOT}(x_{n-2})\).
Nakon toga dobijamo da je \(x_5 = \mathit{NOT}(x_1)\), \(x_6 = \mathit{NOT}(x_2)\), \(x_7 = \mathit{NOT}(x_3)\) i \(x_8 = \mathit{NOT}(x_4)\). U ovom slučaju važi da je \(x_n = \mathit{NOT}(x_{n-4})\).
Dakle, za \(n>1\) važi rekurentna formula \(x_n = \mathit{NOT}(x_{n-m})\), gde je \(m\) - maksimalni stepen broja 2, koji je strogo manji od \(n\). Ova rekurentna formula omogućava veoma efikasno izračunavanje traženog člana niza. Na primer,
\(x_{15} = \mathit{NOT}(x_{15-8}) = \mathit{NOT}(x_7) = \mathit{NOT}(\mathit{NOT}(x_{7-4})) = x_{7-4} = x_3 = \mathit{NOT}(x_{3-2}) = \mathit{NOT}(x_1) = \mathit{NOT}(1) = 0\).
Traženi broj se dobija u nekoliko koraka i za veće vrednosti broja \(n\). Na primer, za \(n=2001\):
\(x_{2001}=\mathit{NOT}(x_{2001-1024})=\mathit{NOT}(x_{977}) = x_{977-512}= x_{465} = \mathit{NOT}(x_{465-256})= \mathit{NOT}(x_{209}) = x_{209-128}= x_{81} = \mathit{NOT}(x_{81-64})= \mathit{NOT}(x_{17}) = x_{17-16} =x_1 = 1.\)
Rekurentna formula nam ukazuje da rešenje možemo veoma jednostavno realizovati uz pomoću rekurzivne funkcije. U implementaciji se koristi pomoćna funkcija za određivanje traženog stepena dvojke (ovu funkciju je moguće implementirati i efikasnije, korišćenjem operacija nad bitovima, međutim i ova jednostavna implementacija je sasvim dovoljna).
Pošto se svaki element niza izračunava na osnovu nekog iz prethodne polovine niza, u svakom koraku se \(n\) bar polovi, tako da je složenost ovog pristupa \(O(\log{n})\).
// vraca najveci stepen od 2, koji je manji od n
int MaxStepen2(int n) {
int max = 1;
while (max * 2 < n)
max *= 2;
return max;
}
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
if (n == 1)
return true;
return !Morzeov(n - MaxStepen2(n));
}#include <iostream>
using namespace std;
// vraca najveci stepen od 2, koji je manji od n
int MaxStepen2(int n) {
int max = 1;
while (max * 2 < n)
max *= 2;
return max;
}
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
if (n == 1)
return true;
return !Morzeov(n - MaxStepen2(n));
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Rekurziju je moguće jednostavno eliminisati i do rešenja možemo doći i iterativno tako što ćemo polazeći od \(x=1\), pri svakom prelasku na indeks nastao umanjenjem za najveći stepen broja negirati tekuću vrednost \(x\).
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
bool x = true; // prvi clan niza
while (n > 1) {
n -= MaxStep2(n);
x = !x;
}
return x;
}#include <iostream>
using namespace std;
// vraca najveci stepen od 2, koji je strogo manji od n
int MaxStep2(int n) {
int max = 1;
while (max * 2 < n)
max *= 2;
return max;
}
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
bool x = true; // prvi clan niza
while (n > 1) {
n -= MaxStep2(n);
x = !x;
}
return x;
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Primetimo da se tokom prethodno opisanog postupka uklanja jedan po jedan bit broja, sve dok ne ostane samo jedan bit (tj. dok broj ne postane stepen dvojke). Nakon toga se taj bit pomera za jedno mesto nadesno, sve dok broj ne postane 1.
Na primer, niz
\[x_{44} = \mathit{NOT}(x_{12}) = x_4 = \mathit{NOT}(x_2) = x_1 = 1\]
se binarno može predstaviti pomoću
\[x_{101100} = \mathit{NOT}(x_{001100}) = x_{000100} = \mathit{NOT}(x_{000010}) = x_{000001} = 1.\]
Ova druga faza bi se mogla izbeći, a implementacija pojednostaviti ako bi brojanje pozicija bilo od 0, a ne od 1 (što lako možemo postići ako odmah nakon učitavanja umanjimo vrednost \(n\) za 1). Tada bi važilo da je \(x_1 = \mathit{NOT}(x_0)\), zatim \(x_2 = \mathit{NOT}(x_0)\), \(x_3 = \mathit{NOT}(x_1)\), zatim \(x_4 = \mathit{NOT}(x_0)\), \(x_5 = \mathit{NOT}(x_1)\), \(x_6 = \mathit{NOT}(x_2)\) i \(x_7 = \mathit{NOT}(x_3)\). Razlika je, dakle, u tome što se od svakog indeksa oduzima najveći stepen dvojke koji je veći ili jednak od datog broja (razlika je značajna baš kada je indeks koji trenutno razmatramo stepen dvojke). U toj varijanti bismo umesto \(x_{44}\) računali \(x_{43}\) i važilo bi
\[x_{43} = \mathit{NOT}(x_{11}) = x_3 = \mathit{NOT}(x_1) = x_0 = 1\]
tj. binarno
\[x_{101011} = \mathit{NOT}(x_{001011}) = x_{000011} = \mathit{NOT}(x_{000001}) = x_{000000} = 1.\]
Dakle, na ovaj način se u svakom koraku uklanja jedan bit broja, sve dok broj ne postane 0, negirajući svaki put rezultujući bit. Uvid koji nas dovodi do lepše implementacije je to da će se isti rezultat dobiti i kada se bitovi uklanjaju jedan po jedan, krenuvši od bitova najmanje, umesto od bitova najveće težine. Uklanjanje poslednjeg bita 1 u binarnom zapisu broja n se može uraditi veoma efikasno korišćenjem izraza n & (n - 1).
Možemo primetiti da se u ovom rešenju potvrđuje da je brojanje od 0 umesto od 1 prirodnije i da ima lepša matematička svojstva.
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
// prilagodjavamo brojanje tako da krene od 0 umesto od 1
n--;
int x = 1;
while (n) {
// uklanjamo poslednji bit iz binarnog zapisa broja
n = n & (n-1);
x = !x;
}
return x;
}#include <iostream>
using namespace std;
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
// prilagodjavamo brojanje tako da krene od 0 umesto od 1
n--;
int x = 1;
while (n) {
// uklanjamo poslednji bit iz binarnog zapisa broja
n = n & (n-1);
x = !x;
}
return x;
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Na kraju, možemo uvideti da je bitan samo broj jedinica u binarnom zapisu broja \(n-1\). Ako je taj broj paran, rezultat je 1, a ako je neparan, rezultat je 0. Postoje efikasni algoritmi da se taj broj izračuna, a neki računari imaju i ugrađenu hardversku instrukciju za to. Iako programski jezik C++ ne standardizuje pristup toj instrukciji, ako se koristi kompilator GCC, moguće je upotrebiti funkciju __builtin_popcount, a ako se koristi Microsoft Visual C++, moguće je upotrebiti funkciju __popcnt.
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
// prilagodjavamo brojanje tako da krene od 0 umesto od 1
n--;
// ispitujemo parnost ukupnog broja bitova jednakih 1 u binarnom
// zapisu broja n
return !(__builtin_popcount(n) & 1);
}#include <iostream>
using namespace std;
// vraca n-ti element Morzeovog niza ako se pozicije broje od 1
bool Morzeov(int n) {
// prilagodjavamo brojanje tako da krene od 0 umesto od 1
n--;
// ispitujemo parnost ukupnog broja bitova jednakih 1 u binarnom
// zapisu broja n
return !(__builtin_popcount(n) & 1);
}
int main() {
int n;
cin >> n;
cout << (Morzeov(n) ? "1" : "0") << endl;
return 0;
}Niz slova \(ABACABADABACABAEABACABADABACABAFABACA...\) se može formirati na sledeći način:
Tako posle prve primene koraka 2 dobijamo niz \(A\), posle druge niz \(ABA\), posle treće niz \(ABACABA\) itd.
Odrediti slovo koje se pojavljuje na \(n\)-tom mestu u nizu, brojeći mesta od \(1\). Redosled slova u engleskom alfabetu je ABCDEFGHIJKLMNOPQRSTUVWXYZ.
Jedan prirodan broj manji od \(67~108~864\).
Jedno veliko slovo engleskog alfabeta.
8
D
65
A
100
C
Rešenje grubom silom je da se u memoriji kreira ceo niz karaktera i da se zatim pročita karakter sa odgovarajuće pozicije. Ovo rešenje troši previše memorije, a i vremena dok se dugačak niz karaktera ne izgradi.
string s = "";
char slovo = 'A';
while (s.size() <= n - 1) {
s = s + slovo + s;
slovo++;
}
cout << s[n-1] << endl;#include <iostream>
#include <string>
using namespace std;
int main() {
unsigned n;
cin >> n;
string s = "";
char slovo = 'A';
while (s.size() <= n - 1) {
s = s + slovo + s;
slovo++;
}
cout << s[n-1] << endl;
}Zadatak se može rešiti bez kreiranja dugačke niske karaktera, ako pažljivo proučimo pravilnost po kojoj se slova pojavljuju. Prvo slovo A se nalazi na mestu 1, prvo slovo B na mestu 2, prvo slovo C na mestu 4, prvo slovo D na mestu 8 itd., pa se može naslutiti da se prva pojavljivanja slova nalaze na mestima koja su stepeni broja 2.
Zaista, ako dužinu niza karaktera pre umetanja novog slova abecede obeležimo sa \(d_k\), važi da je \(d_0 = 0\) (pre umetanja slova A ne nalazi se nijedan karakter) i da je \(d_{k+1} = 2d_k + 1\) (pre umetanja novog slova nalazi se niska koja je dobijena tako što je prethodno slovo spojeno sa dva pojavljivanja niske koja se pojavljivala pre tog prethodnog slova). Zato je \(d_k = 2^k - 1\) (važi da je \(2^0 - 1 = 0\) i da je \(2^{k+1} - 1 = 2\cdot (2^k - 1) + 1\)), dok je prva pozicija slova \(k\) (ako se slova broje od jedan) jednaka \(2^k\).
Dakle, ako je uneti broj \(n\) neki stepen dvojke \(n = 2^k\), onda je u pitanju mesto na kom se slovo prvi put pojavljuje i važi da je \(k = \log_2{n}\) (\(\log_2{n}\) označava broj \(k\) takav da je \(2^k = n\), npr. \(\log_2{32} = 5\), jer je \(2^5 = 32\)). Znajući \(k\) slovo lako možemo odrediti sabirajući \(k\) sa ASCII/UNICODE kodom slova A.
U suprotnom problem možemo svesti na problem manje dimenzije. Neka je \(2^k < n < 2^{k+1}\), tj. neka je \(k\) najveći stepen dvojke manji od \(n\). Karakter koji tražimo nalazi se, dakle, iza pozicije \(2^k\) u delu niza koji je dobijen kopiranjem dela niza ispred pozicije \(2^k\). Zato je \(n\)-ti karakter u celom nizu jednak \((n - 2^k)\)-tom karakteru u kopiranom delu, a pošto deo koji se kopira počinje na početku niza, jednak je \((n-2^k)\)-tom karakteru u celom nizu.
Ovim smo opisali rekurzivni postupak kojim efikasno možemo doći do rešenja.
\[f(n) = \begin{cases} \log_2{n}, \text{za } n = 2^k \\ f(n-2^k), \text{za } 2^k < n < 2^{k+1} \end{cases}.\]
Na primer, \(f(23) = f(23-16) = f(7) = f(7 - 4) = f(3) = f(3 - 2) = f(1) = 0\), pa se na mestu 23 nalazi slovo A. Slično, na primer, važi da je \(f(40) = f(40 - 32) = f(8) = 3\), pa se na mestu 40 nalazi slovo D.
Na osnovu prethodne definicije bi se mogla implementirati rekurzivna funkcija (za to bi bilo potrebno ispitati da li je dati broj stepen broja 2, naći logaritam takvog broja, i naći najveći stepen broja 2 od kog je dati broj veći ili jednak). Ipak, za tim nema potrebe. Analizirajući rad takve rekurzivne funkcije možemo unapred zaključiti šta će njen rezultat biti, bez potrebe za njenim izvršavanjem. Pretpostavimo da znamo binarni zapis broja \(n\) tj. da znamo da se broj \(n\) predstavlja kao zbir nekih stepenova dvojke \(2^{s_m} + 2^{s_{m-1}} + \ldots + 2^{s_0}\). Tokom rekurzije od broja će se oduzimati jedan po jedan stepen dvojke, sve dok ne ostane samo \(2^{s_0}\) i tada ćemo znati da je \(k = s_0\). Dakle važi da je rezultat jednak najmanjem stepenu dvojke koji učestvuje razlaganju broja na zbir stepenova dvojke tj. da je traženi broj \(k\) jednak poziciji najdešnje jedinice u binarnom zapisu broja (pretpostavljamo da se pozicije broje od 0, zdesna). Do traženog rezultata je moguće doći deljenjem broja sa \(2^s_0\), tj. uzastopnim deljenjem broja sa 2 sve dok poslednji sabirak ne postane 1, tj. sve dok je broj paran (to će se dogoditi tačno \(s_0\) puta).
int k = 0;
while (n % 2 == 0) {
n /= 2;
k++;
}
cout << (char)('A' + k) << endl;#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int k = 0;
while (n % 2 == 0) {
n /= 2;
k++;
}
cout << (char)('A' + k) << endl;
return 0;
}Sličan rezultat možemo dobiti i baratajući direktno sa internim zapisom broja u računaru, korišćenjem bitovskih operatora. Poziciju krajnje desne jedinice jednostavno možemo izračunati šiftovanjem (pomeranjem) binarnog zapisa broja udesno za jedno mesto sve dok poslednja cifra ne postane jednaka 1 (poslednju cifru možemo ispitati bitovskom konjunkcijom sa 1).
int k = 0;
while ((n & 1) == 0) {
n >>= 1;
k++;
}
cout << (char)('A' + k) << endl;#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int k = 0;
while ((n & 1) == 0) {
n >>= 1;
k++;
}
cout << (char)('A' + k) << endl;
return 0;
}Savremeni hardver često poseduje i instrukciju count trailing zeroes kojom se određuje broj nula iza poslednje jedinice u binarnom zapisu (što je baš pozicija poslednje jedinice). Iako programski jezici obično ne standardizuju pristup ovoj operaciji, neki kompilatori nude podršku za to (na primer, ako se koristi GCC, može se upotrebiti funkcija __builtin_ctz, a ako se koristi Microsoft Visual C++, može se upotrebiti funkcija _BitScanReverse).
cout << (char)('A' + __builtin_ctz(n)) << endl;#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
cout << (char)('A' + __builtin_ctz(n)) << endl;
return 0;
}Napiši program koji određuje koliko prirodnih brojeva iz intervala \([0, n]\) ne sadrže cifru 3 u svom dekadnom zapisu.
Prva linija standardnog ulaza sadrži prirodan broj \(n\) (\(n \leq 2 \cdot 10^9\)).
U prvoj liniji standardnog izlaza prikazati traženi rezultat.
15
14
U intervalu \([0, 15]\) postoji 16 brojeva, a brojevi \(3\) i \(13\) jedini sadrže cifru \(3\).
999
729
12345
8262
Zadatak možemo rešiti tako što za svaki broj od 0 do \(n\) proverimo da li sadrži cifru 3, i ako ne sadrži uvećamo brojač brojeva koji ne sadrže cifru 3 (taj brojač u početku inicijalizujemo na nulu). U tom rešenju primenjuje se algoritam određivanja broja elemenata serije koji zadovoljavaju dati uslov, tj. algoritam brojanja filtrirane serije. Proveru da li broj sadrži cifru 3 možemo realizovati u posebnoj funkciji.
bool sadrziCifru3(int n) {
do {
if (n % 10 == 3)
return true;
n /= 10;
} while (n > 0);
return false;
}
int brojeviBezCifre3(int n) {
int br = 0;
for (int i = 0; i <= n; i++)
if (!sadrziCifru3(i))
br++;
return br;
}#include <iostream>
using namespace std;
bool sadrziCifru3(int n) {
do {
if (n % 10 == 3)
return true;
n /= 10;
} while (n > 0);
return false;
}
int brojeviBezCifre3(int n) {
int br = 0;
for (int i = 0; i <= n; i++)
if (!sadrziCifru3(i))
br++;
return br;
}
int main() {
int n;
cin >> n;
cout << brojeviBezCifre3(n) << endl;
return 0;
}Zadatak možemo rešiti i na mnogo efikasniji način (ali je rešenje u tom slučaju dosta kompleksnije). Neka \(f(a, b)\) označava broj brojeva iz intervala \([a, b]\) koji u svom dekadnom zapisu ne sadrže cifru 3, a \(f_0(n)\) broj takvih brojeva iz intervala \([0, n]\). Razmotrimo primer u kome želimo da izračunamo vrednost \(f_0(4251)\). Sve brojeve iz intervala \([0, 4251]\) možemo podeliti u nekoliko grupa tj. podintervala. Važi da je
\[[0, 4251] = [0, 999] \cup [1000, 1999] \cup [2000, 2999] \cup [3000, 3999] \cup [4000, 4251].\]
Zato je
\[f_0(4251) = f(0, 999) + f(1000, 1999) + f(2000, 2999) + f(3000, 3999) + f(4000, 4251).\]
Važi da je \(f(0, 999) = f_0(999)\). Takođe, važi i da je \(f(1000, 1999)\) jednak broju \(f(0, 999)\) tj. \(f_0(999)\). Zaista, između intervala \([0, 999]\) i \([1000, 1999]\) može se uspostaviti bijekcija takva da slika u svom dekadnom zapisu sadrži cifru 3 ako i samo ako njen original u svom dekadnom zapisu sadrži cifru 3. Slično, važi i da je \(f(2000, 2999) = f_0(999)\), dok je \(f(3000, 3999) = 0\) jer svi brojevi u intervalu \([3000, 3999]\) sadrže cifru 3. Na kraju, važi i da je \(f(4000, 4251)\) jednako \(f(0, 251)\) tj. \(f_0(251)\). Zato je
\[f_0(4251) = 3\cdot f_0(999) + f_0(251).\]
Dakle, ako znamo brojeve \(f_0(999)\) i \(f_0(251)\) tada možemo izračunati i broj \(f_0(4251)\).
Ista tehnika se može primeniti i na izračunavanje brojeva \(f_0(999)\) i \(f_0(251)\).
Važi da je
\[[0, 999] = [0, 99] \cup [100, 199] \cup \ldots \cup [900, 999],\]
pa je
\[f_0(999) = f(0, 99) + f(100, 199) + \ldots + f(900, 999).\]
Važi da je \(f(0, 99) = f(100, 199) = f(200, 299) = f(400, 499) = \ldots = f(900, 999) = f_0(99)\), a da je \(f(300, 399) = 0\). Stoga je
\[f_0(999) = 8\cdot f_0(99) + f_0(99) = 9\cdot f_0(99).\]
Slično, važi da je
\[f_0(99) = 9 \cdot f_0(9),\]
dok je \(f_0(9) = 9\) (jer u intervalu \([0, 9]\) koji ima 10 elemenata, jedino element 3 sadrži cifru 3).
Važi i da je
\[[0, 251] = [0, 99] \cup [100, 199] \cup [200, 251],\]
pa je
\[f_0(251) = 2\cdot f_0(99) + f_0(51).\]
Pošto je
\[[0, 51] = [0, 9] \cup [10, 19] \cup [20, 29] \cup [30, 39] \cup [40, 49] \cup [50, 51],\]
važi da je
\[f_0(51) = 4 \cdot f_0(9) + f_0(1).\]
Važi i da je \(f_0(1) = 2\) jer su oba elementa intervala \([0, 1]\) takvi da ne sadrže cifru 3.
Dakle, \(f_0(4251)\) = \(3\cdot f_0(999) + f_0(251)\) = \(3\cdot(9 \cdot f_0(99)) + 2\cdot f_0(99) + f_0(51)\) = \(3\cdot (9 \cdot (9 \cdot f_0(9))) + 2 \cdot (9 \cdot f_0(9)) + 4 \cdot f_0(9) + f_0(1)\) = \(3\cdot 9 \cdot 9 \cdot 9 + 2 \cdot 9 \cdot 9 + 4 \cdot 9 + 2\) = \(2387\).
Funkciju \(f_0\) je moguće rekurzivno definisati. Ako se broj \(n\) razlaže na početnu cifru \(c\) i sufiks \(n'\) tada se \(f_0(n)\) može izračunati na sledeći način, u zavisnosti od cifre \(c\) (pretpostavljamo da broj \(9\ldots 9\) ima onoliko devetki koliko cifara ima broj \(n'\)).
Izlaz iz rekurzije može biti i samo slučaj \(f_0(0) = 1\) (\(0\) je jedini broj u intervalu \([0, 0]\) i on ne sadrži cifru 3).
Problem sa implementacijom ovakve rekurzivne funkcije je to što se cifre odvajaju sleva nadesno, što je komplikovanije nego zdesna nalevo, kada broj \(n\) lako razlažemo na \(n \,\mathrm{div}\,10\) i \(n \,\mathrm{mod}\,10\). Stoga pre ulaska u rekurziju možemo obrnuti cifre broja. Takođe, za dati broj \(n\) potrebno je odrediti odgovarajući broj koji se sastoji samo od devetki. To jednostavno možemo rešiti tako što konstruišemo broj koji se od broja \(n\) dobija zamenom svih cifara cifrom 9 i ako taj broj prosleđujemo kao drugi parametar rekurzije (taj broj u svakom pozivu sadrži samo devetke i to onoliko devetki koliko cifara ima broj \(n\)).
Primetimo da se od jednog rekurzivnog poziva za broj sa \(k\) cifara najčešće dobijaju dva rekurzivna poziva za brojeve sa \(k-1\) cifara, što ukazuje na to da je složenost eksponencijalna (za osnovu \(2\)), što je dopustivo, jer je broj cifara mali. Ipak, s obzirom na to da se isti rekurzivni pozivi preklapaju (pre svega oni oblika \(f_0(9\ldots 9)\)), implementacija se može ubrzati dinamičkim programiranjem ili tako što se primeti da je da je \(f_0(\underbrace{9\ldots 9}_{k}) = 9^k\), pa bi se ovi rekurzivni pozivi mogli specijalizovati.
int brojeviBezCifre3(int n, int d) {
if (n == 0)
return 1;
int c = n % 10;
if (c < 3)
return c * brojeviBezCifre3(d / 10, d / 10) + brojeviBezCifre3(n / 10, d / 10);
else if (c == 3)
return c * brojeviBezCifre3(d / 10, d / 10);
else
return (c - 1) * brojeviBezCifre3(d / 10, d / 10) + brojeviBezCifre3(n / 10, d / 10);
}
int brojeviBezCifre3(int n) {
int nObratno = 0;
int devetke = 0;
do {
nObratno = nObratno * 10 + n % 10;
devetke = devetke * 10 + 9;
n /= 10;
} while (n > 0);
return brojeviBezCifre3(nObratno, devetke);
}#include <iostream>
using namespace std;
int brojeviBezCifre3(int n, int d) {
if (n == 0)
return 1;
int c = n % 10;
if (c < 3)
return c * brojeviBezCifre3(d / 10, d / 10) + brojeviBezCifre3(n / 10, d / 10);
else if (c == 3)
return c * brojeviBezCifre3(d / 10, d / 10);
else
return (c - 1) * brojeviBezCifre3(d / 10, d / 10) + brojeviBezCifre3(n / 10, d / 10);
}
int brojeviBezCifre3(int n) {
int nObratno = 0;
int devetke = 0;
do {
nObratno = nObratno * 10 + n % 10;
devetke = devetke * 10 + 9;
n /= 10;
} while (n > 0);
return brojeviBezCifre3(nObratno, devetke);
}
int main() {
int n;
cin >> n;
cout << brojeviBezCifre3(n) << endl;
return 0;
}Umesto rekurzije koja radi odozgo naniže, rešenje možemo sintetizovati odozdo naviše.
Obrađivaćemo jednu po jednu cifru broja \(n\), zdesna nalevo i malo po malo ćemo proširivati obrađeni sufiks \(n'\) broja \(n\). Uvedimo promenljivu, npr. \(br\), koja tokom iteracije čuva vrednosti \(f_0(n')\) za sufikse \(n'\) broja \(n\) koje tokom iteracije obrađujemo, i promenljivu, npr. \(t\), koja čuva vrednosti brojeva \(f_0(9\ldots 9) = 9^k\), za brojeve \(9\ldots 9\) koji imaju \(k\) cifara 9, koliko ukupno cifara ima u trenunom sufiksu \(n'\).
Promenljive \(t\) i \(br\) inicijalizujemo na 1 (pretpostavljamo da je pre petlje obrađen prazan sufiks koji odgovara broju \(0\) i da je \(9^0 = 1\)). Zatim u petlji obrađujemo cifru po cifru broja \(n\), krenuvši od cifre jedinica. Promenljivu \(br\) ažuriramo na sledeći način, u zavisnosti od tekuće cifre \(c\).
Promenljivu \(t\) ažuriramo na vrednost \(9 \cdot t\).
Razmotrimo ponovo primer izračunavanja \(f_0(4251)\) i primenimo prethodno opisani algoritam na broj \(4251\).
Pretpostavimo da na početku promenljive \(t\) i \(br\) imaju vrednost 1.
Prvo obrađujemo poslednju (prvu zdesna) cifru broja \(n\), a to je cifra 1. Pošto je ona manja od \(3\), ažuriramo \(br\) na vrednost \(c \cdot t + br = 1 \cdot 1 + 1 = 2\), a vrednost \(t\) na vrednost \(9 \cdot t = 9\). Nakon ovoga, promenljiva \(br\) ima vrednost \(f_0(1)\), a promenljiva \(t\) ima vrednost \(f_0(9)\).
Naredna cifra je \(5\) i pošto je ona veća od 3, ažuriramo vrednost \(br\) na \((c-1)\cdot t + br = 4\cdot 9 + 2 = 38\), a vrednost \(t\) na vrednost \(9\cdot t = 81\). Nakon ovoga, promenljiva \(br\) ima vrednost \(f_0(51)\), a promenljiva \(t\) ima vrednost \(f_0(99)\).
Naredna cifra je \(2\) i pošto je ona manja od 3, ažuriramo vrednost \(br\) na \(c\cdot t + br = 2\cdot 81 + 38 = 200\), a vrednost \(t\) na vrednost \(9\cdot t = 9\cdot 81 = 729\). Nakon ovoga, promenljiva \(br\) ima vrednost \(f_0(251)\), a promenljiva \(t\) ima vrednost \(f_0(999)\).
Na kraju, početna cifra je \(4\) i pošto je ona veća od 4, ažuriramo vrednost \(br\) na \((c-1)\cdot t + br = 3\cdot 729 + 200 = 2387\). Vrednost \(t\) se ažurira na \(9\cdot 729 = 6561\), ali se ta vrednost dalje ne koristi. Nakon ovoga, promenljiva \(br\) ima vrednost \(f_0(4251)\), a promenljiva \(t\) ima vrednost \(f_0(9999)\).
int brojeviBezCifre3(int n) {
int t = 1, br = 1;
while (n > 0) {
int c = n % 10;
if (c < 3)
br = c*t + br;
else if (c == 3)
br = c*t;
else
br = (c-1)*t + br;
t = 9*t;
n /= 10;
}
return br;
}#include <iostream>
using namespace std;
int brojeviBezCifre3(int n) {
int t = 1, br = 1;
while (n > 0) {
int c = n % 10;
if (c < 3)
br = c*t + br;
else if (c == 3)
br = c*t;
else
br = (c-1)*t + br;
t = 9*t;
n /= 10;
}
return br;
}
int main() {
int n;
cin >> n;
cout << brojeviBezCifre3(n) << endl;
return 0;
}Napiši program koji za dati prirodan broj \(n\) određuje zbir svih brojeva koji se mogu dobiti izbacivanjem nekih cifara broja \(n\).
Sa standardnog ulaza se učitava broj koji može da ima najviše 1000 cifara.
Na standardni izlaz ispisati traženi zbir.
123
177
\(123 + 12 + 13 + 23 + 1 + 2 + 3 + 0 = 177\).
Do rešenja možemo doći induktivno-rekurzivnom konstrukcijom. Ako je broj jednak nuli, tada je traženi zbir jednak nuli. U suprotnom se taj broj može razložiti na svoju poslednju cifru i cifre koje joj prethode (npr. broj 1234 se može razložiti na broj 123 i cifru 4). Pretpostavimo da umemo da odredimo traženi zbir za broj kome je uklonjena poslednja cifra i razmotrimo kako se kombinacijom tog broja i poslednje cifre može dobiti traženi zbir. U tekućem primeru, pretpostavljamo, dakle, da umemo da odredimo traženi zbir za broj 123. Na svaki od sabiraka koji učestvuje u tom zbiru možemo dodati četvorku zdesna. Svaki od tih sabiraka se dobija tako što se originalni broj pomnoži sa 10 i doda se 4. Njihov se zbir zato može dobiti tako što se polazni zbir (177) pomnoži sa 10 i zatim uveća za onoliko četvorki koliko ima sabiraka (u tekućem primeru ih ima 8). Pošto su ovim pokrivene sve mogućnosti, ukupan zbir se dobija sabiranjem polaznog i ovako transformisanog zbira.
177 177*10 + 8*4 = 1802 177 + 1802 = 1979 123 1234 12 124 13 134 23 234 1 14 2 24 3 34 0 4
U opštem slučaju, dakle, dobijeni zbir prefiksa množimo sa 10 i uvećavamo proizvodom poslednje cifre i broja brojeva koji se dobijaju precrtavanjem cifara tog prefiksa. Taj broj nije teško izračunati jer je prilično očigledno da \(k\)-tocifren broj može da generiše \(2^k\) brojeva (svaka od \(k\) cifara može biti ili precrtana ili neprecrtana). Zato možemo ojačati induktivnu hipotezu i napraviti funkciju koja uz traženi zbir vraća još dodatno i broj cifara broja (ili još bolje, odgovarajući stepen dvojke).
Dakle, problem jednostavno možemo rešiti tako što definišemo rekurzivnu funkciju koja prima broj \(n\) a vraća traženi zbir za taj broj \(n\) i odgovarajući stepen dvojke. Više vrednosti funkcija može da vrati pomoću svojih izlaznih parametara.
Dodatni problem predstavlja veličina brojeva koji su dopušteni na ulazu, tako da je jasno da implementacija algoritma sa bibliotečkim tipovima podataka nije ispravna. Stoga implementacija koja koristi samo osnovne brojevne tipove podataka ne radi korektno za sve moguće ulaze (to se može rešiti korišćenjem velikih brojeva).
void Zbir(int n, int& zbir, int& b) {
if (n == 0) {
zbir = 0;
b = 1;
} else {
int zbirR, brojR;
Zbir(n / 10, zbirR, brojR);
zbir = zbirR + zbirR*10 + brojR * (n % 10);
b = brojR * 2;
}
}
int Zbir(int n) {
int zbir, b;
Zbir(n, zbir, b);
return zbir;
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
void Zbir(int n, int& zbir, int& b) {
if (n == 0) {
zbir = 0;
b = 1;
} else {
int zbirR, brojR;
Zbir(n / 10, zbirR, brojR);
zbir = zbirR + zbirR*10 + brojR * (n % 10);
b = brojR * 2;
}
}
int Zbir(int n) {
int zbir, b;
Zbir(n, zbir, b);
return zbir;
}
int main() {
int n; cin >> n;
cout << Zbir(n) << endl;
return 0;
}Ovakve rekurzije je veoma jednostavno osloboditi se i algoritam se lako može implementirati i iterativno. Razmotrimo kako se izvršava rekurzivni poziv za argument \(n = 123\).
Zbir(123) 177, 8 Zbir(12) 15, 4 Zbir(1) 1, 2 Zbir(0) 0, 1
Primećujemo, dakle, da se izračunavanja vrše u povratku kroz rekurziju i to tako što se vrednost prethodnog zbira i prethodnog stepena dvojke ažuriraju na osnovu opisanog postupka. Isto izračunavanje se može opisati i iterativnim postupkom u kom se promenljive inicijalizuju na 0 i 1, a zatim tokom iteracije ažuriraju korišćenjem jedne po jedne cifre polaznog broja, s leva nadesno. Prolazak kroz cifre broja u tom redosledu jednostavniji je ako se broj predstavi kao niska karaktera.
int Zbir(const string& broj) {
int zbir = 0, b = 1;
for (char c : broj) {
zbir += 10*zbir + b * (c - '0');
b *= 2;
}
return zbir;
}#include <iostream>
#include <string>
using namespace std;
int Zbir(const string& broj) {
int zbir = 0, b = 1;
for (char c : broj) {
zbir += 10*zbir + b * (c - '0');
b *= 2;
}
return zbir;
}
int main() {
string broj; cin >> broj;
cout << Zbir(broj) << endl;
}Da bismo dobili potpuno ispravno rešenje moramo koristiti rad sa velikim brojevima.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> saberi(const vector<int>& a, const vector<int>& b) {
vector<int> rez;
int p = 0;
for (size_t i = 0; i < a.size() || i < b.size(); i++) {
int c = (i < a.size() ? a[i] : 0) +
(i < b.size() ? b[i] : 0) + p;
rez.push_back(c % 10);
p = c / 10;
}
if (p > 0)
rez.push_back(p);
return rez;
}
vector<int> mnoziBrojem(const vector<int>& a, int b) {
vector<int> rez;
int p = 0;
for (size_t i = 0; i < a.size(); i++) {
int c = a[i] * b + p;
rez.push_back(c % 10);
p = c / 10;
}
if (p > 0)
rez.push_back(p);
return rez;
}
vector<int> ucitajBroj(const string& broj) {
vector<int> rez(broj.size());
for (int i = broj.size() - 1; i >= 0; i--)
rez.push_back(broj[i] - '0');
return rez;
}
string ispisiBroj(const vector<int>& broj) {
string s;
for (int i = broj.size() - 1; i >= 0; i--)
s.push_back('0' + broj[i]);
return s;
}
int main() {
string broj; cin >> broj;
vector<int> zbir; zbir.push_back(0);
vector<int> b; b.push_back(1);
for (char c : broj) {
zbir = saberi(zbir, saberi(mnoziBrojem(zbir, 10),
mnoziBrojem(b, c - '0')));
b = mnoziBrojem(b, 2);
}
cout << ispisiBroj(zbir) << endl;
return 0;
}Zadatak se mnogo lakše može rešiti ako se koristi bibliotečki tip podataka za rad sa velikim brojevima. Na žalost, ta funkcionalnost ne postoji u standardnoj biblioteci jezika C++, ali su dostupne kvalitetne biblioteke otvorenog koda koje se mogu iskoristiti (npr. GNU Multiprecision Library - GMP).
Dati niz od \(n\) celih brojeva ciklički pomeriti (rotirati) za \(k\) mesta ulevo.
U prvoj liniji standardnog ulaza nalazi se prirodan broj \(k\) (\(1 \le k \le 10^5\)) koji predstavlja broj mesta za koja se niz pomera ulevo, u drugoj prirodan broj \(n\) (\(1\le n \le 10^5\)), koji predstavlja broj elemenata niza, a zatim se u sledećih \(n\) linija nalaze celi brojevi u granicama od \(-1000\) do \(1000\) koji predstavljaju elemente niza.
U \(n\) linija standardnog izlaza ispisati elemente niza koji se dobija cikličkim pomeranjem učitanog niza za \(k\) mesta ulevo.
3 10 1 2 3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 1 2 3
Pošto se cikličnim pomeranjem za \(n\) mesta niz vraća u svoju originalnu poziciju, nije teško uočiti da je cikličko pomeranje za \(k\) mesta ulevo isto što i cikličko pomeranje za \(k \,\mathrm{mod}\,n\) mesta ulevo. Zato ćemo u svim narednim rešenjima pretpostaviti da se nakon učitavanja broja k on menja vrednošću k % n i da važi da je \(0 \leq k < n\).
Zadatak se može rešiti na zaista mnogo različitih načina, koji se razlikuju po količini dodatne memorije koju koriste i po broju operacija koje je potrebno primeniti. S obzirom na potencijalno velike dimenzije ulaznog niza, poželjno je koristiti ona rešenja koja niz transformišu u mestu tj. ne koriste pomoćne nizove, i kod koji je broj operacija linearan (tj. proporcionalan broju \(n\)).
Ako bi niz imao \(2k\) elemenata, rotacija za \(k\) mesta bi se vršila tako što bi se razmenili blokovi elemenata koji čine prvu i drugu polovinu niza. U opštem slučaju situacija je malo komplikovanija, ali se ponovo može svesti na razmenu blokova elemenata. Neka niz ima \(n\) elemenata i neka ga rotiramo za \(k\) mesta ulevo. Neka prvih \(k\) elemenata čine blok koji ćemo označiti sa \(L\), a preostalih \(n-k\) elemenata čine blok koji ćemo označiti sa \(D\). Razmotrimo sledeće slučajeve, u zavisnosti od odnosa dužina ta dva bloka.
Ako su blokovi \(L\) i \(D\) jednake dužine, njihovom razmenom se dobija traženo rešenje.
Ako je blok \(L\) kraći, označimo sa \(D_1\) početni deo bloka \(D\) dužine \(k\), a sa \(D_2\), preostali deo bloka \(D\). Elementi bloka \(D_1\) treba da budu početni elementi u traženom rešenju i da bismo to postigli, možemo ih razmeniti sa elementima bloka \(L\). Time iz situacije \(LD_1D_2\) dolazimo u situaciju \(D_1LD_2\), dok je traženo rešenje oblika \(DL\), tj. \(D_1D_2L\). Da bismo to postigli, potrebno je da niz \(LD_2\) zarotiramo za dužinu bloka \(L\) ulevo (a to je opet \(k\)), tj. da razmenimo blokove \(L\) i \(D_2\), što je problem istog oblika, ali manje dimenzije od polaznog.
Ako je blok \(L\) duži, označimo sa \(L_1\) početni deo bloka \(L\) dužine \(n-k\), a sa \(L_2\), preostali deo bloka \(L\). Elementi bloka \(D\) treba da budu početni elementi u traženom rešenju i da bismo to postigli, možemo ih razmeniti sa elementima bloka \(L_1\). Time iz situacije \(L_1L_2D\) dolazimo u situaciju \(DL_2L_1\), dok je traženo rešenje oblika \(DL\), tj. \(DL_1L_2\). Da bismo to postigli, potrebno je da niz \(L_2L_1\) zarotiramo za dužinu bloka \(L_2\) ulevo (a to je \(2k-n\)), tj. da razmenimo blokove \(L_2\) i \(L_1\), što je problem istog oblika, ali manje dimenzije od polaznog.
Dakle, zadatak se može rešiti induktivno-rekurzivnom konstrukcijom. Prvi slučaj možemo podvesti pod drugi (ili treći) jer se kompletan levi blok zamenjuje sa desnim, nakon čega ostaje da se razmene prazni blokovi, što ne proizvodi nikakav efekat, pa izlaz iz rekurzije može biti slučaj kada je bilo koji od blokova prazan.
Pretpostavićemo da na raspolaganju imamo funkciju razmeni koja u datom nizu ili vektoru razmenjuje blokove iste dužine koji se ne preklapaju i koji počinju na dve date pozicije. Tu funkciju je veoma jednostavno implementirati. U jeziku C++ može se iskoristiti bibliotečka funkcija swap_ranges koja kao argumente prima dva iteratora koja ograničavaju prvi blok i iterator koji ukazuje na početak drugog bloka.
Rešenje se može isprogramirati rekurzivno.
// razmenjujemo u vektoru "v" blok duzine "duzina" koji pocinje na
// poziciji "p1" sa blokom duzine d koji pocinje na poiciji "p2"
void razmeni(vector<int>& v, int p1, int p2, int d) {
for (int i = 0; i < d; i++)
swap(v[p1+i], v[p2+i]);
}
// funkcija rotira elemente niza a, duzine n za k mesta ulevo
void RotirajUlevo(vector<int>& a, int k) {
// broj elemenata niza
int n = a.size();
// ciklicko pomeranje za k mesta je isto sto i ciklicko pomeranje za
// k % n mesta
k %= n;
// vrsimo rotiranje niza
int dl = k;
int dd = n-k;
while (true) {
if (dl < dd) {
// niz je oblika LD1D2, |L|=|D2| i razmenjujemo L i D2 tako da
// dobijamo D2D1L
razmeni(a, 0, dd, dl);
dd -= dl;
} else if (dl > dd) {
// niz je oblika L1L2D, |L1|=|D| i razmenjujemo L2 i D tako da
// dobijamo L1DL2
razmeni(a, dl-dd, dl, dd);
dl -= dd;
} else {
// niz je oblika LD, |L|=|D| i razmenjujemo L i D cime
// zavrsavamo postupak
razmeni(a, 0, dl, dl);
break;
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// razmenjujemo u vektoru "v" blok duzine "duzina" koji pocinje na
// poziciji "p1" sa blokom duzine d koji pocinje na poiciji "p2"
void razmeni(vector<int>& v, int p1, int p2, int d) {
for (int i = 0; i < d; i++)
swap(v[p1+i], v[p2+i]);
}
// funkcija rotira elemente niza a, duzine n za k mesta ulevo
void RotirajUlevo(vector<int>& a, int k) {
// broj elemenata niza
int n = a.size();
// ciklicko pomeranje za k mesta je isto sto i ciklicko pomeranje za
// k % n mesta
k %= n;
// vrsimo rotiranje niza
int dl = k;
int dd = n-k;
while (true) {
if (dl < dd) {
// niz je oblika LD1D2, |L|=|D2| i razmenjujemo L i D2 tako da
// dobijamo D2D1L
razmeni(a, 0, dd, dl);
dd -= dl;
} else if (dl > dd) {
// niz je oblika L1L2D, |L1|=|D| i razmenjujemo L2 i D tako da
// dobijamo L1DL2
razmeni(a, dl-dd, dl, dd);
dl -= dd;
} else {
// niz je oblika LD, |L|=|D| i razmenjujemo L i D cime
// zavrsavamo postupak
razmeni(a, 0, dl, dl);
break;
}
}
}
int main() {
// ubrzavamo ucitavanje i ispis
ios_base::sync_with_stdio(false);
// ucitavamo ulazne podatke
int k, n;
cin >> k >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
RotirajUlevo(a, k);
// ispisujemo rotirani niz
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}Primer 4.A.1. Razmotrimo sledeći primer. Želimo da rotiramo sledeći niz \([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\) za 4 mesta ulevo.
Nakon rotacije trebalo bi da dobijemo \([5, 6, 7, 8, 9, 10, 1, 2, 3, 4]\).
Rotacija se vrši tako što razmenjujemo levi blok \(L = [1, 2, 3, 4]\) sa desnim blokom \(D = [5, 6, 7, 8, 9, 10]\). Važi da je \(p_l = 0\), \(d_l=k=4\), \(p_d=k=4\) i \(d_d=n-k=6\). Pošto je levi blok kraći od desnog bloka, možemo zameniti ceo blok \(L\) sa blokom \(D_1 = [5, 6, 7, 8]\). Tako dobijamo \([5, 6, 7, 8, 1, 2, 3, 4, 9, 10]\).
Na taj načini brojevi \([5, 6, 7, 8]\) su došli na svoje mesto, a da bi se od ovog niza dobio krajnji rezultat, potrebno je u delu niza iza njih razmeniti blok \(L = [1, 2, 3, 4]\) i blok \(D_2 = [9, 10]\).
Sada je \(L = [1, 2, 3, 4]\), a \(D=[9, 10]\). Važi da je \(p_l = 4\), \(d_l=4\), \(p_d=8\) i \(d_d=2\). Pošto je levi blok duži od desnog bloka, razmenjujemo ceo blok \(D\) sa blokom \(L_1 = [1, 2]\) i tako dobijamo \([5, 6, 7, 8, 9, 10, 3, 4, 1, 2]\).
Na taj način su brojevi \([9, 10]\) došli na svoje mesto, a da bi se od ovog niza dobio krajnji rezultat, potrebno je u delu niza iza njih razmeniti blokove \(L_2 = [3, 4]\) i \(L_1 = [1, 2]\).
Sada je \(L = [3, 4]\) i \(D = [1, 2]\). Važi da je \(p_l = 6\), \(d_l=2\), \(p_d=8\) i \(d_d=2\). U ovom slučaju je dužina oba bloka jednaka, pa se nakon njihove razmene dobijamo \([5, 6, 7, 8, 9, 10, 1, 2, 3, 4]\) i procedura se zaustavlja.
Dokažimo da se algoritam zaustavlja i procenimo mu složenost. Centralna mera progresa u algoritmu je ukupna dužina blokova koji se razmenjuju. Ukupna dužina kreće od \(n\) i smanjuje se sve dok ne dođe do nule. U prvom slučaju se vrši razmena blokova dužine \(d_l\) za šta je potrebno \(O(d_l)\) koraka i nakon toga se vrši rekurzivni poziv takav da je zbir dužina blokova upravo za \(d_l\) manji od polaznog zbira dužina (novi zbir je \(d_l + (d_d - d_l) = d_d\), a polazni \(d_l + d_d\)). Slično, u drugom slučaju se vrši zamena blokova dužine \(d_d\) za šta je potrebno \(O(d_d)\) koraka i nakon toga se vrši rekurzivni poziv takav da je zbir dužina blokova upravo za \(d_d\) manji od polaznog zbira dužina (novi zbir je \((d_l - d_d) + d_d = d_l\), a polazni \(d_l + d_d\)). Dakle, rekurentna jednačina je u oba slučaja jednaka \(T(n) = T(n-d) + O(d)\), gde je \(d=\min(d_l, d_d)\) i njeno rešenje je \(T(n) = O(n)\).
Još jednostavnije, u svakom funkcije razmeni se pomoću \(d\) razmena tačno \(d\) elemenata dovodi na svoje finalno mesto, odakle se više ne mrda, a u rekurzivnoj funkciji se osim toga (i rekurzivnih poziva) ne vrši nikakav drugi posao. Pošto se po završetku rekurzije svaki element nalazi na svom mestu izvšeno je tačno \(n\) razmena.
// razmenjujemo u vektoru v blok duzine d koji pocinje na
// poziciji p1 sa blokom duzine duzina koji pocinje na poziciji p2
void razmeni(vector<int>& v, int p1, int p2, int d) {
swap_ranges(next(v.begin(), p1), next(v.begin(), p1 + d),
next(v.begin(), p2));
}
// razmenjujemo u vektoru v blok L koji pocinje na poziciji pl i
// duzine je dl i blok D koji pocinje na poziciji pd i duzine je dd
void razmeniBlokove(vector<int>& v, int pl, int dl, int pd, int dd) {
// ako je neki blok prazan nema potrebe za razmenom
if (dl == 0 || dd == 0)
return;
if (dl <= dd) {
// razmenjujemo kompletan levi blok sa pocetkom desnog
razmeni(v, pl, pd, dl);
// iz situacije L.D1.D2 dosli smo u situaciju D1.L.D2 i
// da bismo dosli u zeljenu situaciju D1.D2.L moramo
// da razmenimo L i D2
razmeniBlokove(v, pl + dl, dl, pd + dl, dd - dl);
} else {
// razmenjujemo kompletan desni blok sa pocetkom levog
razmeni(v, pl, pd, dd);
// iz situacije L1.L2.D dosli smo u situaciju D.L2.L1 i
// da bismo dosli u zeljenu situaciju D.L1.L2 moramo
// da razmenimo L1 i L2
razmeniBlokove(v, pl + dd, dl - dd, pd, dd);
}
}
void rotiraj(vector<int>& v, int k) {
// razmenjujemo pocetni blok duzine k i ostatak niza
razmeniBlokove(v, 0, k, k, v.size() - k);
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// razmenjujemo u vektoru v blok duzine d koji pocinje na
// poziciji p1 sa blokom duzine duzina koji pocinje na poziciji p2
void razmeni(vector<int>& v, int p1, int p2, int d) {
swap_ranges(next(v.begin(), p1), next(v.begin(), p1 + d),
next(v.begin(), p2));
}
// razmenjujemo u vektoru v blok L koji pocinje na poziciji pl i
// duzine je dl i blok D koji pocinje na poziciji pd i duzine je dd
void razmeniBlokove(vector<int>& v, int pl, int dl, int pd, int dd) {
// ako je neki blok prazan nema potrebe za razmenom
if (dl == 0 || dd == 0)
return;
if (dl <= dd) {
// razmenjujemo kompletan levi blok sa pocetkom desnog
razmeni(v, pl, pd, dl);
// iz situacije L.D1.D2 dosli smo u situaciju D1.L.D2 i
// da bismo dosli u zeljenu situaciju D1.D2.L moramo
// da razmenimo L i D2
razmeniBlokove(v, pl + dl, dl, pd + dl, dd - dl);
} else {
// razmenjujemo kompletan desni blok sa pocetkom levog
razmeni(v, pl, pd, dd);
// iz situacije L1.L2.D dosli smo u situaciju D.L2.L1 i
// da bismo dosli u zeljenu situaciju D.L1.L2 moramo
// da razmenimo L1 i L2
razmeniBlokove(v, pl + dd, dl - dd, pd, dd);
}
}
void rotiraj(vector<int>& v, int k) {
// razmenjujemo pocetni blok duzine k i ostatak niza
razmeniBlokove(v, 0, k, k, v.size() - k);
}
int main() {
// ubrzavamo ucitavanje i ispis
ios_base::sync_with_stdio(false);
// ucitavamo ulazne podatke
int k, n;
cin >> k >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ciklicko pomeranje za k mesta je isto sto i ciklicko pomeranje za
// k % n mesta
k %= n;
// vrsimo rotiranje niza
rotiraj(a, k);
// ispisujemo rotirani niz
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}Rekurzija je repna i lako je se možemo osloboditi. Moguća je i dodatna optimizacija, jer početne pozicije blokova koji se razmenjuju ne moramo posebno pamtiti, već ih možemo uvek izračunati ako znamo dužine blokova koji se razmenjuju i znamo da se oni nalaze u završnom delu niza. Ilustracije radi, prikazaćemo malo drugačije iterativno rešenje u kom ćemo pretpostaviti da u svakom koraku blok koji treba da se nađe na kraju niza dovodimo na njegovo mesto, a da nakon toga razmene preostalih blokova vršimo na početku niza.
Pretpostavimo da je u svakom koraku petlje potrebno razmeniti blokove \(L\) i \(D\) koji se sastoje od početnih \(d_l\), pa zatim \(d_d\) elemenata niza. Vrednosti \(d_l\) i \(d_d\) se inicijalizuju na \(k\) i \(n-k\), a zatim se u petlji ponavlja sledeće.
Ako su \(d_l\) i \(d_d\) jednaki, tada se razmenjuju blokovi koji počinju na pozicjama \(0\) i \(d_l\) i koji su dužine \(d_l = d_d\) i petlja se prekida.
Ako je \(d_l < d_d\), niz je oblika \(LD_1D_2\), gde je \(|D_2| = |L| = d_l\). Razmenićemo blokove \(L\) i \(D_2\). Prvi počinje na poziciji \(0\), a drugi na poziciji \(|LD_1| = d_l + (d_d - d_l) = d_d\). Nakon toga ćemo dobiti niz \(D_2D_1L\) i preostaće nam da razmenimo blokove \(D_2\) i \(D_1\), koji su na početku niza. Dužina bloka \(D_2\) je \(d_l\), a bloka \(D_1\) je \(d_d - d_l\). Zato se vrednost \(d_d\) umanjuje za \(d_l\), dok se \(d_d\) ne menja.
Ako je \(d_l > d_d\), niz je oblika \(L_1L_2D\), gde je \(|L_2| = |D| = d_d\). Razmenićemo blokove \(L_2\) i \(D\). Prvi počinje na poziciji \(|L_1| = d_l - d_d\), a drugi na poziciji \(|L_1L_2| = d_l\). Nakon toga ćemo dobiti niz \(L_1DL_2\) i preostaće nam da razmenimo blokove \(L_1\) i \(D\). Dužina bloka \(L_2\) jednaka je dužini bloka \(D\) i iznosi \(d_d\), pa je dužina bloka \(L_1\) jednaka \(d_l - d_d\). Zato se \(d_l\) umanjuje za \(d_d\) dok se \(d_d\) ne menja.
Primer 4.A.2. Primenimo opisani algoritam na još jednom primeru. Neka je dat niz \([1, 2, 3, 4, 5]\) i \(k=3\).
U početku je \(d_l=k=3\) i \(d_d=n-k=2\), pa treba razmeniti blokove \(L=[1, 2, 3]\) i \(D=[4, 5]\). Pošto je \(d_d < d_l\), razmenjuje se se blok \(L_2=[2, 3]\), koji počinje na poziciji \(d_l - d_d=1\) i blok \(D=[4, 5]\), koji počinje na poziciji \(d_l=3\). Oba su dužine \(d_d=2\). Tako se dobija niz \([1, 4, 5, 2, 3]\). Nakon toga se \(d_l\) umanjuje za \(d_d\) i postaje \(1\).
Sada je \(d_l=1\) i \(d_d=2\), pa treba razmeniti blokove \(L=[1]\) i \(D=[4, 5]\). Pošto je \(d_l < d_d\), razmenjuju se levi blok \(L=[1]\), koji počinje na poziciji \(0\) i desni blok \(D_2=[5]\), koji počinje na poziciji \(d_d=2\) (oba su dužine \(d_l=1\)). Tako se dobija niz \([5, 4, 1, 2, 3]\). Nakon toga se \(d_d\) umanjuje za \(d_l\) i postaje \(1\).
Sada je \(d_l=d_d=1\). Zato se razmenjuju blokovi \([5]\) i \([4]\), koji počinju na poziciji \(0\) tj. \(d_l=1\), čime se niz dovodi u željenu konfiguraciju \([4, 5, 1, 2, 3]\).
Primetimo da je složenost ovog postupka linearna, jer se u svakom koraku pomoću \(d\) razmena bar \(d\) elemenata dovodi na svoje konačno mesto i eliminiše iz dalje obrade.
Bazirano na ideji razmene blokova, tj. na prethodnim induktivno-rekurzivnim konstrukcijama možemo formulisati još jedan algoritam (sa dosta elegantnom implementacijom). Pretpostavimo da imamo na raspolaganju promenljive \(l\) i \(d\) koje ukazuju na početak blokova \(L\) i \(D\) i promenljive \(k\) i \(n\) koje ukazuju na njihove krajeve (preciznije, pozicije iza njihovih krajeva).
Na početku je \(l = 0\) i \(d = k\).
U petlji razmenjujemo elemente na pozicijama \(l\) i \(d\), uvećavajući, pri tom, oba indeksa. Tokom postupka će se dogoditi ili da indeks \(l\) dostigne \(k\) ili da indeks \(d\) dostigne \(n\).
Ako se obe stvari dogode istovremeno, blokovi su bili iste dužine i uspešno smo ih razmenili, čime je posao završen.
Ako \(l\) dostigne \(k\) pre nego što \(d\) dostigne \(n\), tada je levi blok bio kraći i u ovoj situaciji je zapravo razmenjen sa početnim delom desnog bloka, čime se došlo u konfiguraciju \(D_1LD_2\). Preostalo je još razmeniti blokove \(L\) i \(D_2\). Početak bloka \(L\) je na mestu trenutnog indeksa \(l\), a kraj mu je tik ispred tekućeg indeksa \(d\) i zato ažuriramo vrednost \(k\) na vrednost \(d\). Početak i kraj dela \(D_2\) su na svojim ispravnim vrednostima (\(d\) i \(n\)).
Ako \(d\) dostigne \(n\) pre nego što \(l\) dostigne \(k\), tada je desni blok bio kraći i u ovoj situaciji je zapravo razmenjen sa početnim delom levog bloka, čime se došlo u konfiguraciju \(DL_2L_1\). Preostalo je još razmeniti blokove \(L_2\) i \(L_1\). Početak bloka \(L_2\) je na mestu trenutnog indeksa \(l\), a kraj mu je tik ispred tekućeg indeksa \(k\). Međutim, početak bloka \(L_1\) je na mestu tekućeg indeksa \(k\) i zato je potrebno vrednost \(d\) postaviti na \(k\), dok je kraj bloka \(L_1\) tik ispred indeksa \(n\).
Dakle, algoritam može imati narednu, veoma elegantnu implementaciju.
void RotirajUlevo(vector<int>& a, int k) {
// broj clanova niza
int n = a.size();
// ciklicko pomeranje za k mesta je isto sto i ciklicko pomeranje za
// k % n mesta
k %= n;
// vrsimo rotiranje niza razmenom blokova
int l = 0; // pocetak levog bloka
int d = k; // pocetak desnog bloka
// razmenjujemo blokove L i D tj. blokove [l, k) i [d, n)
while (true) {
// menjamo tekuce elemente u blokovima
swap(a[l++], a[d++]);
// stigli smo do kraja oba bloka, pa je posao zavrsen
if (l == k && d == n)
break;
if (d == n) // stigli smo do kraja desnog bloka
// razmenili smo pocetak levog bloka sa desnim i dosli u
// situaciju DL2L1 i jos treba da razmenimo blokove L2 i L1, a
// to su blokovi [l, k) i [k, n), tako da d treba postaviti na k
d = k;
if (l == k) // stigli smo do kraja levog bloka
// razmenili smo levi blok sa pocetkom desnog i dosli u situaciju
// D1LD2 i jos treba da razmenimo blokove L i D2, a to su blokovi
// [l, d) i [d, n), tako da k treba postaviti na d
k = d;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void RotirajUlevo(vector<int>& a, int k) {
// broj clanova niza
int n = a.size();
// ciklicko pomeranje za k mesta je isto sto i ciklicko pomeranje za
// k % n mesta
k %= n;
// vrsimo rotiranje niza razmenom blokova
int l = 0; // pocetak levog bloka
int d = k; // pocetak desnog bloka
// razmenjujemo blokove L i D tj. blokove [l, k) i [d, n)
while (true) {
// menjamo tekuce elemente u blokovima
swap(a[l++], a[d++]);
// stigli smo do kraja oba bloka, pa je posao zavrsen
if (l == k && d == n)
break;
if (d == n) // stigli smo do kraja desnog bloka
// razmenili smo pocetak levog bloka sa desnim i dosli u
// situaciju DL2L1 i jos treba da razmenimo blokove L2 i L1, a
// to su blokovi [l, k) i [k, n), tako da d treba postaviti na k
d = k;
if (l == k) // stigli smo do kraja levog bloka
// razmenili smo levi blok sa pocetkom desnog i dosli u situaciju
// D1LD2 i jos treba da razmenimo blokove L i D2, a to su blokovi
// [l, d) i [d, n), tako da k treba postaviti na d
k = d;
}
}
int main() {
// ubrzavamo ucitavanje i ispis
ios_base::sync_with_stdio(false);
// ucitavanje podataka
int k, n;
cin >> k >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// rotiramo niz za k mesta ulevo
RotirajUlevo(a, k);
// ispisujemo rotirani niz
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}Složenost je linearna u odnosu na dužinu niza i ne koristi se dodatni memorijski prostor osim pomoćne promenljive u sklopu razmene dva elementa niza.
Primer 4.A.3. Primenimo opisani algoritam na primeru. Neka je dat niz \([1, 2, 3, 4, 5]\) i \(k=3\).
Brojač \(l\) kreće od vrednosti \(0\), brojač \(d\) od vrednosti \(k=3\), tj. kreće se sa obradom blokova \([1, 2, 3]\) i \([4, 5]\). U trenutku kada brojač \(d\) dođe do kraja (do vrednosti \(n\)), brojač \(l\) ima vrednost 2. Tada je konfiguracija niza \([4, 5, 3, 1, 2]\).
Tada se vrednost \(d\) postavlja na tekuću vrednost \(k\) a to je \(3\) i prelazi se na obradu blokova \([3]\) i \([1, 2]\). Ovaj put \(l\) stiže do vrednosti \(k\) kada \(d\) ima vrednost 4 i tada je konfiguracija \([4, 5, 1, 3, 2]\).
Tada se \(k\) pomera na 4 i razmatraju se blokovi \([3]\) i \([2]\). Nakon njihove razmene dolazi se do kraja i tražene konfiguracije \([4, 5, 1, 2, 3]\).
Veoma interesantno bi bilo dokazati direktno da je ovaj algoritam korektan. U nastavku ćemo jedino dokazati da se prethodni algoritam zaustavlja (što nije samo po sebi trivijalno). Jedna od invarijanti prethodne petlje je da je \(0 \leq l \leq k \leq d \leq n\). Dokažimo to.
Pošto je \(0 < n\), \(0 < k\) i \(k < n\), na početku važi \(0 = l < k = d < n\), pa je invarijanta ispunjena.
Pošto je \(0 < k\), na osnovu uslova prekida petlje, kada se uđe u telo petlje znamo da je \(0 \leq l < k \leq d < n\). Nakon toga se \(l\) i \(d\) uvećavaju za 1, pa nakon toga važi \(0 \leq l \leq k < d \leq n\). Ako je \(l = k\) i \(d = n\), petlja se završava, a invarijanta važi i nakon prekida petlje. U suprotnom, ako je \(l = k\), tada je \(d < n\), dok se \(k\) postavlja na \(d\), pa odnos \(0 \leq l < k \leq d < n\) važi i pre naredne iteracije. Slično, ako je \(d = n\), tada je \(l < k\), dok se \(d\) postavlja na \(k\), pa odnos \(0 \leq l < k \leq d < n\) važi i pre naredne iteracije. Na osnovu ovoga znamo da ova invarijanta ostaje ispunjena i nakon izvršavanja tela petlje.
Potrebno je još dokazati da se u nekom trenutku mora dogoditi da je \(l = k\) ili da je \(d = n\). Međutim, u svakom koraku petlje promenljiva \(l\) se uvećava za \(1\), dok se gornja granica \(n\) ne menja. Stoga znamo da će se nakon najviše \(n\) koraka desiti da je \(l = n\). Na osnovu invarijante tada će morati da važi da je \(l = k = d = n\), pa će se petlja zaustaviti. Ujedno vidimo i da se u najgorem slučaju petlja izvršava \(n\) puta, pa je algoritam složenosti \(O(n)\).
Sažete forme niski se grade od malih slova engleskog alfabeta i cifara od 2 do 9. Svaka cifra u sažetoj formi označava da se niska određena prefiksom sažete forme pre te cifre ponavlja onoliko puta kolika je vrednost te cifre. Na primer, sažeta forma a2b3 označava nisku aabaabaab (a ne aabbb), jer cifra 2 iza a označava da se a ponavlja dva puta, pa a2b predstavlja nisku aab, dok cifra 3 iza a2b označava da se niska određena sažetom formom a2b, a to je aab, ponavlja tri puta. Napiši program koji određuje dužinu niske zadate nekom sažetom formom.
Sa standardnog ulaza se učitava sažeta forma niske koja je dužine manje od \(10^{18}\).
Na standardni izlaz ispisati dužinu sažete forme.
a2bb3c
13
a2b32c
19
Sažeta forma \(s\) je sastavljena ili samo od malih slova (u kom slučaju je trivijalno odrediti njenu dužinu \(|s|\)) ili u sebi sadrži neku cifru. Ako sadrži cifru \(c\), ona je oblika \(s_1cs_2\), gde možemo pretpostaviti da je \(c\) poslednja cifra, tj. da je \(s_1\) sažeta forma, a da je \(s_2\) obična niska (koja ne sadrži cifre). Tada je \(|s| = c \cdot |s_1| + |s_2|\). Dužinu sažete forme \(|s_1|\) određujemo rekurzivno, dok dužinu niske \(|s_2|\) određujemo trivijalno, jer ona ne sadrži karaktere. Ovim je u potpunosti definisan rekurzivni postupak za izračunavanje dužine sažete forme.
Primer 4.A.4. Prikažimo izračunavanje dužine niske \(ab2c3d\).
\[|ab2c3d| = 3|ab2c|+|d| = 3(2|ab|+|c|)+1 = 3(2\cdot 2 + 1) + 1 = 16\]
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll duzina(const string& s) {
const string digits = "0123456789";
size_t p = s.find_last_of(digits);
if (p == string::npos)
return s.length();
else
return duzina(s.substr(0, p)) * (s[p] - '0') + (s.length() - p - 1);
}
int main() {
string s;
cin >> s;
cout << duzina(s) << endl;
return 0;
}Dužinu možemo izračunati i iterativnim postupkom, analizirajući jednu po jednu cifru u sažetom zapisu. Pretpostavićemo da je \(r\) dužina obrađenog dela sažete forme \(s\), a da je \(pp\) broj karaktera tog dela sažete forme (obe inicijalizujemo na nulu). Sve dok u preostalom delu sažete forme postoje cifre, radimo sledeće. Određujemo poziciju \(p\) naredne cifre (to je pozicija prve cifre u delu sažete forme iza pozicije \(pp\)).
Ako takva pozicija postoji, to znači da je sažeta forma zaključno sa pozicijom \(p\) oblika \(s_1s_2c\), gde je \(s_1\) sažeta forma koja sadrži \(pp\) karaktera i predstavlja nisku dužine \(r\), dok se \(c\) nalazi na poziciji \(p\). Dužina niske \(s_2\) je \(p-pp\), pa je dužina niske predstavljene sažetom formom \(s_1s_2c\) jednaka \((r + (p - pp)) \cdot s\) – promenljivu \(r\) ažuriramo baš na tu vrednost.
Na kraju, kada ustanovimo da iza pozicije \(pp\) ne postoji više cifara znamo da je sažeta forma oblika \(s_1s_2\), gde je niska predstavljena formom \(s_1\) dužine \(r\), dok je broj karaktera dela \(s_2\), pa i dužina niske koja je njime predstavljena jednaka razlici između dužine cele sažete forme i pozicije \(pp\). Zato se na kraju \(r\) uvećava tačno za tu razliku.
Primer 4.A.5. Prikažimo kretanje promenljivih tokom obrade sažete forme \(ab2c3d\).
pp r p obradjen deo forme s 0 0 2 - 3 4 4 ab2 5 15 - ab2c3 16 ab2c3d
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll duzina(const string& s) {
const string digits = "0123456789";
size_t pp = 0;
size_t p = s.find_first_of(digits);
ll rez = 0;
while (p != string::npos) {
rez += p - pp;
rez *= s[p] - '0';
pp = p+1;
p = s.find_first_of(digits, p+1);
}
rez += s.length() - pp;
return rez;
}
int main() {
string s;
cin >> s;
cout << duzina(s) << endl;
return 0;
}Rekurzivnu funkciju je moguće organizovati i na osnovu analize poslednjeg karaktera sažete forme.
Ako je sažeta forma prazna dužina niske koju predstavlja je nula.
Ako je poslednji karakter sažete forme slovo, onda je dužina niske koju predstavlja za jedan veća od dužine niske koju predstavlja sažeta forma bez tog poslednjeg slova.
Ako je poslednji karakter sažete forme cifra, onda je dužina niske koju predstavlja jednaka proizvodu te cifre i dužine niske koju predstavlja sažeta forma bez te poslednje cifre.
Primer 4.A.6. Prikažimo postupak izračunavanja dužine sažete forme \(ab2c3d\).
\[\begin{eqnarray*} |ab2c3d| &=& |ab2c3| + 1 = |ab2c|\cdot 3 + 1 = (|ab2| + 1)\cdot 3 + 1 = (|ab|\cdot 2 + 1) \cdot 3 + 1\\ &=& ((|a| + 1)\cdot 2 + 1)\cdot 3 + 1 = (((|\varepsilon| + 1) + 1)\cdot 2 + 1) \cdot 3 + 1 \\ &=& (((0+1)+1)\cdot 2 + 1)\cdot 3 + 1 = 16 \end{eqnarray*}\]
#include <iostream>
#include <string>
using namespace std;
// duzina prefiksa duzine n sazete forme s
long long duzina(const string& s, int n) {
if (n == 0)
return 0;
if (!isdigit(s[n-1]))
return duzina(s, n-1) + 1;
else
return duzina(s, n-1) * (s[n-1] - '0');
}
// duzina sazete forme s
long long duzina(const string& s) {
return duzina(s, s.length());
}
int main() {
string s;
cin >> s;
cout << duzina(s) << endl;
return 0;
}Dužinu možemo izračunati i iterativnim postupkom, analizirajući jedan po jedan karakter sleva nadesno. U svakom trenutku broj \(r\) predstavlja dužinu niske predstavljene do tada obrađenim karakterima sažete forme \(s\). Na početku nije obrađen ni jedan karakter, pa se \(r\) inicijalizuje na nulu. Ako je tekući karakter slovo, \(r\) se uvećava za 1, a ako je cifra, tada se \(r\) množi tom cifrom.
Primer 4.A.7. Prikažimo kretanje promenljivih tokom obrade sažete forme \(ab2c3d\).
r c obradjen deo forme s 0 a - 1 b a 2 2 ab 4 c ab2 5 3 ab2c 15 d ab2c3 16 ab2c3d
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll duzina(const string& s) {
// duzina prefiksa sazete forme s koji se sastoji od do sada
// obradjenih karaktera niske s
ll rez = 0;
// obradjujemo karakter po karakter i azuriramo duzinu obradjenog dela
// sazete forme s
for (char c : s)
if (isdigit(c))
rez *= c - '0';
else
rez++;
return rez;
}
int main() {
string s;
cin >> s;
cout << duzina(s) << endl;
return 0;
}Sažete forme niski se grade od malih slova engleskog alfabeta i cifara od 2 do 9. Svaka cifra u sažetoj formi označava da se niska određena prefiksom sažete forme pre te cifre ponavlja onoliko puta kolika je vrednost te cifre. Na primer, sažeta forma a2b3 označava nisku aabaabaab (a ne aabbb), jer cifra 2 iza a označava da se a ponavlja dva puta, pa a2b predstavlja nisku aab, dok cifra 3 iza a2b označava da se niska određena sažetom formom a2b, a to je aab, ponavlja tri puta. Napiši program koji određuje element na poziciji \(k\) unutar niske zadate nekom sažetom formom.
Sa standardnog ulaza se učitava sažeta forma niske koja je dužine manje od \(10^{18}\), a zatim i broj \(k\) koji je veći ili jednak od \(0\), a strogo manji od dužine niske.
Na standardni izlaz ispisati traženo slovo.
zdravo2svima3 30
v
a2b3ca3d2f 40
a
Sažeta forma niske je ili sastavljena samo od malih slova ili je oblika \(s_1cs_2\), gde je \(c\) cifra, a \(s_2\) je niska sastavljena samo od malih slova.
Ako se sažeta forma se sastoji samo od malih slova, ona je jednaka niski koju predstavlja i njeno slovo na poziciji \(k\) se trivijalno očitava.
Ako je sažeta forma oblika \(s_1cs_2\), tada ona predstavlja nisku koja se sastoji od \(c\) kopija niske predstavljene sažetom formom \(s_1\) na koje je nadovezana niska \(s_2\). Ako je \(d = |s_1|\) dužina niske predstavljene sažetom formom \(s_1\), razlikovaćemo slučaj kada je \(k < c\cdot d\) i kada je \(k \geq c\cdot d\).
Ako je \(k < c\cdot d\), tada treba izračunati slovo na poziciji \(k\) u \(c\) ponovljenih kopija niske predstavljene sažetom formom \(s_1\) (njihova ukupna dužina je \(c\cdot d\)). Pošto se slova ciklično ponavljaju sa periodom \(d\), potrebno je odrediti slovo na poziciji \(k\,\mathrm{mod}\,d\) u niski predstavljenoj sažetom formom \(s_1\), što se može uraditi rekurzivnim pozivom.
Ako je \(k \geq c\cdot d\), tada slovo pripada niski \(s_2\) i nalazi se u njoj na poziciji \(k - c\cdot d\).
Primer 4.A.8. Razmotrimo primer pronalaženja karaktera na poziciji 40 u niski određenoj sažetom formom \(a2b3ca3d2f\).
Sažeta forma \(s=a2b3ca3d2f\) se razlaže na \(s_1 = a2b3ca3d\), \(c=2\) i \(s_2 = f\). Dužina \(d = |s_1| = 34\), pa je \(40 = k < cd = 68\). Zato određujemo karakter na poziciji \(40 \,\mathrm{mod}\,34 = 6\) u niski određenoj sažetom formom \(a2b3ca3d\).
Sažeta forma \(s=a2b3ca3d\) se razlaže na \(s_1 = a2b3ca\), \(c=3\) i \(s_2 = d\). Dužina \(d = |s_1| = 11\), pa je \(6 = k < cd = 33\). Zato određujemo karakter na poziciji \(6 \,\mathrm{mod}\,11 = 6\) u niski određenoj sažetom formom \(a2b3ca\).
Sažeta forma \(s=a2b3ca\) se razlaže na \(s_1 = a2b\), \(c=3\) i \(s_2 = ca\). Dužina \(d = |s_1| = 3\), pa je \(6 = k < cd = 9\). Zato određujemo karakter na poziciji \(6 \,\mathrm{mod}\,3 = 0\) u niski određenoj sažetom formom \(a2b\).
Sažeta forma \(a2b\) se razlaže na \(s_1=a\), \(c=2\) i \(s_2=b\). Dužina \(d=|s_1| = 1\), pa je \(0 = k < cd = 2\). Zato određujemo karakter na poziciji \(0 \,\mathrm{mod}\,1 = 0\) u niski određenoj sažetom formom \(a\).
Niska \(a\) ne sadrži cifre, pa čitamo njen karakter na poziciji 0 i to je \(a\).
Direktna implementacija prethodnog algoritma koja izračunava dužinu podniske tako što svaki put poziva funkciju koja izračunava dužinu sažete forme nije najefikasnija, jer dolazi do ponavljanja identičnih izračunavanja. Ovo bi se se moglo optimizovati tako što bi se primenila memoizacija i tako što bi se dužine svih prefiksa sažete forme upamtile u niz. Umesto eksplicitnog izdvajanja prefiksa (funkcijom za izdvajanje podniske), mogli bismo čuvati stalno originalnu nisku i poziciju koja određuje dužinu prefiksa. S obzirom na to da je sažeta forma (za razliku od niske koja je njome predstavljena) obično veoma kratka, ove optimizacije nisu neophodne.
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const string digits = "0123456789";
ll duzina(const string& s) {
size_t p = s.find_last_of(digits);
if (p == string::npos)
return s.length();
else
return duzina(s.substr(0, p)) * (s[p] - '0') + (s.length() - p - 1);
}
char kToSlovo(const string& s, ll k) {
size_t p = s.find_last_of(digits);
if (p == string::npos)
return s[k];
ll d = duzina(s.substr(0, p));
int m = s[p] - '0';
if (k >= m*d)
return s.substr(p+1)[k-m*d];
else
return kToSlovo(s.substr(0, p), k % d);
}
int main() {
string s;
cin >> s;
ll k;
cin >> k;
cout << kToSlovo(s, k) << endl;
return 0;
}Zadatak možemo rešiti i iterativno. U prvoj fazi možemo podeliti sažetu formu na delove koji sadrže podniske sastavljene samo od slova i cifre koje određuju broj ponavljanja. Ako se sažeta forma ne završava cifrom, uniformnosti radi možemo je dopuniti cifrom 1.
Primer 4.A.9. Na primer, sažetu formu \(a2b3ca3d2f\) razlažemo na \((a, 2), (b, 3), (ca, 3), (d, 2), (f, 1)\).
Nakon toga izračunavamo dužine svih niski određenih prefiksima sažete forme. Ako smo sažetu formu razložili na niz parova \((s_0, c_0), (s_1, c_1), \ldots, (s_m, c_m)\), tada računamo redom dužine niski određenih prefiksima \(d_0 = |s_0|\), \(d_1 = |s_0c_0s_1|\), \(d_2 = |s_0c_0s_1c_1s_2|\) itd., zaključno sa dužinom \(d_m = |s_0c_0s_1c_1\ldots c_{m-1}s_m|\). Dužina prvog prefiksa je \(d_0 = |s_0|\), dok se dužina narednih prefiksa izračunava kao \(d_{i} = d_{i-1}\cdot c_{i-1} + |s_i|\), za \(i > 0\).
Primer 4.A.10. Dužine niski određene prefiksima sažete forme \(a2b3ca3d\) su određene na sledeći način.
Na kraju analizu krećemo od kraja tj. od para \((s_m, c_m)\), pa unazad do para \((s_0, c_0)\). U svakom koraku određujemo element na poziciji \(k\) u niski određenoj prefiksom \(s_0c_0\ldots c_{i-1}s_ic_is_{i+1}\) (kada je \(i=m\), tada je \(s_{i+1}\) prazna niska).
Ako je \(k \geq c_i \cdot d_i = c_i |s_0c_0\ldots c_is_i|\), tada traženo slovo pripada niski \(s_{i+1}\) na poziciji \(k - d_ic_i\). Ovo se po uslovima zadatka ne može dogoditi kada je \(i=m\).
U suprotnom se slovo nalazi u niski određenoj pomoću \(c_i\) ponavljanja niske određene prefiksom \(s_0c_0\ldots c_{i-1}s_i\), čija je dužina \(d_i\). To se slovo nalazi na poziciji \(k \,\mathrm{mod}\,d_i\) u niski određenoj prefiksom \(s_0c_0\ldots c_{i-1}s_i\), pa stoga \(k\) menjamo njegovim ostatkom pri deljenju sa \(d_i\) i prelazimo na narednu iteraciju.
Ako se petlja završi a da nismo već odredili traženo slovo, znamo da se karakter nalazi u niski \(s_0\) i to na poziciji \(k\).
Primer 4.A.11. Prikažimo izvršavanje algoritma na primeru pronalaženja karaktera na poziciji \(k = 40\) unutar niske određene sažetom formom \(a2b3ca3d2f\).
Krećemo od vrednosti \(i=m=4\). Važi da je \(k = 40 < c_4d_4 = 1 \cdot 69 = 69\), pa određujemo ostatak pri deljenju \(40\) sa \(69\), ali time \(k\) ostaje \(40\).
Prelazimo na \(i=3\). Važi da je \(k = 40 < c_3d_3 = 2\cdot 34 = 68\), pa određujemo ostatak pri deljenju \(40\) sa \(34\) i menjamo \(k\) na \(6\).
Prelazimo na \(i=2\). Važi da je \(k = 6 < c_2d_2 = 3\cdot 11 = 33\), pa određujemo ostatak pri deljenju \(6\) sa \(11\), ali time \(k\) ostaje \(6\).
Prelazimo na \(i=1\). Važi da je \(k = 6 < c_1d_1 = 3\cdot 3 = 9\), pa određujemo ostatak pri deljenju \(6\) sa \(3\) i menjamo \(k\) na \(0\).
Prelazimo na \(i=0\). Važi da je \(k = 0 < c_0d_0 = 2\cdot 1 = 2\), pa određujemo ostatak pri deljenju \(0\) sa \(1\), ali time \(k\) ostaje \(0\).
Pošto je petlja završena, vraćamo karakter na poziciji \(0\) niske \(s_0\), a to je \(a\).
#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;
typedef long long ll;
const string digits = "0123456789";
vector<pair<string, int>> podeli(const string& s) {
vector<pair<string, int>> rez;
size_t pp = 0, p = s.find_first_of(digits);
while (p != string::npos) {
rez.emplace_back(s.substr(pp, p - pp), s[p] - '0');
pp = p + 1;
p = s.find_first_of(digits, p + 1);
}
if (pp < s.length())
rez.emplace_back(s.substr(pp), 1);
return rez;
}
char kToSlovo(const string& s, ll k) {
auto delovi = podeli(s);
vector<ll> duzine(delovi.size());
duzine[0] = delovi[0].first.length();
for (int i = 1; i < delovi.size(); i++)
duzine[i] = duzine[i-1] * delovi[i-1].second + delovi[i].first.length();
for (int i = delovi.size() - 1; i >= 0; i--) {
if (k >= duzine[i] * delovi[i].second)
return delovi[i+1].first[k - duzine[i]*delovi[i].second];
k %= duzine[i];
}
return delovi[0].first[k];
}
int main() {
string s;
cin >> s;
ll k;
cin >> k;
cout << kToSlovo(s, k) << endl;
return 0;
}