U nastavku ćemo prikazati još neke primere koji ilustruju primenu opisanih tehnika poboljšanja složenosti algoritama.
Napiši program koji određuje koliko u intervalu \([a, b]\) postoji brojeva deljivih brojem \(k\).
Sa standardnog ulaza unose se tri cela broja, svaki u posebnom redu: \(a\) (\(0 \leq a \leq 10^9\)), \(b\) (\(a \leq b \leq 10^9\)), \(k\) (\(1 \leq k \leq 10^9\)).
Na standardni izlaz ispisati traženi ceo broj.
30 53 5
5
Brojevi su 30, 35, 40, 45 i 50.
Moguće je napraviti rešenje zasnovano na pretrazi grubom silom, i koje redom prolazi kroz sve brojeve od \(a\) do \(b\), proverava za svaki da li je deljiv brojem \(k\) i za svaki koji jeste, uvećava brojač pronađenih brojeva. To rešenje je najjednostavnije za razumevanje i implementaciju, međutim može biti neefikasno.
// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
int broj = 0;
for (int i = a; i <= b; i++)
if (i % k == 0)
broj++;
return broj;
}#include <iostream>
using namespace std;
// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
int broj = 0;
for (int i = a; i <= b; i++)
if (i % k == 0)
broj++;
return broj;
}
int main() {
int a, b, k;
cin >> a >> b >> k;
cout << brojDeljivih(a, b, k) << endl;
return 0;
}Složenost ovog rešenja je linearna u odnosu na broj elemenata u intrevalu tj. \(O(b-a)\).
Da bi broj \(x\) bio deljiv brojem \(k\) potrebno je da postoji neko \(n\) tako da je \(x=n\cdot k\). Pošto \(x\) mora biti u intervalu \([a, b]\), mora da važi da je \(a \leq n\cdot k\) i \(n \cdot k \leq b\). Najmanje \(n\) koje zadovoljava prvu nejednačinu jednako je \(n_l = \left\lceil{\frac{a}{k}}\right\rceil\), najveće \(n\) koje zadovoljava drugu nejednačinu jednako je \(n_d = \left\lfloor{\frac{b}{k}}\right\rfloor\). Bilo koji broj iz intervala \([n_l, n_d]\) zadovoljava obe nejednakosti i predstavlja količnik nekog broja iz intervala \([a, b]\) brojem \(k\). Slično, bilo koji broj iz intervala \([a, b]\) deljiv brojem \(k\) daje neki količnik iz intervala \([n_l, n_d]\). Zato je traženi broj brojeva iz intervala \([a, b]\) koji su deljivi brojem \(k\) jednak broju brojeva u intervalu \([n_l, n_d]\) a to je \(n_d - n_l + 1\) ako je \(n_d \geq n_l\), tj. \(0\) ako je taj interval prazan tj. ako je \(n_d < n_l\). Brojevi \(n_l\) i \(n_d\) se mogu odrediti, na primer, grananjem.
// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
int nl = a % k == 0 ? a/k : a/k + 1; // ceil(a/k)
int nd = b / k; // floor(b/k)
int broj = nd >= nl ? nd-nl+1 : 0;
return broj;
}#include <iostream>
using namespace std;
// broj brojeva u intervalu [a, b] deljivih brojem k
int brojDeljivih(int a, int b, int k) {
int nl = a % k == 0 ? a/k : a/k + 1; // ceil(a/k)
int nd = b / k; // floor(b/k)
int broj = nd >= nl ? nd-nl+1 : 0;
return broj;
}
int main() {
int a, b, k;
cin >> a >> b >> k;
cout << brojDeljivih(a, b, k) << endl;
return 0;
}Složenost ovog rešenja je, očigledno, konstantna tj. \(O(1)\).
Dat je pravougaonik dimenzije \(a \times b\), gde su brojevi \(a\) i \(b\) celi. Kolika je maksimalna površina pravougaonika koji se može dobiti produžavanjem stranica tog pravougaonika za ukupnu dužinu \(c\), gde je \(c\) ceo broj i dužine stranica novog pravougaonika su takođe celi brojevi?
Sa standardnog ulaza se učitavaju prirodni brojevi \(a, b, c \leq 10^9\), razdvojeni sa po jednim razmakom.
Na standardni izlaz ispisati maksimalnu površinu nakon produženja stranica.
5 10 3
80
Dimenzija nakon proširenja će biti \(8 \times 10\).
9 10 4
132
Dimenzija nakon proširenja će biti \(11 \times 12\).
14 17 5
324
Zadatak može biti rešen grubom silom, tj. isprobavanjem svih mogućnosti raspodele dodatne dužine. Za svaku dužinu \(i\) između \(0\) i \(c\), dodajemo \(i\) stranici \(a\) i \(c-i\) stranici \(b\), izračunavamo površinu i tražimo maksimum tako dobijenih površina.
long long maksPovrsina(long long a, long long b, long long c) {
long long maks = a * (b + c);
for (long long i = 1; i <= c; i++)
maks = max(maks, (a+i)*(b+c-i));
return maks;
}#include <iostream>
#include <algorithm>
using namespace std;
long long maksPovrsina(long long a, long long b, long long c) {
long long maks = a * (b + c);
for (long long i = 1; i <= c; i++)
maks = max(maks, (a+i)*(b+c-i));
return maks;
}
int main() {
long long a, b, c;
cin >> a >> b >> c;
cout << maksimalnaPovrsina(a, b, c) << endl;
}Složenost ovog rešenja je \(O(c)\).
Dokažimo da od svih pravougaonika datog fiksiranog obima, najveću površinu ima kvadrat. Neka je obim pravougaonika jednak \(2(x + y) = 2s\). Njegova površina jednaka je \(x\cdot y = x \cdot (s - x) = x\cdot s - x\cdot x = s^2/4 - (x - s/2)^2\). Pošto je \((x - s/2)^2 \geq 0\), površina ne može biti veća od \(s^2/4\), a jednaka je toj vrednosti kada je \(x = y = s/2\). Dakle, u zadatom problemu, uvećanje treba napraviti tako da se dobije oblik koji je što sličniji kvadratu (dobijanje kvadrata u nekim slučajevima nije moguće).
Neka je \(a \leq b\). Ako je \(a + c \leq b\), tada celokupan iznos uvećanja \(c\) treba dodati na manju stranicu \(a\). U suprotnom, prvo se kraća stranica \(a\) produži tako da postane jednaka dužoj stranici \(b\), a zatim se preostali iznos uvećanja (\(c - (b - a)\)) podeli što ravnomernije moguće (ako je to paran broj može se dobiti kvadrat, a ako nije, tada se dobija pravougaonik kod kojeg je jedna stranica za jedan duža od druge). U implementaciji dužine novih stranica možemo izračunati tako što dužu stranicu \(b\) uvećamo za \(\left\lfloor{\frac{c - (b - a)}{2}}\right\rfloor\) i za \(\left\lceil{\frac{c - (b - a)}{2}}\right\rceil = \left\lfloor{\frac{c - (b - a) + 1}{2}}\right\rfloor\).
long long maksPovrsina(long long a, long long b, long long c) {
if (a > b) swap(a, b);
if (c <= b - a)
a += c;
else {
long long preostalo = c - (b - a);
a = b + preostalo / 2;
b = b + (preostalo + 1) / 2;
}
return a*b;
}#include <iostream>
#include <algorithm>
using namespace std;
long long maksPovrsina(long long a, long long b, long long c) {
if (a > b) swap(a, b);
if (c <= b - a)
a += c;
else {
long long preostalo = c - (b - a);
a = b + preostalo / 2;
b = b + (preostalo + 1) / 2;
}
return a*b;
}
int main() {
long long a, b, c;
cin >> a >> b >> c;
cout << maksimalnaPovrsina(a, b, c) << endl;
return 0;
}Složenost ovog rešenja je \(O(1)\).
Primetimo da smo u ovom optimizacionom problemu uspeli da damo preciznu matematičku karakterizaciju traženog maksimuma (što je bilo moguće jer je funkcija koja se optimizovala bila jednostavna, u ovom slučaju - kvadratna) i time izbegli iterativnu pretragu. Generalno, kada se rešavaju optimizacioni problemi uvek ima smisla razmisliti da li je funkcija koja se optimizuje možda takva da se maksimum može izračunati matematičkim metodama da bi se u potpunosti izbegla pretraga ili bar okarakterisati na neki način koji omogućava da se značajno redukuje broj kandidata koje treba proveriti.
Brojevi od 0 do \(n^2 - 1\) ređaju se u kvadrat. Na primer, za \(n=5\) dobija se sledeći kvadrat:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Napiši program koji izračunava zbir brojeva u datoj vrsti i datoj koloni kvadrata (i njih ćemo brojati od nule).
Sa standardnog ulaza učitavaju se sledeći celi brojevi (svaki u posebnom redu).
Na standardni izlaz ispisati dva cela broja, svaki u posebnom redu:
Ako su ovi zbirovi veći ili jednaki od \(10^9\), ispisati njihovih poslednjih 9 cifara.
5 1
35 55
Rešenje se može dobiti upotrebom petlji i algoritma za sabiranje serije brojeva, pri čemu je svako sabiranje potrebno vršiti po modulu \(10^9\) (da ne bi došlo do prekoračenja i da bi se kod velikih brojeva dobilo samo poslednjih 9 cifara).
Početak vrste \(i\) izračunavamo tako što broj \(n\) saberemo \(i\) puta (početak svake naredne vrste veći je za \(n\) od prethodne, dok prva vrsta počinje nulom). Naravno, jasno je da će se dobiti vrednost \(i\cdot n\), pa bi ova petlja lako mogla da se izbegne. Zbir vrste izračunavamo tako što sabiramo jedan po jedan element te vrste, pri čemu je svaki element za jedan veći od prethodnog (ako je početak vrste \(p\), sabiramo brojeve \(p\), \(p+1\), , \(p+n-1\)).
Prvi element kolone sa rednim brojem \(i\) je \(i\). Svaki naredni element te kolone za \(n\) je veći od prethodnog. Na taj način izračunavamo svih \(n\) elemenata te kolone, dodajući ih jedan po jedan na zbir.
Složenost iterativnog algoritma za izračunavanje zbira svake vrste i svake kolone je \(O(n)\).
typedef long long ll;
int main() {
ll n, i;
cin >> n >> i;
const ll MOD = 1e9;
ll pocetakVrste = 0;
for (ll k = 0; k < i; k++)
pocetakVrste = (pocetakVrste + n) % MOD;
ll zbirVrste = 0;
for (int k = pocetakVrste; k < pocetakVrste + n; k++)
zbirVrste = (zbirVrste + k) % MOD;
cout << zbirVrste << endl;
ll elementKolone = i;
ll zbirKolone = i;
for (ll k = 1; k < n; k++) {
elementKolone = (elementKolone + n) % MOD;
zbirKolone = (zbirKolone + elementKolone) % MOD;
}
cout << zbirKolone << endl;
return 0;
}#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ll n, i;
cin >> n >> i;
const ll MOD = 1e9;
ll pocetakVrste = 0;
for (ll k = 0; k < i; k++)
pocetakVrste = (pocetakVrste + n) % MOD;
ll zbirVrste = 0;
for (int k = pocetakVrste; k < pocetakVrste + n; k++)
zbirVrste = (zbirVrste + k) % MOD;
cout << zbirVrste << endl;
ll elementKolone = i;
ll zbirKolone = i;
for (ll k = 1; k < n; k++) {
elementKolone = (elementKolone + n) % MOD;
zbirKolone = (zbirKolone + elementKolone) % MOD;
}
cout << zbirKolone << endl;
return 0;
}Kvadrat sadrži sledeće brojeve:
\[ \begin{array}{cccccc} 0 & 1 & \ldots & i & \ldots & n-1\\ n & n+1 & \ldots & n+i & \ldots & n + n-1\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ i\cdot n & i\cdot n+1 & \ldots & i\cdot n+i & \ldots & i\cdot n + n-1\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ (n-1)\cdot n & (n-1)\cdot n + 1 & \ldots & (n-1)\cdot n + i & \ldots & (n-1)\cdot n + n-1 \end{array} \]
Elementi \(i\)-te vrste čine aritmetički niz. Prvi član je \(a_1 = i\cdot n\), a razlika između susedna dva člana \(d = 1\). Primenom formule za zbir \(n\) elemenata aritmetičkog niza \(S_n = a_1 + \ldots + a_n = n\cdot a_1 + d\cdot\frac{n(n-1)}{2}\) dobijamo da je zbir elemenata u \(i\)-toj vrsti jednak
\[i\cdot n^2 + \frac{n(n-1)}{2}.\]
Slično, elementi \(i\)-te koloni takođe čine aritmetički niz u kome je prvi član \(a_0=i\), a razlika između susedna dva člana jednaka je \(n\). Zato je njen zbir jednak
\[n\cdot i + n\cdot \frac{n(n-1)}{2}.\]
Pošto je bar jedan od brojeva \(n\) ili \(n-1\) paran, rezultat je uvek ceo broj i moguće je sve operacije izvoditi nad celim brojevima (uključujući i celobrojno deljenje sa 2). Implementaciju je moguće napraviti direktno na osnovu ovih formula, vodeći računa o tome da se sve operacije izvode po modulu \(10^9\), da ne bi došlo do prekoračenja i da bi se odredilo poslednjih 9 cifara dužih brojeva.
Složenost ovog programa je, jasno, \(O(1)\). U implementaciji bi mogao biti smanjen broj primene izračunavanja ostatka (ovo je skupa operacija), međutim, pošto se ona primenjuje samo konstantan broj puta, time se ne bi dobilo značajno ubrzanje, a kod bi postao teže razumljiv i lakše bi moglo doći do greške.
typedef long long ll;
const long long MOD = 1e9;
ll pm(ll a, ll b) {
return ((a % MOD) * (b % MOD)) % MOD;
}
ll pm(ll a, ll b, ll c) {
return pm(pm(a, b), c);
}
ll zm(ll a, ll b) {
return (a % MOD + b % MOD) % MOD;
}
int main() {
ll n, i;
cin >> n >> i;
// i*n*n + n*(n-1)/2
ll zbirVrste =
zm(pm(i, n, n), n%2 == 0 ? pm(n/2, n-1) : pm(n, (n-1)/2));
cout << zbirVrste << endl;
// n*i + n*n*(n-1)/2
ll zbirKolone =
zm(pm(n, i), n%2 == 0 ? pm(n/2, n, n-1) : pm(n, n, (n-1)/2));
cout << zbirKolone << endl;
return 0;
}#include <iostream>
using namespace std;
typedef long long ll;
const long long MOD = 1e9;
ll pm(ll a, ll b) {
return ((a % MOD) * (b % MOD)) % MOD;
}
ll pm(ll a, ll b, ll c) {
return pm(pm(a, b), c);
}
ll zm(ll a, ll b) {
return (a % MOD + b % MOD) % MOD;
}
int main() {
ll n, i;
cin >> n >> i;
// i*n*n + n*(n-1)/2
ll zbirVrste =
zm(pm(i, n, n), n%2 == 0 ? pm(n/2, n-1) : pm(n, (n-1)/2));
cout << zbirVrste << endl;
// n*i + n*n*(n-1)/2
ll zbirKolone =
zm(pm(n, i), n%2 == 0 ? pm(n/2, n, n-1) : pm(n, n, (n-1)/2));
cout << zbirKolone << endl;
return 0;
}Moguće je i definisati funkciju za izračunavanje zbira elemenata aritmetičkog niza i dva puta je upotrebiti. I u ovom rešenju je potrebno sve aritmetičke operacije izvoditi po modulu \(10^9\).
ll sumaAritmetickog(ll a, ll d, ll n) {
// n*a + d*n*(n-1)/2
return zm(pm(n, a),
n%2 == 0 ? pm(d, n/2, n-1) : pm(d, n, (n-1)/2));
}
int main() {
ll n, i;
cin >> n >> i;
cout << sumaAritmetickog(i*n, 1, n) << endl;
cout << sumaAritmetickog(i, n, n) << endl;
return 0;
}#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1e9;
ll pm(ll a, ll b) {
return ((a % MOD) * (b % MOD)) % MOD;
}
ll pm(ll a, ll b, ll c) {
return pm(pm(a, b), c);
}
ll zm(ll a, ll b) {
return (a % MOD + b % MOD) % MOD;
}
ll sumaAritmetickog(ll a, ll d, ll n) {
// n*a + d*n*(n-1)/2
return zm(pm(n, a),
n%2 == 0 ? pm(d, n/2, n-1) : pm(d, n, (n-1)/2));
}
int main() {
ll n, i;
cin >> n >> i;
cout << sumaAritmetickog(i*n, 1, n) << endl;
cout << sumaAritmetickog(i, n, n) << endl;
return 0;
}Napiši program koji određuje na koliko se načina dati prirodni broj \(n\) može predstaviti kao zbir dva ili više uzastopnih prirodnih brojeva (većih ili jednakih 1).
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 10^9\)).
Na standardni izlaz ispisati traženi broj načina.
15
3
Važi: \(15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8.\)
Prvi pokušaj može biti rešavanje problema grubom silom, tj. isprobavanje svih mogućih prvih članova zbira. Najmanji mogući prvi član je \(a_0 = 1\). Pošto zbir mora da bude bar dvočlan, najveći mogući prvi član je onaj broj \(a_0\) takav da je \(a_0 + (a_0 + 1) \leq n\). Kada smo odredili prvi član, određujemo koliko sabiraka treba uzeti da bi se dobio zbir \(n\). Krećemo od dvočlanog niza i zatim dodajemo jedan po jedan naredni sabirak sve dok zbir ne dostigne ili ne prestigne zbir \(n\). Brojač uvećavamo ako je nakon petlje zbir jednak vrednosti \(n\) (tada je uspešno nađeno jedno rešenje).
int brojNacina(int n) {
int broj = 0;
for (int a0 = 1; a0 + (a0+1) <= n; a0++) {
int zbir = a0 + (a0+1);
for (int ai = a0 + 2; zbir < n; ai++)
zbir += ai;
if (zbir == n)
broj++;
}
return broj;
}#include <iostream>
using namespace std;
int brojNacina(int n) {
int broj = 0;
for (int a0 = 1; a0 + (a0+1) <= n; a0++) {
int zbir = a0 + (a0+1);
for (int ai = a0 + 2; zbir < n; ai++)
zbir += ai;
if (zbir == n)
broj++;
}
return broj;
}
int main() {
int n;
cin >> n;
cout << brojNacina(n) << endl;
return 0;
}Spoljašnja petlja se izvršava oko \(\frac{n}{2}\) puta. Broj izvršavanja unutrašnje petlje je teže proceniti. Pitamo se koji je broj sabiraka \(m\) potreban, tako da je \(a_0 + (a_0 + 1) + \ldots + (a_0 + (m-1)) \geq n\). Ako primenimo formulu za zbir aritmetičkog niza, vidimo da je taj zbir jednak \(m \cdot a_0 + \frac{m(m-1)}{2}\). Veoma gruba procena kada je \(a_0\) malo daje nam procenu za \(m\) oko \(\sqrt{2n}\). Mada, čim \(a_0\) krene da raste, ovaj broj krene da opada. Veoma grubo, složenost možemo ograničiti odozgo kao \(O(n \sqrt{n})\).
Redosled petlji može biti drugačiji. Spoljašnjom petljom možemo određivati broj sabiraka \(m\), a unutrašnjom isprobavati vrednosti početnog sabirka. Krećemo od dva sabirka. Najveći mogući broj sabiraka nastupa kada je \(a_0 = 1\), i pošto je \(a_0 + (a_0 + 1) + \ldots + (a_0 + (m-1)) = m \cdot a_0 + \frac{m(m-1)}{2}\), da bi zbir mogao da eventualno bude \(n\) mora da važi da je \(m + \frac{m(m-1)}{2} \leq n\).
int brojNacina(int n) {
int broj = 0;
for (int m = 2; m + m*(m-1)/2 <= n; m++) {
int a0 = 1;
int zbir = a0*m + m*(m-1)/2;
while (zbir < n) {
a0++;
zbir = a0*m + m*(m-1)/2;
}
if (zbir == n)
broj++;
}
return broj;
}#include <iostream>
using namespace std;
int brojNacina(int n) {
int broj = 0;
for (int m = 2; m + m*(m-1)/2 <= n; m++) {
int a0 = 1;
int zbir = a0*m + m*(m-1)/2;
while (zbir < n) {
a0++;
zbir = a0*m + m*(m-1)/2;
}
if (zbir == n)
broj++;
}
return broj;
}
int main() {
int n;
cin >> n;
cout << brojNacina(n) << endl;
return 0;
}Složenost je identična kao u prethodnom pristupu i može se grubo proceniti sa \(O(n \sqrt{n})\).
Ključna optimizacija nastupa kada uvidimo da nam unutrašnja petlja nije potrebna. Naime, nema potrebe isprobavati različite vrednosti \(a_0\), već se \(a_0\) može izračunati na osnovu \(m\) i \(n\). Ako je \(m \cdot a_0 + \frac{m(m-1)}{2} = n\), tada je \(a_0 = \frac{n - \frac{m(m-1)}{2}}{m}\). Zbir sa \(m\) sabiraka postoji ako i samo ako je ovo ceo broj (što se može proveriti ispitivanjem ostatka pri deljenju brojeva \(n - \frac{m(m-1)}{2}\) i \(m\)). Uslov \(m + \frac{m(m-1)}{2} \leq n\) garantuje da je \(a_0 \geq 1\).
int brojNacina(int n) {
int broj = 0;
for (int m = 2; m + m*(m-1)/2 <= n; m++)
if ((n - m*(m-1)/2) % m == 0)
broj++;
return broj;
}#include <iostream>
using namespace std;
int brojNacina(int n) {
int broj = 0;
for (int m = 2; m + m*(m-1)/2 <= n; m++)
if ((n - m*(m-1)/2) % m == 0)
broj++;
return broj;
}
int main() {
int n;
cin >> n;
cout << brojNacina(n) << endl;
return 0;
}Složenost jedine petlje, pa i celog programa se može grubo oceniti sa \(O(\sqrt{n})\) (u njenom telu se provera postojanja broja \(a_0\) vrši u složenosti \(O(1)\)).
Primetimo da se nakon primene formule za zbir aritmetičkog niza zadatak sveo na pronalaženje celobrojnih rešenja jedne jednačine sa dve nepoznate (\(a_0\) i \(m\))
\[m\cdot a_0 + \frac{m(m-1)}{2} = n.\]
Pošto broj celobrojnih rešenja ne možemo unapred odrediti, koristimo iterativni postupak da proverimo razne kandidate.
Do efikasnog rešenja ovog zadatka smo došli tako što smo umesto provere raznih parova vrednosti, uvideli da se nakon fiksiranja jedne vrednosti ona druga može eksplicitno izračunati. Redosled provera je veoma važan, jer je jednačina linearna po \(a_0\), a kvadratna po \(m\), tako da je za fiksirano \(m\), \(a_0\) prilično jednostavno izračunati, dok za fiksirano \(a_0\) nije jednostavno izračunati \(m\). Dakle, u ovom zadatku vidimo odličan spoj računarskog i matematičkog pristupa: pošto jednačinu sa dve promenljive ne možemo da rešimo matematički, koristimo iterativni postupak i isprobavamo razne vrednosti \(m\). Nakon toga dobija se jednačina koja se može rešiti matematički i tada izbegavamo korišćenje iterativnog postupka koji bi isprobavao razne vrednosti \(a_0\).
Jedan klasičan inkrementalni algoritam je Bresenhamov algoritam koji se koristi za crtanje pravih linija na ekranu koji se sastoji od piksela. Pretpostavimo da je koordinatni sistem postavljen tako da je širina svakog piksela 1 i da su pikseli postavljeni tako da im centri leže u tačkama sa celobrojnim koordinatama. Crtaćemo duž od piksela čiji je centar u tački \((x_0, y_0)\) do piksela čiji je centar u tački \((x_1, y_1)\). Razmatraćemo samo slučaj kada je \(x_0 < x_1\) i kada je nagib duži \(\Delta y / \Delta x\) manji od 1 (duž je “pretežno horizontalna”).
Razmotrimo Bresenhamov algoritam ilustrovan na slici 15.
Obrađivaćemo sve celobrojne koordinate od \(x_0\) do \(x_1\) i za svaku ćemo crtati tačno jedan piksel. Prvo se crta levi piksel sa centrom u \((x_0, y_0)\). Položaj svakog narednog piksela se određuje tako da taj naredni piksel bude ili na istoj visini sa trenutnim (horizontalni korak) ili na visini za jedan većoj (dijagonalni korak). Dva potencijalna piksela (ona levo i onaj gore levo) deli horizontalna prava čija je visina \(y_i + 1/2\) (duž gornje ivice tekućeg piksela). Koji od njih treba uzeti zavisi od toga da li tzv. središnja tačka \((x_i+1, y_i+1/2)\) leži ispod ili iznad duži koja spaja tačke \((x_0, y_0)\), kao što je ilustrovano na slici 15.
Koordinata u kojoj duž seče vertikalnu pravu \(x=x_i\) se može izračunati kao \(y_0 + \Delta y / \Delta x \cdot (x_i-x_0)\), ali pošto trenutna visina \(y_i\) zavisi od prethodnih piksela, nju ne možemo izračunati unapred nekom formulom. Stoga se algoritam prirodno izražava inkrementalno, tj. sav račun se organizuje tako da potrebne koordinate narednog piksela zavise samo od koordinata prethodnog piksela. Duž kreće od koordinate \((x_0, y_0)\) i u svakom koraku se desno pomeri za 1, a naviše za \(\Delta y / \Delta x\). Središnja tačka se inicijalno nalazi na \((x_0+1, y_0+1/2)\). U svakom koraku joj se \(x\)-koordinata povećava za 1, dok se \(y\)-koordinata ili ne menja (ako je napravljen horizontalni korak) ili se poveća za 1 (ako je napravljen dijagonalni korak).
Neka promenljiva \(p\) označava vertikalnu razliku između visine duži i visine središnje tačke. Inicijalno (za \(x=x_0+1\), gde se donosi prva odluka), je ta razlika jednaka \((y_0 + \Delta y / \Delta x) - (y_0 + 1/2)\) \(=\) \(\Delta y / \Delta x - 1/2\). Kako se ta razlika menja u svakom koraku?
Na taj način dobijamo naredni inkrementalni algoritam.
double dx = x1 - x0;
double dy = y1 - y0;
int x = x0; y = y0;
double p = dy/dx - 0.5;
while (x <= x1) {
// Ispis koordinata (zamjenjuje crtanje piksela)
std::cout << "(" << x << ", " << y << ")\n";
// Središnja tačka je ispod duži
if (p >= 0) {
// dijagonalni korak
y++;
// duž se podigne za dy/dx, a središnja tačka za 1
p = p + dy/dx - 1;
}
// Središnja tačka je iznad duži
else {
// horizontalni korak
// duž se podigne za dy/dx, a središnja tačka ostaje na istoj visini
p = p + dy/dx;
}
// Prelazimo na sledeći horizontalni piksel
x++;
}Važna optimizacija (konstantnog faktora) koju je Breseman primetio je da se umesto rada se realnim brojevima algoritam može sprovesti samo u celobrojnoj aritmetici. Pošto je vrednost \(\Delta x\) po našim pretpostavkama pozitivna, znak razlike \(p\) se ne menja ako se umesto razlike sve vreme razmatra razlika pomnožena vrednošću \(2\cdot \Delta x\). Pošto je inicijalno \(p=\Delta y/\Delta x + 1/2\), ovim množenjem dobijamo da je celobrojna razlika \(p' = 2\Delta x\cdot p = 2\Delta y - \Delta x\). I koraci ažuriranja se lako prilagođavaju (množenjem dodela u kojima se ažurira \(p\) sa \(2\Delta x\)). U dijagonalnom koraku se celobrojna razlika uvećava za \(2\Delta y - 2 \Delta x\), dok se u horizontalnom uvećava samo za \(2\Delta y\). Time se dobija efikasnija verzija.
int dx = x1 - x0;
int dy = y1 - y0;
int x = x0; y = y0;
int p = 2*dy - dx;
while (x <= x1) {
// Ispis koordinata (zamjenjuje crtanje piksela)
std::cout << "(" << x << ", " << y << ")\n";
// Središnja tačka ja iznad duži
if (p >= 0) {
y++;
p -= 2*dx;
}
// Prelazimo na sledeći piksel
x++;
p += 2*dy;
}U narednom apletu možete videti kako ovaj algoritam funkcioniše.
Pangrami su reči koje sadrže bar jedno pojavljivanje svakog slova abecede ili azbuke (slova se mogu pojavljivati i više puta). Čuveni pangram u engleskom jeziku je niska "the quick brown fox jumps over a lazy dog". Napiši program koji proverava da li se u datom tekstu nalazi neki podtekst (niz uzastopnih karaktera) dužine \(k\) koji je pangram.
Prva linija standardnog ulaza sadrži nisku sastavljenu samo od malih slova engleske abecede, dužine najviše \(10^5\) karaktera. Naredni red sadrži prirodan broj \(k\) (\(1 \leq k \leq 10^5\)).
Na standardni izlaz ispisati da ako u unetom tekstu postoji pangram dužine \(k\), odnosno ne u suprotnom.
xxxabcdefghijklmnopqrstuvwxyzxxx 26
da
xxxabcdefghijklmxxxnopqrstuvwxyzxxx 28
ne
xxxabcdefghijklmxxxnopqrstuvwxyzxxx 29
da
Rešenje grubom silom podrazumeva da se za svaku podnisku dužine \(k\) proveri da li sadrži sve karaktere abecede. Za svaku podnisku i svako slovo abecede možemo linearnom pretragom utvrditi da li podniska sadrži to slovo (linearna pretraga može biti realizovana bilo bibliotečkom funkcijom, bilo ručno implementirana). Ako su sva slova pronađena, podniska je pangram i tada možemo prekinuti dalju analizu, dok u suprotnom prelazimo na analizu naredne podniske.
Provera da li je podniska pangram zahteva 26 linearnih pretraga dužine \(k\). U principu, možemo smatrati da je složenost \(O(k)\), iako je konstanta 26 prilično velika. Podniski ima ukupno \(n-k\), pa u najgorem slučaju (kada je \(k\) oko pola dužine niza), dobijamo algoritam kvadratne složenosti \(O(n^2)\).
// provera da li dati tekst sadrzi pangram duzine k
bool sadrzi_pangram(const string& tekst, int k) {
// proveravamo sve podniske duzine k
for (int i = 0; i + k < tekst.length(); i++) {
// da li je podniska pangram
bool pangram = true;
// proveravamo da li podniska [i, i+k) sadrzi sva slova
for (char c = 'a'; c <= 'z'; c++) {
bool sadrzi = false;
for (int j = i; j < i + k; j++)
if (tekst[j] == c) {
sadrzi = true;
break;
}
// ako nema nekog slova, podniska nije pangram
if (!sadrzi) {
pangram = false;
break;
}
}
// sva slova su pronadjena, podniska jeste pangram
if (pangram)
return true;
}
return false;
}#include <iostream>
#include <set>
using namespace std;
// provera da li dati tekst sadrzi pangram duzine k
bool sadrzi_pangram(const string& tekst, int k) {
// proveravamo sve podniske duzine k
for (int i = 0; i + k < tekst.length(); i++) {
// da li je podniska pangram
bool pangram = true;
// proveravamo da li podniska [i, i+k) sadrzi sva slova
for (char c = 'a'; c <= 'z'; c++) {
bool sadrzi = false;
for (int j = i; j < i + k; j++)
if (tekst[j] == c) {
sadrzi = true;
break;
}
// ako nema nekog slova, podniska nije pangram
if (!sadrzi) {
pangram = false;
break;
}
}
// sva slova su pronadjena, podniska jeste pangram
if (pangram)
return true;
}
return false;
}
int main() {
string tekst;
cin >> tekst;
int k;
cin >> k;
cout << (sadrzi_pangram(tekst, k) ? "da" : "ne") << endl;
return 0;
}Efikasnije rešenje možemo dobiti zahvaljujući principu inkrementalnosti. Da bismo proverili da li je neka reč pangram, dovoljno je da znamo skup karaktera koji se u njoj javljaju i da proverimo da li taj skup sadrži 26 elemenata. Prilikom prelaska sa jedne na drugu podnisku, većina karaktera se poklapa. Razlikuju se samo prvi karakter prve podniske i poslednji karakter druge podniske. Zato prilikom prelaska sa podniske na podnisku treba iz skupa ukloniti prvi, a dodati poslednji karakter. Međutim, pošto se karakteri javljaju više puta, ovo može biti pogrešno, pa zapravo umesto skupova treba razmatrati multiskupove. Najjednostavniji način je da uvedemo preslikavanje koje svakom karakteru dodeljuje njegov broj pojavljivanja u podniski (ono može biti realizovano pomoću niza brojača ili, jednostavnije, preko mape tj. rečnika). Prilikom prelaska na narednu podnisku umanjujemo brojač prvog karaktera (i ako dostigne nulu, uklanjamo ga iz mape) i uvećavamo brojač poslednjeg karaktera. Nakon toga, proveravamo da li je broj karaktera u mapi jednak 26 i ako jeste, tekuća podniska predstavlja pangram.
Pošto se u svakom trenutku održavaju podaci o nekom segmentu originalnog niza kraktera dužine \(k\) i taj segment se polako pomera sleva nadesno, nekada se kaže da se primenjuje tehnika pokretnog prozora i taj prozor se ažurira inkrementalno.
U petlji se analizira svaki karakter niske. Ako pretpostavimo da su operacije sa mapom tj. rečnikom konstantne složenosti (što je prilično opravdano, jer postoji samo 26 različitih ključeva), složenost celog algoritma se može oceniti sa \(O(n)\), gde je \(n\) dužina niske koja se proverava.
// provera da li dati tekst sadrzi pangram duzine k
bool sadrzi_pangram(const string& tekst, int k) {
// broj pojavljivanja karaktera u trenutnoj podniski duzine k
map<char, int> karakteri;
// prolazimo sve karaktere u tekstu
for (int i = 0; i < tekst.length(); i++) {
// prelazimo na narednu podnisku,
// inkrementalno azurirajuci njen broj karaktera
if (i >= k)
// izbacujemo karakter na poziciji i-k
if (--karakteri[tekst[i-k]] == 0)
karakteri.erase(tekst[i-k]);
// dodajemo karakter na poziciji i
karakteri[tekst[i]]++;
// ako se svi karakteri javljaju, pangram je pronadjen
if (karakteri.size() == 26)
return true;
}
return false;
}#include <iostream>
#include <map>
using namespace std;
// provera da li dati tekst sadrzi pangram duzine k
bool sadrzi_pangram(const string& tekst, int k) {
// broj pojavljivanja karaktera u trenutnoj podniski duzine k
map<char, int> karakteri;
// prolazimo sve karaktere u tekstu
for (int i = 0; i < tekst.length(); i++) {
// prelazimo na narednu podnisku,
// inkrementalno azurirajuci njen broj karaktera
if (i >= k)
// izbacujemo karakter na poziciji i-k
if (--karakteri[tekst[i-k]] == 0)
karakteri.erase(tekst[i-k]);
// dodajemo karakter na poziciji i
karakteri[tekst[i]]++;
// ako se svi karakteri javljaju, pangram je pronadjen
if (karakteri.size() == 26)
return true;
}
return false;
}
int main() {
string tekst;
cin >> tekst;
int k;
cin >> k;
cout << (sadrzi_pangram(tekst, k) ? "da" : "ne") << endl;
return 0;
}Neki blokovi memorije su zauzeti, a neki slobodni. Da bi se u memoriju mogao smestiti dugačak niz podataka, potrebno je pronaći što duži niz uzastopnih slobodnih blokova.
Sa standardnog ulaza se unosi prirodan broj \(N\) (\(5 \leq N \leq 50000\)), a zatim i \(N\) brojeva 1 (što označava da je blok zauzet) ili 0 (što označava da je blok slobodan).
Na standardni izlaz ispisati jedan prirodan broj koji predstavlja traženu dužinu najduže serije uzastopnih slobodnih blokova.
8 0 0 1 0 0 0 1 1
3
Zadatak zahteva da se odredi dužina najduže serije uzastopnih nula.
U naivnom pristupu rešavanju ovog problema ulazni podaci se smeštaju i čuvaju u nizu. To nije neophodno, ali ćemo najpre prikazati i takva rešenja, da bismo sistematično ilustrovali neke tehnike postupne optimizacije koda.
Jedno veoma naivno rešenje je da analiziramo sve moguće segmente niza određene svim mogućim vrednostima promenljivih \(0 \leq i \leq j < n\). Njih možemo nabrojati ugnežđenim petljama. Za svaki segment možemo primenom linearne pretrage proveriti da li sadrži samo nule i ako sadrži, ažurirati maksimum u skladu sa tim.
// izracunava duzinu najduze serije uzastopnih nula
int najduzaSerijaNula(const vector<int>& a) {
// broj podataka
int N = a.size();
// duzina najduze serije uzastopnih nula
int maxDuzina = 0;
// analiziramo sve segmente a[i, j]
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
// proveravamo da li su u segmentu a[i, j] samo nule
bool samo_nule = true;
for (int k = i; k <= j; k++)
if (a[k] != 0) {
samo_nule = false;
break;
}
// ako jesu, azuriramo maksimum u odnosu na duzinu
// segmenta [i, j]
if (samo_nule)
maxDuzina = max(maxDuzina, j - i + 1);
}
}
return maxDuzina;
}#include <iostream>
#include <vector>
using namespace std;
// izracunava duzinu najduze serije uzastopnih nula
int najduzaSerijaNula(const vector<int>& a) {
// broj podataka
int N = a.size();
// duzina najduze serije uzastopnih nula
int maxDuzina = 0;
// analiziramo sve segmente a[i, j]
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
// proveravamo da li su u segmentu a[i, j] samo nule
bool samo_nule = true;
for (int k = i; k <= j; k++)
if (a[k] != 0) {
samo_nule = false;
break;
}
// ako jesu, azuriramo maksimum u odnosu na duzinu
// segmenta [i, j]
if (samo_nule)
maxDuzina = max(maxDuzina, j - i + 1);
}
}
return maxDuzina;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo sve podatke u niz
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++)
cin >> a[i];
// ispisujemo duzinu najduze serije uzastopnih nula
cout << najduzaSerijaNula(a) << endl;
}Pošto se podaci smeštaju u pomoćni niz, memorijska složenost je \(O(n)\). Ovo rešenje je izrazito neefikasno, jer mu je vremenska složenost čak kubna tj. \(O(n^3)\). Sa druge strane korektnost ovog rešenja je zaista trivijalno obrazložiti (ono se potpuno direktno izvodi iz same formulacije zadatka).
Malo bolji pristup je da za svaku poziciju \(i\) odredimo najdužu seriju uzastopnih nula koja počinje na toj poziciji. To se može uraditi tako što se serija koji počinje na poziciji \(i\) proširuje od pozicije \(i\) nadesno, sve dok se u njoj nalaze samo nule. Važna ušteda na ovom mestu je to što ako znamo da su u segmentu \([i, j]\) sve nule i da se nula nalazi i na poziciji \(j+1\), onda znamo i da su sve nule i u segmentu \([i, j+1]\) (kažemo da proveru vršimo inkrementalno).
Kada se naiđe na broj različit od nule (ili na kraj niza), nađena je najduža serija uzastopnih nula koja počinje na poziciji \(i\), jer će sva produžavanja te serije nadesno, ako ih ima, sadržati i ovu vrednost različitu od nule. Dakle, na ovom mestu vršimo odsecanje pretrage preskačući mnoge segmente niza za koje se unapred zna da ne mogu zadovoljiti nametnuti uslov. Takođe, poređenje sa maksimalnom dužinom vršimo tek kada maksimalno proširimo tekući segment, jer unapred znamo da su svi podsegmenti tog maksimalno proširenog segmenta kraći od njega (i ovde zapravo vršimo određeno odsecanje).
// izracunava duzinu najduze serije uzastopnih nula
int najduzaSerijaNula(const vector<int>& a) {
// broj podataka
int N = a.size();
// duzina najduze serije uzastopnih nula
int maxDuzina = 0;
// za svaku poziciju i odredjujemo duzinu najduze serije
// uzastopnih nula koja pocinje na poziciji i
for (int i = 0; i < N; i++) {
int duzina = 0;
for (int j = i; j < N && a[j] == 0; j++)
duzina++;
// ako je duzina serije koja pocinje na poziciji i veca od
// maksimalne do tada vidjene duzine, azuriramo maksimalnu
// duzinu
if (duzina > maxDuzina)
maxDuzina = duzina;
}
return maxDuzina;
}#include <iostream>
#include <vector>
using namespace std;
// izracunava duzinu najduze serije uzastopnih nula
int najduzaSerijaNula(const vector<int>& a) {
// broj podataka
int N = a.size();
// duzina najduze serije uzastopnih nula
int maxDuzina = 0;
// za svaku poziciju i odredjujemo duzinu najduze serije
// uzastopnih nula koja pocinje na poziciji i
for (int i = 0; i < N; i++) {
int duzina = 0;
for (int j = i; j < N && a[j] == 0; j++)
duzina++;
// ako je duzina serije koja pocinje na poziciji i veca od
// maksimalne do tada vidjene duzine, azuriramo maksimalnu
// duzinu
if (duzina > maxDuzina)
maxDuzina = duzina;
}
return maxDuzina;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo sve podatke u niz
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++)
cin >> a[i];
// ispisujemo duzinu najduze seriju uzastopnih nula
cout << najduzaSerijaNula(a) << endl;
}Ovo rešenje je složenosti \(O(n^2)\), što je bolje od prvog, međutim i dalje suboptimalno. Pošto se podaci smeštaju u pomoćni niz, memorijska složenost je \(O(n)\).
Program se može dodatno značajno ubrzati daljim odsecanjem. Jednom kada odredimo da je najduži segment koji sadrži uzastopne nule i počinje na poziciji \(i\) segment \([i, j]\), vreme značajno možemo uštedeti tako što primetimo da ni jedan segment koji sadrži uzastopne nule i počinje na pozicijama nakon \(i\), a zaključno sa \(j\) ne može biti duži od segmenta koji počinje sa \(i\) (jer ako pozicija \(j\) nije poslednja u nizu, na poziciji iza nje se ne nalazi nula i ti segmenti se ne mogu proširiti dalje od pozicije \(j\)). Zato je nakon širenja segmenta koji počinje na poziciji \(i\) nadesno i određivanja serije nula koja počinje na poziciji \(i\) moguće direktno preći na izračunavanje najdužeg segmenta uzastopnih nula koji počinje na poziciji \(j+1\) (ako takva postoji). Ovo zapravo odgovara tome da ceo niz izdelimo na segmente uzastopnih nula koji se nadovezuju (presečeni segmentima uzastopnih jedinica). Složenost takvog pristupa je \(O(n)\), jer se granice segmenata samo uvećavaju i nikada ne smanjuju.
Ovaj algoritam je zapravo i vrlo intuitivan i verovatno je prvi algoritam koji bi programer sa malo iskustva implementirao: krećemo od početka, pronalazimo seriju uzastopnih nula koji počinje na početku, nakon toga tražimo seriju uzastopnih nula nakon te prve serije, zatim seriju uzastopnih nula nakon te druge i tako dalje. Dakle, ceo niz delimo na manje segmente koji sadrže jednake elemente i nadovezuju se jedan iza drugog, pri čemu je podela takva da je svaki od tih segmenata optimalan u smislu da ga nije moguće produžiti (ni na levo, ni na desno).
Možemo primetiti da nam tokom implementacije nije više neophodno da pamtimo sve rezultate u nizu istovremeno. U jednoj petlji ćemo čitati redom elemente niza i u svakom trenutku održavati dužinu tekuće i dužinu najduže do tada obrađene serije (segmenta) uzastopnih nula. Pošto na početku nismo videli još ni jedan element niza, obe promenljive inicijalizujemo na nulu. Ako učitamo nulu, tada se tekuća seriju uzastopnih nula produžava i njenu dužinu uvećavamo za jedan. Ako nije nula, tada se tekuća serija prekida i započinje nova, koja ima dužinu 0 (jer je za sada prazna i ne sadrži ni jednu nulu).
Nakon završetka čitanja svake serije uzastopnih nula potrebno je ažurirati dužinu najduže serije. To se dešava ili kada se naiđe na podatak različit od nule ili nakon petlje, kada je poslednja eventualna serija nula završena. Treba biti veoma obazriv da se ne zaboravi na poslednju seriju, tj. da se ne zaboravi poređenje tekuće i najduže serije nakon završetka petlje. Alternativa je da se maksimum ažurira prilikom svakog uvećanja dužine tekuće serije uzastopnih nula (na taj način se zapravo određuje dužina najduže serije uzastopnih nula koja se završava na tekućoj poziciji).
// broj blokova
int N;
cin >> N;
// duzina tekuce serije uzastopnih nula
int duzinaTekuce = 0;
// duzina najduze do sada vidjene serije uzastopnih nula
int duzinaNajduze = 0;
// ucitavamo podatke
for (int i = 0; i < N; i++) {
// naredni broj
int x;
cin >> x;
if (x == 0) {
// nula produzava tekucu seriju
duzinaTekuce++;
} else {
// ako je upravo prekinuta serija duza od najduze,
// azuriramo duzinu najduze
if (duzinaTekuce > duzinaNajduze)
duzinaNajduze = duzinaTekuce;
// broj razlicit od nule prekida seriju i zapocinje se nova
// u kojoj jos ne postoji nijedna nula
duzinaTekuce = 0;
}
}
// vrsimo proveru i za poslednju seriju
if (duzinaTekuce > duzinaNajduze)
duzinaNajduze = duzinaTekuce;
// ispisujemo konacan rezultat
cout << duzinaNajduze << endl;#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
// broj blokova
int N;
cin >> N;
// duzina tekuce serije uzastopnih nula
int duzinaTekuce = 0;
// duzina najduze do sada vidjene serije uzastopnih nula
int duzinaNajduze = 0;
// ucitavamo podatke
for (int i = 0; i < N; i++) {
// naredni broj
int x;
cin >> x;
if (x == 0) {
// nula produzava tekucu seriju
duzinaTekuce++;
} else {
// ako je upravo prekinuta serija duza od najduze,
// azuriramo duzinu najduze
if (duzinaTekuce > duzinaNajduze)
duzinaNajduze = duzinaTekuce;
// broj razlicit od nule prekida seriju i zapocinje se nova
// u kojoj jos ne postoji nijedna nula
duzinaTekuce = 0;
}
}
// vrsimo proveru i za poslednju seriju
if (duzinaTekuce > duzinaNajduze)
duzinaNajduze = duzinaTekuce;
// ispisujemo konacan rezultat
cout << duzinaNajduze << endl;
return 0;
}Složenost ovog algoritma je \(O(n)\). Memorijska složenost je \(O(1)\).
Dat je niz \(a\) celih brojeva, dužine \(n\). Napisati program kojim se određuje na koliko načina možemo izabrati rastuće segmente u nizu. Rastući segment čine uzastopni elementi niza \(a_p < a_{p+1} < \ldots < a_q\), za \(0 \leq p < q < n\).
Prva linija standardnog ulaza sadrži prirodan broj \(n\) (\(2 \leq n\leq 10000\)), broj elemenata niza. U svakoj od \(n\) narednih linija standardnog ulaza, nalazi po jedan član niza.
Na standardnom izlazu prikazati broj rastućih segmenata datog niza.
5 1 3 4 -2 10
4
To su segmenti \([1, 3]\), \([1, 3, 4]\), \([3, 4]\), \([-2, 10]\).
Zadatak možemo rešiti analizirajući sve segmente datog niza \(a\) i za svaki segment \(a_i, a_{i+1}, ..., a_j\) gde je \(0 \leq i < j < n\) proveriti da li je rastući i u skladu sa tim uvećati brojač rastućih segmenata. Pošto segmenata ima \(O(n^2)\) i svakom se provera monotonosti vrši u linearnoj složenosti, ovo rešenje je složenosti \(O(n^3)\) (naravno, nisu svi segmenti iste dužine i precizna analiza bi trebalo da u obzir uzme dužine svih segmenata, međutim, i na taj način bi se izračunalo da je algoritam kubne složenosti). Elementi su smešteni u niz, pa je memorijska složenost \(O(n)\).
Efikasnije rešenje se može dobiti ako se provera monotonosti vrši inkrementalno (da bi se proverilo da je segment \([i, j]\) rastući dovoljno je da je \(a_j > a_{j-1}\) i da je segment \([i, j-1]\) rastući ili jednočlan).
Vreme izvršavanja možemo unaprediti i odsecanjem. Primetimo da ako segment koji čine elementi na pozicijama \([i, j]\) nije rastući, onda nisu rastući ni segmenti \([i, j']\) za \(j \leq j' < n\), pa za te segmente ne treba vršiti proveru, što znači da je brojanje rastućih segmenata koji počinju na poziciji \(i\) moguće prekinuti čim se pronađe neki segment koji počinje na toj poziciji i nije rastući.
Dakle, za svaku poziciju \(i\) u nizu (za svako \(0 \leq i < n-1\)) analiziramo jedan po jedan segment \([i, j]\) koji na toj poziciji počinje sve dok su ti segmenti rastući i za svaki rastući segment uvećavamo brojač rastućih segmenata za 1. Čim naiđemo na segment koji nije rastući (tj. na element koji je manji od prethodnog), prelazimo na narednu poziciju \(i\).
Primer 3.A.1. Na primer u nizu \([1, 3, 4, 5, 2, 6]\) analiziramo segmente koji počinju prvim elementom niza tj. elementom \(a_0\) sve dok su segmenti rastući, pri tome prebrojimo rastuće segmente \([1, 3]\); \([1, 3, 4]\) i \([1, 3, 4, 5]\). Slično polazeći od drugog elementa niza prebrojimo rastuće segmente \([3, 4]\) i \([3, 4, 5]\). Nastavljajući isti postupak za ostale elemente niza prebrojimo i rastući segment \([4, 5]\), a zatim i \([2, 6]\).
Složenost ovog algoritma je \(O(n^2)\) i njime se najefikasnije moguće eksplicitno nabrajaju svi rastući segmenti. Memorijska složenost je \(O(n)\).
long long brojRastucihSegmenata(const vector<int>& a) {
// velicina niza
int n = a.size();
// ukupan broj rastucih serija
long long brojRastucih = 0;
// za svaku poziciju u nizu
for (int i = 0; i < n - 1; i++) {
// pronalazimo sve rastuce serije koje pocinju na toj
// poziciji
// proveru da li je serija odredjena pozicijama [i, j]
// rastuca odredjujemo inkrementalno
// postupak prekidamo cim se naidje na seriju koja nije
// rastuca
for (int j = i + 1; j < n; j++)
if (a[j] > a[j-1])
brojRastucih++;
else
break;
}
return brojRastucih;
}#include <iostream>
#include <vector>
using namespace std;
long long brojRastucihSegmenata(const vector<int>& a) {
// velicina niza
int n = a.size();
// ukupan broj rastucih serija
long long brojRastucih = 0;
// za svaku poziciju u nizu
for (int i = 0; i < n - 1; i++) {
// pronalazimo sve rastuce serije koje pocinju na toj
// poziciji
// proveru da li je serija odredjena pozicijama [i, j]
// rastuca odredjujemo inkrementalno
// postupak prekidamo cim se naidje na seriju koja nije
// rastuca
for (int j = i + 1; j < n; j++)
if (a[j] > a[j-1])
brojRastucih++;
else
break;
}
return brojRastucih;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
// ispisujemo ukupan broj rastucih serija
cout << brojRastucihSegmenata(a) << endl;
return 0;
}U prethodno rešenju se nabrajaju svi rastući segmenti, međutim, u zadatku je potrebno izračunati samo njihov broj (a ne i nabrojati ih eksplicitno), a to se može uraditi i efikasnije.
Primetimo da u prethodnom primeru analizirajući rastući segment koji počinje od elementa \(a_0\) prolazimo i po rastućim segmentima niza koji počinju sa \(a_1\) i \(a_2\). Ako je segment \([a_i, a_{i+1}, ..., a_{j}]\) rastući, onda unapred znamo da su rastući i segmenti \([a_i, a_{i+1}]\), \([a_i, a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{j}]\), zatim \([a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{j}]\), pa sve do \([a_{j-1}, a_j]\), a da segmenti \([a_i, a_{i+1}, \ldots, a_{j+1}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{n-1}]\), zatim \([a_{i+1}, a_{i+2}, \ldots, a_{j+1}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{n-1}]\) itd., zaključno sa \([a_{j}, \ldots, a_{n-1}]\) nisu rastući. Dakle, za svaku poziciju iz intervala \([i, j]\) tačno znamo sve rastuće segmente koji na njoj počinju.
Rastući segment \([a_i, a_{i+1}, \ldots, a_{i+k-1}]\) dužine \(k\) u sebi sadrži:
ukupno \((k-1) + (k-2) + ... + 1\) rastućih segmenata što iznosi \(\frac {k \cdot (k - 1)}{2}\).
Do istog zaključka možemo doći i na sledeći način: svaki podsegment \(a_p, a_{p+1}, \ldots, a_q\) gde je \(i \leq p < q \leq i+k-1\) rastućeg segmenta \(a_i, a_{i+1}, ..., a_{i+k-1}\) je rastući, početak \(p\) i kraj \(q\) podsegmenta možemo izabrati na \(\frac {k \cdot (k - 1)}{2}\) načina.
Dakle, potrebno je pronaći dužine maksimalnih rastućih segmenata (onih koji se ne mogu produžiti dodatnim elementom tako da i dalje ostaju rastući), a zatim broj njihovih rastućih podsegmenata umesto iteracijom, izračunati formulom. Naime, nakon nalaženja nekog maksimalnog rastućeg segmenta \([i, j]\), možemo neposretno da izračunamo broj rastućih segmenata koji počinju na svim pozicijama između \(i\) i \(j\).
Prema tome, u petlji analiziramo niz član po član počev od prvog člana (\(i = 0\)) i određujemo dužinu \(t\) tekućeg rastućeg segmenta (ako je \(a_i < a_{i+1}\) uvećavamo \(t\) za 1). Kada dođemo do kraja tekućeg rastućeg segmenta, uvećavamo ukupan broj rastućih segmenata \(br\) za \(\frac{t \cdot (t - 1)}{2}\) i počinjemo analizu sledećeg rastućeg segmenta (\(t = 1\)). Do kraja maksimalnog rastućeg segmenta se može stići na dva načina: ili kada je \(a_i \geq a_{i+1}\) ili kada se dođe do kraja niza. Napomenimo da za taj poslednji rastući segment uvećavamo ukupan broj rastućih segmenata izvan petlje (česta greška je da se to zaboravi).
U svakom trenutku je dovoljno porediti samo susedna člana niza, tako da nije neophodno ceo niz pamtiti u memoriji, već samo dva susedna člana niza (prethodni i tekući).
Na prethodno opisan način dobijamo rešenje jednim prolaskom po nizu i vremenska složenost mu je \(O(n)\). Memorijska složenost je \(O(1)\).
int n;
cin >> n;
int prethodni;
cin >> prethodni;
// ukupan broj rastucih serija
long long brojRastucih = 0;
// duzina tekuce rastuce serije
long long duzinaTekuceRastuce = 1;
for(int i = 1; i < n; i++) {
int tekuci;
cin >> tekuci;
if (tekuci > prethodni)
// tekuci element produzava tekucu rastucu seriju
duzinaTekuceRastuce++;
else {
// tekuci element zapocinje novu rastucu seriju
// dodajemo sve rastuce serije koje su podserije rastuce
// serije koja se zavrsila sa prethodnim elementom
brojRastucih += (duzinaTekuceRastuce - 1) *
duzinaTekuceRastuce / 2;
duzinaTekuceRastuce = 1;
}
prethodni = tekuci;
}
// dodajemo sve rastuce serije koje su podserije poslednje
// rastuce serije
brojRastucih += (duzinaTekuceRastuce - 1) *
duzinaTekuceRastuce / 2;
cout << brojRastucih << endl;#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
int prethodni;
cin >> prethodni;
// ukupan broj rastucih serija
long long brojRastucih = 0;
// duzina tekuce rastuce serije
long long duzinaTekuceRastuce = 1;
for(int i = 1; i < n; i++) {
int tekuci;
cin >> tekuci;
if (tekuci > prethodni)
// tekuci element produzava tekucu rastucu seriju
duzinaTekuceRastuce++;
else {
// tekuci element zapocinje novu rastucu seriju
// dodajemo sve rastuce serije koje su podserije rastuce
// serije koja se zavrsila sa prethodnim elementom
brojRastucih += (duzinaTekuceRastuce - 1) *
duzinaTekuceRastuce / 2;
duzinaTekuceRastuce = 1;
}
prethodni = tekuci;
}
// dodajemo sve rastuce serije koje su podserije poslednje
// rastuce serije
brojRastucih += (duzinaTekuceRastuce - 1) *
duzinaTekuceRastuce / 2;
cout << brojRastucih << endl;
return 0;
}Čuvena veb-platforma želi da napravi sistem za analizu posete svom veb-sajtu. Sakupljen je broj poseta tokom svakog minuta u prethodnih nekoliko godina (najviše \(10\)). Napisati program koji omogućava korisniku da za zadate vremenske raspone (određene minutima od početka brojanja) izračuna broj poseta tokom tih vremenskih raspona.
Sa standardnog ulaza se unosi broj minuta \(n\) (\(1 \leq n \leq 60\cdot 24\cdot 365\cdot 10\)), a zatim u narednom redu \(n\) celih brojeva između \(0\) i \(100\), razdvojenih sa po jednim razmakom, koji predstavljaju broj posetilaca tokom svakog od tih \(n\) minuta. Nakon toga se unosi broj upita \(m\) (\(1 \leq m \leq 100000\)) i u narednih \(m\) redova se unose vremenski periodi određeni rednim brojem početnog minuta \(a\) i krajnjeg minuta \(b\) (\(0 \leq a \leq b < n\)).
Na standardni izlaz ispisati \(m\) celih brojeva koji predstavljaju ukupan broj posetilaca u svakom od tih \(m\) perioda.
5 1 2 3 4 5 3 0 4 1 3 2 2
15 9 3
Učitan je broj posetilaca tokom 5 minuta.
Direktno rešenje podrazumeva da sve brojeve učitamo u niz, a zatim da za svaki upit iznova računamo zbir odgovarajućeg segmenta niza.
// ucitavamo niz
int n;
cin >> n;
vector<int> brojevi(n);
for (int i = 0; i < n; i++)
cin >> brojevi[i];
// ucitavamo granice segmenata i izracunavamo i ispisujemo
// njihove zbirove
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
int zbir = 0;
for (int j = a; j <= b; j++)
zbir += brojevi[j];
cout << zbir << endl;
}#include <iostream>
#include <vector>
using namespace std;
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<int> brojevi(n);
for (int i = 0; i < n; i++)
cin >> brojevi[i];
// ucitavamo granice segmenata i izracunavamo i ispisujemo
// njihove zbirove
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
int zbir = 0;
for (int j = a; j <= b; j++)
zbir += brojevi[j];
cout << zbir << endl;
}
return 0;
}Složenost ovakvog pristupa je \(O(nm)\). Pošto se faza učitavanja i ispisa podataka prepliću, učitavanje bi i ispis podataka bi trebalo dodatno ubrzati, no to ne može popraviti neefikasnost ovog naivnog algoritma.
Jednostavno efikasno rešenje je zasnovano na narednoj ideji: umesto čuvanja elemenata niza, možemo čuvati niz zbirova prefiksa niza. Zbir svakog segmenta \([l, d]\) možemo razložiti na razliku zbira prefiksa do elementa \(d\) i prefiksa do elementa \(l-1\). Ako koristimo oznaku \(\sum_{k=m}^{n} a_k\) koja označava zbir \(a_m + a_{m+1} + \ldots + a_n\), možemo zapisati da je
\[\sum_{k=l}^d a_k = \sum_{k=0}^{d} a_k - \sum_{k=0}^{l-1} a_k.\]
Zbirovi svih prefiksa se mogu izračunati i smestiti u dodatni (a ako je ušteda memorije bitna, onda čak i u originalni) niz. Dakle, tokom učitavanja elemenata možemo formirati niz zbirova prefiksa (računaćemo ih inkrementalno, jer se svaki naredni zbir prefiksa dobija uvećavanjem prethodnog zbira prefiksa za tekući element niza). Neka \(z_i\) označava zbir elemenata prefiksa određenog pozicijama iz intervala \([0, i)\). Formiramo, dakle, niz \(z_i = \sum_{k=0}^{i-1} a_k\) (pri čemu je \(z_0 = 0\), zbir praznog prefiksa). Tada zbir elemenata u segmentu pozicija \([l, d]\) izračunavamo kao \(z_{d+1} - z_l\).
// ucitavamo brojeve i izracunavamo zbirove prefiksa
int n;
cin >> n;
vector<int> zbirovi_prefiksa(n+1);
zbirovi_prefiksa[0] = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
zbirovi_prefiksa[i+1] = zbirovi_prefiksa[i] + x;
}
// ucitavamo granice segmenata i izracunavamo i ispisujemo
// njihove zbirove
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
cout << zbirovi_prefiksa[b+1] - zbirovi_prefiksa[a] << '\n';
}#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// ucitavamo brojeve i izracunavamo zbirove prefiksa
int n;
cin >> n;
vector<int> zbirovi_prefiksa(n+1);
zbirovi_prefiksa[0] = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
zbirovi_prefiksa[i+1] = zbirovi_prefiksa[i] + x;
}
// ucitavamo granice segmenata i izracunavamo i ispisujemo
// njihove zbirove
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
cout << zbirovi_prefiksa[b+1] - zbirovi_prefiksa[a] << '\n';
}
return 0;
}Za učitavanje brojeva i formiranje niza zbirova prefiksa potrebno nam je \(O(n)\) koraka. Nakon ovakvog pretprocesiranja, zbir svakog segmenta se može izračunati u vremenu \(O(1)\), pa je ukupna složenost \(O(n + m)\).
Pošto se u ovom zadatku prepliću faza učitavanja i faza ispisa podataka na standardni ulaz i izlaz, potrebno je obratiti pažnju na neefikasnost koja nastaje zbog čestog pražnjenja izlaznog bafera. Potrebno je razvezati cin i cout korišćenjem cin.tie(0) i umesto pomoću endl u novi red prelaziti pomoću \n. Naravno, ovo ima smisla samo u slučaju automatske primene programa na velike ulaze i izlaze - ovim izmenama program prestaje da radi korektno u interaktivnom režimu.
Dat je niz \(a\) prirodnih brojeva dužine \(n\) i prirodan broj \(k\). Napisati program koji određuje broj segmenta niza \(a\) (nepraznih podnizova uzastopnih elemenata) čiji je zbir deljiv sa \(k\).
U prvoj liniji standardnog ulaza nalazi se prirodan broj \(k\) (\(k\leq 10^5\)). Druga linija standardnog ulaza sadrži prirodan broj \(n\) (\(n \leq 10^5\)). U sledećoj liniji se nalazi \(n\) prirodnih brojeva (ti brojevi predstavljaju redom elemente niza \(a\)), razdvojenih sa po jednim razmakom.
Na standarnom izlazu prikazati koliko postoji segmenata niza \(a\) čiji je zbir deljiv sa \(k\).
3 5 1 8 2 3 4
4
To su segmenti \((1,8)\), \((3)\), \((2,3,4)\) i \((1,8,2,3,4)\).
Direktan način da se zadatak reši je da se ugnežđenim petljama nabroje svi segmenti, da se za svaki izračuna suma i da se proveri da li je deljiva sa \(k\), brojeći usput takve segmente. Broj je deljiv sa \(k\) ako i samo ako daje ostatak \(0\) pri deljenju sa \(k\), a znamo da je ostatak pri deljenju zbira sa brojem \(k\) zapravo jednak zbiru ostataka tj. da važi da je \((a + b) \,\mathrm{mod}\,k = (a \,\mathrm{mod}\,k + b \,\mathrm{mod}\,k) \,\mathrm{mod}\,k\).
Dakle, za svaki segment dovoljno je izračunati zbir po modulu \(k\), pri čemu za fiksirani levi kraj segmenta, zbir svakog narednog segmenta \([i, j]\) dobijamo inkrementalno, od zbira segmenta \([i, j-1]\), dodajući na njega broj \(a_j\) i izračunavajući ostatak dobijenog zbira pri deljenju sa \(k\).
// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a,
int k) {
// duzina niza
int n = a.size();
// broj segmenata deljivih sa k
int broj = 0;
// obradjujemo sve segmente [i, j]
for (int i = 0; i < n; i++) {
// zbir po modulu k segmenta [i, j] inicijalizujemo na
// nulu
int s = 0;
for (int j = i; j < n; j++) {
// azuriramo zbir po modulu k segmenta [i, j] na osnovu
// zbira [i, j-1]
s = (s + a[j]) % k;
// ako je zbir po modulu k jednak 0, zbir je deljiv sa k
if (s == 0)
broj++;
}
}
return broj;
}#include <iostream>
#include <vector>
using namespace std;
// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a,
int k) {
// duzina niza
int n = a.size();
// broj segmenata deljivih sa k
int broj = 0;
// obradjujemo sve segmente [i, j]
for (int i = 0; i < n; i++) {
// zbir po modulu k segmenta [i, j] inicijalizujemo na
// nulu
int s = 0;
for (int j = i; j < n; j++) {
// azuriramo zbir po modulu k segmenta [i, j] na osnovu
// zbira [i, j-1]
s = (s + a[j]) % k;
// ako je zbir po modulu k jednak 0, zbir je deljiv sa k
if (s == 0)
broj++;
}
}
return broj;
}
int main() {
// ucitavamo ulazne podatke
int k;
cin >> k;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ispisujemo broj segmenata ciji je zbir deljiv sa k
cout << brojSegmenataZbiraDeljivogSaK(a, k) << endl;
return 0;
}Uz ovako inkrementalno izračunavanje zbira, složenost algoritma jednaka je broju segmenata što je \(O(n^2)\).
Tražimo broj segmenata \(a_p, a_{p+1}, \ldots, a_q\), za \(0\leq p\leq q < n\), takvih da je zbir \(S_{pq} = a_p + a_{p+1} + ... + a_q\) deljiv sa \(k\).
Obeležimo sa \(S_0 = 0\), \(S_1 = a_0\), \(S_2 = a_0 + a_1\), itd., tj. obeležimo sa \(S_i\), \(0<i\leq n\) zbir prvih \(i\) elemenata niza (\(S_i = a_0 + a_1 + ... +a_{i-1}\)). Zbir \(S_{pq}\) možemo izraziti kao \(S_{q+1} - S_p\).
Na osnovu osobina operacija po modulu važi da je \(S_{pq} \,\mathrm{mod}\,k = (S_{q+1} \,\mathrm{mod}\,k - S_p \,\mathrm{mod}\,k + k) \,\mathrm{mod}\,k\).
Prema tome zbir \(S_{pq}\) je deljiv sa \(k\) (tj. važi \(S_{pq} \,\mathrm{mod}\,k = 0\)) akko zbirovi \(S_{q+1}\) i \(S_p\) imaju isti ostatak pri deljenju sa \(k\) tj. ako je \(S_{q+1} \,\mathrm{mod}\,k = S_p\,\mathrm{mod}\,k\).
Obeležimo sa \(b_r\) broj zbirova \(S_i\) (za \(0 \leq i \leq n\)) koji pri deljenju sa \(k\) daju ostatak \(r\) (za svako \(0 \leq r < k\)). Svaki par (različitih) zbirova prefiksa koji daju isti ostatak \(r\) određuje tačno jedan segment čiji je zbir elemenata deljiv sa \(k\). U skupu od \(m\) različitih elemenata postoji tačno \(\frac{m(m-1)}{2}\) različitih parova. Zato je za svako \(r\) broj segmenata koji se dobija kombinujući dva zbira koji daju ostatak \(r\) jednak \(\frac{b_r \cdot (b_r - 1)}{2}\). Prema tome ukupan broj segmenata deljivih sa \(k\) je \(\sum_{r=0}^{k-1}\frac{b_r \cdot (b_r - 1)}{2}\).
Ostaje još samo pitanje kako izbrojati zbirove prefiksa za svaki dati ostatak tj. kako izračunati sve brojeve \(b_r\). Nizom \(b\) dužine \(k\) pamtimo broj prefiksa čiji zbirovi elemenata daju ostatke redom \(0, 1, 2, \ldots, k-1\) tako da je \(b_r\) jednak broju prefiksa čiji zbir elemenata pri deljenju sa \(k\) daje ostatak \(r\) (što je moguće, s obzirom na datu gornju granicu broja \(k\)). Zbirove prefiksa, naravno, izračunavamo inkrementalno.
Polazni zbir je \(S_0 = 0\), tako da sve elemente niza \(b\) inicijalizujemo na 0, osim vrednosti na poziciji 0 koju inicijalizujemo na 1. Zbir tekućeg prefiksa održavamo u promenljivoj \(S\) koju inicijalizujemo na nulu. Učitavamo član po član niza \(x\), i pri tome ažuriramo zbir prefiksa (\(S\) postavljamo na \((S + x)\,\mathrm{mod}\,k\)), uvećavajući odgovarajući brojač (vrednost \(b_S\) uvećavamo za 1).
Primer 3.A.2. Prikažimo rad ovog algoritma na primeru određivanja broja segmenata niza \(1, 8, 2, 3, 4\) koji su deljivi sa \(3\). Mogući ostaci su \(0\), \(1\) i \(2\).
i ai Si b0 b1 b2 0 1 0 0 0 1 1 1 1 0 1 8 0 2 1 0 2 2 2 2 1 1 3 3 2 2 1 2 4 4 0 3 1 2
Zato je konačan rezultat \(\frac{b_0(b_0-1)}{2} + \frac{b_1(b_1-1)}{2} + \frac{b_1(b_1-1)}{2} = 3 + 0 + 1 = 4\).
// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a,
int k) {
// duzina niza
int n = a.size();
// na mestu i u nizu br čuvamo broj segmenata čiji zbir pri
// deljenju sa k daje ostatak i
vector<int> br(k, 0);
br[0] = 1;
// zbir tekućeg segmenata
int s = 0;
for (int i = 0; i < n; i++) {
// ažuriramo zbir elemenata tekućeg segmenta po modulu k
s = (s + a[i]) % k;
br[s]++;
}
// izračunavamo ukupan broj segmenata deljivih sa k
int broj = 0;
for(int i = 0; i < k; i++)
broj += br[i]*(br[i]-1)/2;
return broj;
}#include <iostream>
#include <vector>
using namespace std;
// izracunava broj segmenata niza a ciji je zbir deljiv sa k
int brojSegmenataZbiraDeljivogSaK(const vector<int>& a,
int k) {
// duzina niza
int n = a.size();
// na mestu i u nizu br čuvamo broj segmenata čiji zbir pri
// deljenju sa k daje ostatak i
vector<int> br(k, 0);
br[0] = 1;
// zbir tekućeg segmenata
int s = 0;
for (int i = 0; i < n; i++) {
// ažuriramo zbir elemenata tekućeg segmenta po modulu k
s = (s + a[i]) % k;
br[s]++;
}
// izračunavamo ukupan broj segmenata deljivih sa k
int broj = 0;
for(int i = 0; i < k; i++)
broj += br[i]*(br[i]-1)/2;
return broj;
}
int main() {
// ucitavamo ulazne podatke
int k;
cin >> k;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ispisujemo broj segmenata ciji je zbir deljiv sa k
cout << brojSegmenataZbiraDeljivogSaK(a, k) << endl;
return 0;
}Vremenska složenost ovog algoritma je, jasno, \(O(n)\). Primetimo da u ovom rešenju nije bilo potrebno koristiti niz za brojeve koje unosimo, jer pri unosu obradimo svaki element, međutim, koristimo pomoćni niz dužine \(k\), pa je memorijska složenost \(O(k)\). Obratimo pažnju na to da ovo može biti ograničavajući faktor, ako \(k\) može biti jako veliki broj (što u ovom zadatku nije slučaj).
Kamion prevozi teret tokom \(N\) kilometara puta. Na put kreće prazan i tokom puta utovaruje i istovaruje pakete. Ako se za svaki paket zna na kom je kilometru puta utovaren, na kom je kilometru puta istovaren i kolika mu je masa, napiši program koji određuje koliko je opterećenje kamiona na svakom kilometru puta. Smatrati da se predmet utovaruje na početku, a istovaruje na kraju datog kilometra.
Sa standardnog ulaza se unosi broj kilometara \(N\) (\(10\leq N 10000\)), zatim, u narednom redu, broj predmeta \(M\) (\(0 \leq M \leq 10000\)), a nakon toga, u narednih \(M\) redova po tri cela broja razdvojena razmacima koji predstavljaju broj kilometra na čijem je početku utovaren predmet (ceo broj između \(0\) i \(N-1\)), broj kilometra na čijem kraju je istovaren (ceo broj između \(0\) i \(N-1\)) i na kraju masa predmeta (ceo broj između 1 i 10).
Na standardni izlaz ispisati masu tereta u kilogramima na svakom kilometru puta (iza svake mase napisati po jedan razmak).
10 3 1 5 10 3 7 10 2 8 15
0 10 25 35 35 35 25 25 15 0
km 0 1 2 3 4 5 9 7 8 9 0 0 0 0 0 0 0 0 0 0 1 5 10 0 10 10 10 10 10 0 0 0 0 3 7 10 0 10 10 20 20 20 10 10 0 0 2 8 15 0 10 25 35 35 35 25 25 15 0
Direktan način je da se održava niz \(M\) u kojem se pamti masa na kamionu tokom svakog kilometra puta. Nakon učitavanja svakog podatka o predmetu (početnog kilometra \(a\), završnog kilometra \(b\) i mase \(m\)), sve vrednosti u nizu \(M\) na pozicijama od \(a\) do \(b\) (uključujući i njih) se uvećavaju za \(m\).
Problem sa ovim rešenjem je to što predmeti mogu putovati veliki broj kilometara pa se u svakom koraku vrši ažuriranje velikog broja članova niza (složenost je u najgorem slučaju \(O(n \cdot m)\)).
int n;
cin >> n;
vector<int> mase(n, 0);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int km_od, km_do, masa;
cin >> km_od >> km_do >> masa;
for (int km = km_od; km <= km_do; km++)
mase[km] += masa;
}
for (int masa : mase)
cout << masa << " ";#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> mase(n, 0);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int km_od, km_do, masa;
cin >> km_od >> km_do >> masa;
for (int km = km_od; km <= km_do; km++)
mase[km] += masa;
}
for (int masa : mase)
cout << masa << " ";
return 0;
}Zadatak možemo rešiti efikasnije ako umesto da u nizu \(M\) održavamo masu u kamionu u kilometru \(i\), održavamo razliku između mase u kilometru \(i\) i \(i-1\) (na poziciji \(0\) se čuva masa u kamionu u nultom kilometru). Dakle, uvodimo niz \(R_i\) takav da je \(R_0 = M_0\), a \(R_i = M_i - M_{i-1}\), za \(1 \leq i < n\). Posmatrajmo šta se dešava sa nizom \(R\) kada se u nizu \(M\) svi elementi na pozicijama \(a\) do \(b\) uvećaju za \(m\).
Recimo da ako je \(b = n-1\), tada ne moramo razmatrati vrednost \(R_{b+1} = R_n\) (mada, uniformnosti radi, možemo, što zahteva da niz \(R\) sadrži \(n+1\) element). Dakle, prilikom svakog učitavanja brojeva \(a\), \(b\) i \(m\) potrebno je samo da uvećavamo element \(R_a\) za \(m\), a da element \(R_{b+1}\) umanjimo za \(m\).
Kada znamo elemente niza \(R\) elemente niza \(M\) možemo jednostavno rekonstruisati sabiranjem elemenata niza \(R\). Naime, važi da je \(M_0 = R_0\), dok je \(M_i = M_{i-1} + R_i\), tako da svaki naredni element niza \(M\) možemo izračunati kao zbir prethodnog elementa niza \(M\) i njemu odgovarajućeg elementa niza \(R\). Primetimo da je zapravo element \(M_i\) jednak zbiru svih elemenata od \(R_0\) do \(R_i\), jer je \(R_0 + R_1 + \ldots + R_i = M_0 + (M_1 - M_0) + \ldots + (M_i - M_{i-1}) = M_i\).
Ukupna složenost ovog pristupa je \(O(n + m)\).
int n;
cin >> n;
vector<int> razlika(n+1, 0);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int km_od, km_do, masa;
cin >> km_od >> km_do >> masa;
razlika[km_od] += masa;
razlika[km_do+1] -= masa;
}
int masa_km = 0;
for (int km = 0; km < n; km++) {
masa_km += razlika[km];
cout << masa_km << " ";
}#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> razlika(n+1, 0);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int km_od, km_do, masa;
cin >> km_od >> km_do >> masa;
razlika[km_od] += masa;
razlika[km_do+1] -= masa;
}
int masa_km = 0;
for (int km = 0; km < n; km++) {
masa_km += razlika[km];
cout << masa_km << " ";
}
return 0;
}Ideja korišćena u ovom zadatku donekle je slična (zapravo inverzna) tehnici određivanja zbira segmenata kao razlike dva zbira prefiksa. Može se primetiti da se rekonstrukcija niza vrši zapravo izračunavanjem prefiksnih zbirova niza razlika susednih elemenata, što ukazuje na duboku vezu između ove dve tehnike. Zapravo, razlike susednih elemenata predstavljaju određeni diskretni analogon izvoda funkcije, dok prefiksni zbirovi predstavljaju analogiju određenog integrala. Izračunavanje zbira segmenta kao razlike dva zbira prefiksa odgovara Njutn-Lajbnicovoj formuli.
Poznato je \(n\) računskih poslova koje treba izvršiti i za svaki od njih je poznato koliko je vremena potrebno procesoru da ga izvrši. Svakom od \(k\) identičnih procesora treba dodeliti tačno po jedan posao, pri čemu je cilj da svi procesori budu što ravnomernije opterećeni. Kolika je najmanja moguća razlika između vremena izvršavanja dva posla dodeljena tim procesorima?
Sa standardnog ulaza se unosi prirodan broj \(n\) (\(1 \leq n \leq 50000\)) a zatim i \(n\) prirodnih brojeva (između \(1\) i \(10^6\), razdvojenih po jednim razmakom) koji predstavljaju vreme potrebno za izvršavanje svakog od poslova. U poslednjem redu se unosi broj procesora \(k\) (\(1 \leq k \leq n\)).
Na standardni izlaz ispisati vrednost najmanje razlike između dva posla dodeljena ovim procesorima.
8 3 8 1 17 4 7 12 9 4
5
Najmanja razlika se dobija ako procesori izvršavaju poslove koji traju 8, 4, 7 i 9 jedinica vremena.
Najdirektniji način da se reši zadatak je da se ispitaju svi podskupovi od \(k\) elemenata skupa od \(n\) elemenata i da se među njima odabere najbolji. Ovo rešenje je relativno komplikovano implementirati, a uz to je i veoma neefikasno (broj podskupova je \({n \choose k}\), što je \(O(n^k)\)).
Bolje i efikasnije rešenje se zasniva na sortiranju. Naime, kada se polazni poslovi sortiraju po vremenu izvršavanja, procesorima treba dodeliti nekih uzastopnih \(k\) poslova. Pretpostavimo da nakon sortiranja imamo niz \(a_0, a_1, \ldots, a_{n-1}\). Procesorima treba dodeliti redom poslove od \(a_i\), do \(a_{i+k-1}\), za neko \(0 \leq i \leq n - k\).
Dokažimo prethodnu činjenicu. Pretpostavimo suprotno, da poslovi koji daju najmanji raspon ne čine uzastopan niz i da svaki uzastopni niz poslova dužine \(k\) ima strogo veći raspon od raspona skupa uzetih paketa. Neka je prvi uzeti posao \(a_i\). Tada sigurno postoji neki posao \(a_j\) za \(i < j < i+k\) koji nije uzet, a umesto njega je uzet neki paket \(a_{j'}\) za neko \(i + k \leq j' < n\). Neka je \(j'\) poslednji paket koji je uzet. Međutim, kada bi procesor koji izvršava posao \(a_{j'}\) zamenio taj posao za \(a_{j}\), raspon bi se sigurno smanjio ili bar ostao isti (jer bi poslednji uzeti paket tada bio neki paket \(a_{j''}\), za \(j'' < j'\), a pošto je niz sortiran neopadajuće, važi da je \(a_{j''} \leq a_{j}\), pa i \(a_{j''} - a_i \leq a_{j'} - a_i\). Daljim zamenema istog tipa možemo doći do toga da su svi uzeti paketi uzastopni, a da je raspon manji ili jednak polaznom, što je u kontradikciji sa tim da je raspon polaznog skupa uzetih paketa strogo manji od raspona bilo kojeg niza \(k\) uzastopnih paketa.
Razmatranje prethodnog tipa je karakteristično za takozvane gramzive (tj. pohlepne) algoritme, o kojima će više reči biti kasnije.
Na osnovu prethodnog, jasno je da niz trajanja poslova treba najpre sortirati i zatim odrediti minimum razlika vrednosti \(a_{i+k-1} - a_{i}\), za \(0 \leq i \leq n - k\), korišćenjem uobičajenog algoritma za nalaženje minimuma.
Složenošću ovog algoritma dominira složenost koraka sortiranja, a ona je \(O(n\log n)\), ako se koriste bibliotečke implementacije. Nakon sortiranja, minimum se određuje u \(n-k\) koraka, tj. u linearnoj složenosti \(O(n)\) (kada je \(k\) malo, broj koraka može biti veoma blizak \(n\)).
// odredjuje najmanju razliku u trajanju poslova
// ako se bira k poslova medju poslovima iz niza a
int minRazlika(vector<int>& a, int k) {
// broj paketa
int n = a.size();
// sortiramo pakete po trajanju poslova
sort(begin(a), end(a));
// odredjujemo i najmanju mogucu razliku
int min = numeric_limits<int>::max();
for (int i = 0; i + k - 1 < n; i++) {
int razlika = a[i + k - 1] - a[i];
if (razlika < min)
min = razlika;
}
return min;
}#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;
// odredjuje najmanju razliku u trajanju poslova
// ako se bira k poslova medju poslovima iz niza a
int minRazlika(vector<int>& a, int k) {
// broj paketa
int n = a.size();
// sortiramo pakete po trajanju poslova
sort(begin(a), end(a));
// odredjujemo i najmanju mogucu razliku
int min = numeric_limits<int>::max();
for (int i = 0; i + k - 1 < n; i++) {
int razlika = a[i + k - 1] - a[i];
if (razlika < min)
min = razlika;
}
return min;
}
int main() {
// ucitavamo trajanje poslova u paketima
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ucitavamo broj procesora
int k;
cin >> k;
// odredjujemo i najmanju mogucu razliku za nekih k odabranih poslova
cout << minRazlika(a, k) << endl;
return 0;
}Dve reči su anagrami ako se jedna može dobiti od druge samo promenom redosleda slova (na primer, trava i vatra). Napiši program koji u datom skupu reči pronalazi najveći podskup reči koje su međusobni anagrami.
Sa standardnog ulaza se unosi broj reči \(n\) (\(0 \leq n \leq 50000\)), a zatim u \(n\) narednih linija po jedna reč polaznog skupa (sve reči se sastoje samo od malih slova engleskog alfabeta i imaju najviše 200 karaktera).
Na standardni izlaz ispisati veličinu najvećeg podskupa polaznog skupa reči, u kome su sve reči jedna drugoj anagrami.
10 tommarvoloriddle viviandarkbloom iamlordvoldemort danabnormal normdanabal vladimirnabokov vladimirkoborov bladvakvinomori damonalbarn dorianvivalkomb
4
Najbrojniju skup anagrama čine reči
viviandarkbloom vladimirnabokov bladvakvinomori dorianvivalkomb
Provera da li su dve reči anagrami može se zasnivati na sortiranju slova dve reči i zatim poređenju da li su dobijene reči iste. Alternativno, provera da li su dve reči anagrami može se uraditi tako što se izračunaju brojevi pojavljivanja svakog od 26 karaktera engleske abecede i zatim se porede ti brojevi za dve zadate reči. U oba pristupa, svaku reč kanonizujemo i umesto poređenja polaznih reči, možemo da poredimo njihove kanonske oblike. Kanonizovanjem dobijamo niz kanonskih predstavnika i želimo da u tom nizu pronađemo skup ekvivalentnih elemenata (jednakih kanonskih predstavnika) koji je najveće kardinalnosti od svih takvih podskupova.
Jedno moguće rešenje je da sortiramo karaktere svake učitane reči (abecedno), a zatim da sortiramo tako dobijeni niz reči (leksikografski abecedno), da bi se identične sortirane reči našle jedna iza druge. Na tako dobijen niz primenjujemo pronalaženje najduže serije jednakih uzastopnih elemenata.
Složenost sortiranja slova svih pojedinačnih reči je \(O(n\cdot m\log{m})\), gde je \(n\) broj reči, a \(m\) maksimalni broj slova u reči. Složenost sortiranja niza svih reči se može proceniti na \(O(n \log{n})\), jer je realno očekivati da će se leksikografsko poređenje dve reči vršiti veoma efikasno (reči su kratke, a realno je očekivati i da su “šarenolike”, tj. da će se njihov poredak moći odrediti već nakon poređenja malog broja početnih karaktera). Pošto je broj slova \(m\) veoma mali, možemo ga smatrati konstantim i složenost algoritma grubo oceniti sa \(O(n\log{n})\).
// sortiramo karaktere svake reci
for (int i = 0; i < n; i++)
sort(begin(reci[i]), end(reci[i]));
// sortiramo ceo niz reci leksikografski
sort(begin(reci), end(reci));
// odredjujemo duzinu najduze serije jednakih reci
int maxDuzinaSerije = 1;
int tekucaDuzinaSerije = 1;
for (int i = 1; i < n; i++) {
if (reci[i] == reci[i-1])
tekucaDuzinaSerije++;
else
tekucaDuzinaSerije = 1;
if (tekucaDuzinaSerije > maxDuzinaSerije)
maxDuzinaSerije = tekucaDuzinaSerije;
}
cout << maxDuzinaSerije << endl;#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<string> reci(n);
for (int i = 0; i < n; i++)
cin >> reci[i];
// sortiramo karaktere svake reci
for (int i = 0; i < n; i++)
sort(begin(reci[i]), end(reci[i]));
// sortiramo ceo niz reci leksikografski
sort(begin(reci), end(reci));
// odredjujemo duzinu najduze serije jednakih reci
int maxDuzinaSerije = 1;
int tekucaDuzinaSerije = 1;
for (int i = 1; i < n; i++) {
if (reci[i] == reci[i-1])
tekucaDuzinaSerije++;
else
tekucaDuzinaSerije = 1;
if (tekucaDuzinaSerije > maxDuzinaSerije)
maxDuzinaSerije = tekucaDuzinaSerije;
}
cout << maxDuzinaSerije << endl;
return 0;
}Dat je niz koji sadrži prirodne brojeve i ceo broj \(D\). Napiši program koji određuje koji se od nekoliko datih nizova može od polaznog dobiti razmenama elemenata koji su tačno na rastojanju \(D\).
Sa standardnog ulaza se učitava ceo broj \(d\) (\(1 \leq d \leq k\)), zatim ceo broj \(k\) (\(5 \leq k \leq 10^5\)), zatim ceo broj \(n\) (\(1 \leq n \leq 10\)) i nakon toga \(n\) nizova dužine \(k\) čiji su elementi razdvojeni razmacima.
Na standardni izlaz za svaki niz od drugog do poslednjeg ispisati da ako se može transformisati u prvi razmenama elemenata na rastojanju \(d\), tj. ne u suprotnom.
2 7 6 1 2 3 4 5 6 7 3 4 1 2 7 6 5 2 1 4 3 6 5 7 1 4 7 2 3 6 5 1 4 7 6 3 2 5 5 4 7 6 3 1 2
da ne da da ne
3 4 1 2 7 6 5 - razmena 3 i 1, 4 i 2, i 7 i 5 2 1 4 3 6 5 7 - ne može 1 4 7 2 3 6 5 - razmena 4 i 2, 7 i 3 i 7 i 5 1 4 7 6 3 2 5 - razmena 6 i 2, 4 i 2, 7 i 3 i 7 i 5 5 4 7 6 3 1 2 - ne može
Primetimo da se element na poziciji \(0\), nakon permutacije može naći samo na poziciji \(d\), \(2d\), \(3d\) itd. Element na poziciji \(1\) se može naći samo na pozicijama \(d+1\), \(2d+1\), \(3d+1\) itd. Na kraju, element na poziciji \(d-1\) se može naći samo na pozicijama \(d+d-1\), \(2d+d-1\), \(3d+d-1\) itd.
Primer 3.A.3. Na primer, u nizu, \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), ako je rastojanje \(d\) jednako \(3\), možemo razmenjivati samo elemente \(1\), \(4\) i \(7\), zatim elemente \(2\), \(5\) i \(8\) i na kraju \(3\), \(6\) i \(9\). Ne postoji nikakav način da se, na primer, element \(2\) ili element \(9\) nađu na poziciji elementa \(1\) ili elementa \(7\).
Dakle, niz je suštinski izdeljen na \(d\) particija, tako što su dva elementa u istoj particiji ako i samo ako su na rastojanju \(i\cdot d\), za neko celobrojno \(i\). Particije su međusobno nezavisne u smislu da se razmenama mogu permutovati samo oni elementi koji se nalaze u istoj particiji. Jedan niz se može transformisati u drugi razmenama elemenata na rastojanju \(d\), ako i samo ako se svaka particija može transformisati u odgovarajuću particiju drugog niza, razmenama susednih elemenata u okviru te particije.
Primer 3.A.4. Na primer, niz \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\) se može transformisati u niz \(7\), \(2\), \(9\), \(1\), \(8\), \(6\), \(4\), \(5\), \(3\), zato što se particija \((1, 4, 7)\) može transformisati u \((7, 1, 4)\), particija \((2, 5, 8)\) se može transformisati u \((2, 8, 5)\), a particija \((3, 6, 9)\) se može transformisati u particiju \((9, 6, 3)\). Pošto svaka particija čini niz za sebe, ostaje da se reši pitanje: da li se dati niz brojeva može transformisati u drugi niz operacijama razmene susednih elemenata?
Postoje razni načini da se na ovo pitanje odgovori, a jedan od najefikasnijih se zasniva na činjenici da se svaki niz može sortirati isključivo razmenama uzastopnih elemenata (na primer, Bubble Sort algoritam vrši upravo takvo sortiranje). To znači da se jedan niz transformacijama uzastopnih elemenata može transformisati u drugi niz ako i samo ako se sortiranjem i jednog i drugog dobija isti niz. Pri tom, sortiranje ne mora biti vršeno samo razmenama uzastopnih elemenata već i mnogo efikasnijim algoritmima (jer je rezultat sortiranja jedinstveno određen i ako znamo da se nekim efikasnim algoritmom sortiranja od početnog niza dobija neki sortiran niz, taj isti niz bi se dobio i da se sortiranje vrši samo razmenama uzastopnih elemenata). Jedan od načina da prethodna razmatranja iskombinujemo u rešenje je da uvedemo operaciju pronalaženja kanonskog predstavnika za svaki niz u odnosu na dati parametar \(d\), tako što ćemo svaku njegovu particiju kanonizovati tj. sortirati.
Primer 3.A.5. Na primer, za \(d=3\) niz \(2, 16, 41, 15, 12, 31, 11, 9\) se deli na particije \((2, 15, 11)\), \((16, 12, 9)\), \((41, 31)\), svaka se particija se nezavisno sortira i time se dobija \((2, 11, 15)\), \((9, 12, 16)\), i \((31, 41)\), čime se dobija kanonski predstavnik \(2, 9, 31, 11, 12, 41, 15, 16\). Dva niza će se moći d-permutovati jedan u drugi ako i samo ako su njihovi ovako definisani kanonski predstavnici jednaki.
Pošto u okviru kanonizacije koristimo bibliotečki algoritam sortiranja možemo pretpostaviti da će njegova složenost za niz dužine \(m\) biti \(O(m\cdot \log{(m)})\). Pošto se sortira \(d\) particija, a svaka je dužine oko \(k/d\), i vrši se prebacivanje elemenata u pomoćni niz i nazad, složenost najgoreg slučaja kanonizacije se može proceniti kao \(O(d\cdot (k/d\cdot \log{(k/d)} + 2(k/d)))\) tj. \(O(k\cdot \log{(k/d)})\). Zato izračunavanje kanonskih predstavnika svih nizova može da se proceni na \(O(n\cdot k\cdot \log{(k/d)})\). S obzirom na to da se poređenje jednakosti dva kanonska predstavnika vrši u vremenu \(O(k)\), a ovo poređenje se vrši \(n-1\) put, imamo dodatno još \(O(nk)\) operacija. Za ukupnu složenost algoritma se zato može uzeti \(O(n\cdot k \cdot \log{(k/d)})\), tj. \(O(k\cdot \log{(k/d)})\) jer \(n\), za razliku od \(k\) ima veoma malu vrednost (praktično se može smatrati konstantom).
Napomenimo da je nakon kanonizacije svake particije niza \(T_i\) bilo moguće proveravati jednakost sa odgovarajućom particijom niza \(S\), čime bi se malo brže moglo konstatovati da se niz ne može transformisati, ali bi se kod donekle zakomplikovao. Slično, korišćenje pomoćnog niza nije bilo neophodno za čuvanje particija, već je bilo moguće kanonizaciju vršiti u okviru niza \(S\), razmenama njegovih elemenata iz istih particija, ali tada ne bi bilo moguće koristiti bibliotečku funkciju sortiranja, što bi takođe dosta zakomplikovalo kod. Asimptotska složenost najgoreg slučaja bi ostala ista.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// određivanje kanonskog predstavnika za niz s
void kanonizuj(vector<int>& s, int d) {
int duzina = s.size();
// pomocni vektor koji ce cuvati particiju po particiju
vector<int> particija(duzina / d + 1);
// kanonizovacemo svaku od d particija
for (int i = 0; i < d; i++) {
int m;
// prebacujemo elemente i-te particije u pomocni vektor
m = 0;
for (int j = i; j < duzina; j += d)
particija[m++] = s[j];
// sortiramo elemente particije unutar pomocnog vektora
sort(particija.begin(), particija.begin() + m);
// vracamo elemente particije iz pomocnog vektora nazad u niz s
m = 0;
for (int j = i; j < duzina; j += d)
s[j] = particija[m++];
}
}
int main() {
// iskljucujemo sinhronizaciju da bi ucitavanje teklo brze
ios::sync_with_stdio(false);
// ucitavamo rastojanje d
int d;
cin >> d;
// ucitavamo dužinu nizova k
int k;
cin >> k;
// ucitavamo broj nizova
int n;
cin >> n;
// ucitavamo niz S
vector<int> s(k);
for (int i = 0; i < k; i++)
cin >> s[i];
// odredjujemo kanonskog predstavnika niza s
kanonizuj(s, d);
// obradjujemo preostalih n-1 nizova Ti
for (int j = 1; j < n; j++) {
// ucitvamo niz Ti
vector<int> t(k);
for (int i = 0; i < k; i++)
cin >> t[i];
// odredjujemo kanonskog predstavnika niza Ti
kanonizuj(t, d);
// odredjujemo da li se niz S moze transformisati u niz Ti
// (moze ako i samo ako su im kanonski predstavnici jednaki)
// i ispisujemo rezultat u trazenom formatu
cout << (s == t ? "da" : "ne") << endl;
}
return 0;
}Napisati program koji za niz zatvorenih intervala \([a_i, b_i], i=0, 1, \cdots, n-1\) određuje ukupnu dužinu delova prave koje pokrivaju i minimalni broj intervala kojim se može postići pokrivanje istog skupa tačaka prave (taj skup intervala može se dobiti ukrupnjivanjem polaznih intervala, tj. objedinjavanjem polaznih intervala koji se seku).
U prvoj liniji standardnog ulaza učitava se broj intervala \(n\) (\(1 \le n \le 50000\)), a u narednih \(n\) linija parovi celih brojeva za koje važi \(-10^6 \le L_i < R_i \le 10^6\) koji predstavljaju levi i desni kraj intervala.
Dva broja: u prvom redu standardnog izlaza broj koji predstavlja dužinu dela prave koju pokrivaju učitani intervali, u sledećem redu broj intervala formiranih ukrupnjavanjem međusobno povezanih intervala.
4 1 3 5 8 2 4 6 7
6 2
Intervali \([1, 3]\) i \([2, 4]\) se mogu ukrupniti u interval \([1, 4]\), a intervali \([5, 8]\) i \([6, 7]\) u interval \([5, 8]\).
Zadatak možemo rešiti tako što jedan po jedan interval dodajemo u skup ukrupnjenih intervala formiranih na osnovu prethodno obrađenih intervala. Dodavanje novog intervala u kolekciju ukrupnjenih može se realizovati tako što se svi ukrupnjeni intervali koji se seku sa intervalom koji se trenutno obrađuje uklone iz kolekcije ukrupnjenih intervala, zatim se napravi njihova unija sa intervalom koji se dodaje i da se tako dobijen ukrupnjeni interval doda u trenutnu kolekciju ukrupnjenih intervala. Za ovo nam je potrebno da implementiramo proveru da li se dva intervala seku i izračunavanje unije dva intervala (što možemo uraditi korišćenjem minimuma i maksimuma). S obzirom na to da nam je potrebno da iz kolekcije ukrupnjenih intervala (efikasno) uklanjamo elemente dok je obilazimo, pogodno je da je predstavimo povezanom listom. U jeziku C++ možemo upotrebiti kolekciju list.
Uklanjanje elementa liste vrši se u vremenu \(O(1)\). Pošto se prilikom dodavanja svakog novog intervala obilaze svi prethodno ukrupnjeni intervali (a njih može biti isto onoliko koliko i polaznih intervala, ako su intervali disjunktni), složenost u najgorem slučaju je \(O(n^2)\).
typedef pair<int, int> Interval;
// provera da li se dva intervala seku
bool sekuSe(Interval i1, Interval i2) {
return max(i1.first, i2.first) <= min(i1.second, i2.second);
}
// pokrivac dva data intervala
Interval pokrivac(Interval i1, Interval i2) {
return make_pair(min(i1.first, i2.first),
max(i1.second, i2.second));
}
int main() {
// učitavamo podatke o intervalima
int n;
cin >> n;
vector<Interval> intervali(n);
for (int i = 0; i < n; i++)
cin >> intervali[i].first >> intervali[i].second;
// lista svih ukrupnjenih ranije obradjenih intervala
list<Interval> ukrupnjeni;
// analiziramo jedan po jedan dati interval
for (Interval interval : intervali) {
// uniramo ga sa svim ranije ukrupnjenim intervalima sa
// kojima se sece, uklanjajuci ih pritom iz liste
Interval novi = interval;
auto it = ukrupnjeni.begin();
while (it != ukrupnjeni.end()) {
if (sekuSe(interval, *it)) {
novi = pokrivac(novi, *it);
ukrupnjeni.erase(it++);
} else
it++;
}
// dodajemo u listu novi ukrupnjenih interval
ukrupnjeni.push_back(novi);
}
// izracunavamo i ispisujemo broj ukrupnjenih intervala i
// njihovu ukupnu duzinu
int broj_ukrupnjenih = ukrupnjeni.size();
int duzina_pokrivaca = 0;
for (auto interval : ukrupnjeni)
duzina_pokrivaca += interval.second - interval.first;
cout << duzina_pokrivaca << endl
<< broj_ukrupnjenih << endl;
return 0;
}#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> Interval;
// provera da li se dva intervala seku
bool sekuSe(Interval i1, Interval i2) {
return max(i1.first, i2.first) <= min(i1.second, i2.second);
}
// pokrivac dva data intervala
Interval pokrivac(Interval i1, Interval i2) {
return make_pair(min(i1.first, i2.first),
max(i1.second, i2.second));
}
int main() {
ios_base::sync_with_stdio(false);
// učitavamo podatke o intervalima
int n;
cin >> n;
vector<Interval> intervali(n);
for (int i = 0; i < n; i++)
cin >> intervali[i].first >> intervali[i].second;
// lista svih ukrupnjenih ranije obradjenih intervala
list<Interval> ukrupnjeni;
// analiziramo jedan po jedan dati interval
for (Interval interval : intervali) {
// uniramo ga sa svim ranije ukrupnjenim intervalima sa
// kojima se sece, uklanjajuci ih pritom iz liste
Interval novi = interval;
auto it = ukrupnjeni.begin();
while (it != ukrupnjeni.end()) {
if (sekuSe(interval, *it)) {
novi = pokrivac(novi, *it);
ukrupnjeni.erase(it++);
} else
it++;
}
// dodajemo u listu novi ukrupnjenih interval
ukrupnjeni.push_back(novi);
}
// izracunavamo i ispisujemo broj ukrupnjenih intervala i
// njihovu ukupnu duzinu
int broj_ukrupnjenih = ukrupnjeni.size();
int duzina_pokrivaca = 0;
for (auto interval : ukrupnjeni)
duzina_pokrivaca += interval.second - interval.first;
cout << duzina_pokrivaca << endl
<< broj_ukrupnjenih << endl;
return 0;
}Efikasan algoritam možemo dobiti ako prilikom dodavanja novog intervala nekako izbegnemo potrebu da se obilaze svi do tada ukrupnjeni intervali. Osnovna ideja je da intervale obilazimo u neopadajućem poretku koordinata levih krajeva. Ako intervale predstavimo uređenim parovima, bibliotečke funkcije sortiranja će ih sortirati upravo na taj način. S obzirom na takav redosled obilaska, svaki novi interval se može seći samo sa poslednjim ukrupnjenim intervalom (i stoga se može preskočiti analiza ostalih ukrupnjenih intervala).
S obzirom na to da nas ne zanimaju sami ukrupnjeni intervali, već samo njihov broj i dužina, tokom izvršavanja petlje u kojoj obrađujemo jedan po jedan interval održavaćemo samo tri podatka: dužinu dela prave koju pokrivaju do tada obrađeni intervali, broj ukrupnjenih intervala koji pokrivaju taj deo prave (pokrivač tog dela prave) i poziciju \(D_{max}\) desnog kraja poslednjeg ukrupnjenog intervala (to je ujedno najdešnja tačka svih do sada obrađenih intervala).
Inicijalizaciju možemo izvršiti na osnovu prvog intervala (on sam pokriva deo prave čija je dužina jednaka njegovoj, trenutno je formiran jedan ukrupnjeni interval i desni kraj je jednak desnom kraju tog prvog intervala).
U svakom koraku proširujemo dosadašnji pokrivač intervalom \([L_i, D_i]\), pri čemu je poslednji ukrupnjeni interval \([L, D_{max}]\). Moguća su sledeća 3 slučaja:
\(D_{max} < L_i\) — interval \([L_i, D_i]\) se ne može priključiti ni jednom već postojećem ukrupnjenom intervalu, niti se to može uraditi ni sa jednim narednim intervalom (jer su zbog sortiranosti svi oni desno od tekućeg). Tekući interval zato započinje novi ukrupnjeni interval, pa uvećavamo broj ukrupnjenih intervala za 1, dužinu pokrivenog dela prave povećavamo za dužinu tekućeg intervala, dok se \(D_{max}\) koriguje na \(D_i\).
\(L \leq L_i \leq D_{max} \leq D_i\) — dosadašnji pokrivač tj. njegov poslednji ukrupnjeni interval \([L, D_{max}]\) se seče sa intervalom \([L_i, D_i]\) pa se proširuje za dužinu \(D_i - D_{max}\), a kraj \(D_{max}\) se koriguje na \(D_i\), pri čemu se broj ukrupnjenih intervala ne menja.
\(L \leq L_i \leq D_i \le D_{max}\) — tekući interval \([L_i, D_i]\), je kompletno sadržan u nekom ukrupnjenom intervalu \([L, D_{max}]\) i može se preskočiti bez ažuriranja pokrivača koji se konstruiše.
Sortiranje \(n\) intervala vrši se u vremenu \(O(n\log{n})\). Nakon toga, obrada intervala vrši se jednim prolaskom kroz niz i složenost te faze je \(O(n)\). Ukupnom složenošću, dakle, dominira sortiranje i ona iznosi \(O(n\log{n})\).
// sortiramo intervale na osnovu njihovog levog kraja
sort(begin(intervali), end(intervali));
// prvi interval ukljucujemo u pokrivac
int duzina_pokrivaca = intervali[0].second -
intervali[0].first;
// desni kraj poslednjeg do sada ukrupnjenog intervala
int desni_kraj = intervali[0].second;
// broj ukrupnjenih intervala
int broj_ukrupnjenih = 1;
for (int i = 1; i < n; i++)
// trenutni interval se ne sece sa trenutno poslednjim
// ukrupnjenim intervalom (leži desno od njega)
if (intervali[i].first > desni_kraj) {
// zapocinjemo novi ukrupnjeni interval
broj_ukrupnjenih++;
duzina_pokrivaca += intervali[i].second -
intervali[i].first;
desni_kraj = intervali[i].second;
} else if (intervali[i].second > desni_kraj) {
// trenutni interval prosiruje trenutno poslednji
// ukrupnjeni interval
duzina_pokrivaca += intervali[i].second - desni_kraj;
desni_kraj = intervali[i].second;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo podatke o intervalima
int n;
cin >> n;
vector<pair<int, int>> intervali(n);
for (int i = 0; i < n; i++)
cin >> intervali[i].first >> intervali[i].second;
// sortiramo intervale na osnovu njihovog levog kraja
sort(begin(intervali), end(intervali));
// prvi interval ukljucujemo u pokrivac
int duzina_pokrivaca = intervali[0].second -
intervali[0].first;
// desni kraj poslednjeg do sada ukrupnjenog intervala
int desni_kraj = intervali[0].second;
// broj ukrupnjenih intervala
int broj_ukrupnjenih = 1;
for (int i = 1; i < n; i++)
// trenutni interval se ne sece sa trenutno poslednjim
// ukrupnjenim intervalom (leži desno od njega)
if (intervali[i].first > desni_kraj) {
// zapocinjemo novi ukrupnjeni interval
broj_ukrupnjenih++;
duzina_pokrivaca += intervali[i].second -
intervali[i].first;
desni_kraj = intervali[i].second;
} else if (intervali[i].second > desni_kraj) {
// trenutni interval prosiruje trenutno poslednji
// ukrupnjeni interval
duzina_pokrivaca += intervali[i].second - desni_kraj;
desni_kraj = intervali[i].second;
}
cout << duzina_pokrivaca << endl
<< broj_ukrupnjenih << endl;
return 0;
}Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.
Nakon što se niz cena sortira, zadatak se veoma efikasno može rešiti binarnom pretragom, primenjenu iznova na svaki budžet \(b_i\). Krenimo od sledeće invarijante. Tokom petlje održavaćemo dva pokazivača l i d, tako da su sve cene levo od pokazivača l takve da se poklon može kupiti za dati budžet, a sve cene desno od pokazivača d takve da se poklon ne može kupiti za dati budžet, dok su na pozicijama iz intervala \([l, d]\) cene koje algoritam još nije ispitao. Dakle, pretpostavimo da je stanje niza sledeće:
| l | d | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | ? | ? | ? | ? | ? | > | > | > |
U početku su sve cene nepregledane, pa interval \([l, d]\) treba da se poklopi sa celim nizom, tj. \(l\) treba inicijalizovati na \(0\), a \(d\) na \(n-1\).
U svakom koraku petlje određujemo središnju poziciju \(s\) u intervalu \([l, d]\). Da bi se smanjila mogućnost prekoračenja, tu poziciju umesto pomoću \(\left\lfloor{\frac{l+d}{2}}\right\rfloor\), možemo izračunati pomoću \(l + \left\lfloor{\frac{d-l}{2}}\right\rfloor\).
Ako se element na poziciji \(s\) uklapa u dati budžet tj. ako je cena \(c_s \leq b_i\), tada se, zbog sortiranosti, mogu priuštiti i svi pokloni na pozicijama levo od \(s\), pa invarijanta ostaje na snazi ako se \(l\) pomeri na poziciju \(s+1\).
U suprotnom, ako je \(b_i < c_s\), tada se, zbog sortiranosti, ne može prišutiti ni jedan poklon na pozicijama desno od \(s\), pa invarijanta ostaje na snazi ako se \(l\) pomeri na poziciju \(s-1\).
Petlja se izvršava dok god ima nepregledanih cena, tj. dok je interval \([l, d]\) neprazan. Kada se pretraga završi, stanje u nizu je sledeće.
| d | l | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | \(\leq\) | \(\leq\) | > | > | > | > | > | > |
Na osnovu invarijante znamo da se svaki element levo od \(l\) može priuštiti, a da se ni jedan desno od \(d\) ne može, pa se stoga traženi najvredniji poklon nalazi na poziciji \(d=l-1\). Ako su svi pokloni preskupi, krajnje vrednosti će biti \(d=-1\) i \(l=0\), pa se vraćanjem vrednosti \(d\) i u tom slučaju dobija korektan rezultat.
Funkcija se zaustavlja jer se u svakom koraku širina intervala \([l, d]\) striktno smanjuje (zahvaljujući zaokruživanju naniže prilikom određivanja središnje pozicije \(s\)).
// vraca poziciju u sortiranom nizu cene najvrednijeg poklona
// koji se moze kupiti za dati budzet ili
// -1 ako su svi pokloni preskupi
int najvredniji_poklon(const vector<int>& cene, int budzet) {
int n = cene.size();
int l = 0, d = n - 1;
while (l <= d) {
int s = l + (d - l) / 2;
if (cene[s] <= budzet)
l = s + 1;
else
d = s - 1;
}
return d;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// vraca poziciju u sortiranom nizu cene najvrednijeg poklona
// koji se moze kupiti za dati budzet ili
// -1 ako su svi pokloni preskupi
int najvredniji_poklon(const vector<int>& cene, int budzet) {
int n = cene.size();
int l = 0, d = n - 1;
while (l <= d) {
int s = l + (d - l) / 2;
if (cene[s] <= budzet)
l = s + 1;
else
d = s - 1;
}
return d;
}
int main() {
int n;
cin >> n;
vector<int> cene(n);
for (int i = 0; i < n; i++)
cin >> cene[i];
sort(begin(cene), end(cene));
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int budzet;
cin >> budzet;
int k = najvredniji_poklon(cene, budzet);
if (k == -1)
cout << -1 << endl;
else
cout << cene[k] << endl;
}
return 0;
}Napisati program koji proverava da li u strogo rastućem nizu elemenata postoji pozicija \(i\) takva da se na poziciji \(i\) nalazi vrednost \(i\) tj. da važi da je \(a_i = i\) (pozicije se broje od nule).
Sa standardnog ulaza se unosi broj \(n\) (\(0 \leq n \leq 10^5\)), a zatim i strogo rastući niz od \(n\) celih brojeva (razdvojenih razmacima).
Na standardni izlaz ispisati indeks \(i\) takav da je \(a_i = i\) ili tekst nema ako takav indeks ne postoji u nizu. Ako u nizu postoji više takvih indeksa ispisati najmanji od njih.
6 -3 -1 1 3 5 7
3
Direktan način da se zadatak reši je da se upotrebi linearna pretraga i da se pozicije proveravaju redom, od \(0\) do \(n-1\) sve dok se ne pronađe prva pozicija koja zadovoljava uslov ili dok se ne dođe do kraja niza.
Složenost linearne pretrage je \(O(n)\).
int iti_na_mestu_i(const vector<int>& a) {
for (int i = 0; i < a.size(); i++)
if (a[i] == i)
return i;
return -1;
}#include <iostream>
#include <vector>
using namespace std;
int iti_na_mestu_i(const vector<int>& a) {
for (int i = 0; i < a.size(); i++)
if (a[i] == i)
return i;
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int i = iti_na_mestu_i(a);
if (i >= 0)
cout << i << endl;
else
cout << "nema" << endl;
return 0;
}Razmotrimo niz -10 -4 1 3 4 9 11. Element -10 je manji od svoje pozicije 0 za 10. Element -4 je manji od svoje pozicije 1 za 5, element 1 je manji od svoje pozicije 2 za 1. Elementi 3 i 4 su jednaki svojim pozicijama. Element 9 je veći od svoje pozicije 5 za 4 dok je element 11 veći od svoje pozicije 6 za 5. Primećujemo određenu monotonost u ovom nizu, što nije slučajno. Pokažimo da je niz \(a_i - i\) neopadajući. Posmatarajmo dva elementa \(a_i\) i \(a_j\) na pozicijama na kojima je \(0 \leq i < j\). Pošto je niz \(a\) strogo rastući, važi da je \(a_{i+1} > a_i\), pa je \(a_{i+1} \geq a_i + 1\). Slično je \(a_{i+2} > a_{i+1}\), pa je \(a_{i+2} \geq a_{i+1} + 1 \geq a_{i} + 2\). Nastavljanjem ovakvog zaključivanja dobijamo da važi da je \(a_j \geq a_i + (j-i)\). Zato je \(a_j - j \geq a_i - i\). Ako je \(a_i = i\), tada je \(a_i - i = 0\). Rešenje, dakle, možemo odrediti tako što binarnom pretragom proverimo da li neopadajući niz \(a_i - i\) sadrži nulu i ako sadrži, tada je rešenje prva pozicija na kojoj se ta nula nalazi.
Jedan od najlakših načina da realizujemo binarnu pretragu je da upotrebimo bibliotečku funkciju. Pošto nam je potrebna prva pozicija nule u transformisanom nizu, ne možemo upotrebiti funkciju binary_search, već moramo upotrebiti funkciju lower_bound.
Složenost binarne pretrage je \(O(\log{n})\), međutim, vremenom dominira učitavanje i transformisanje niza koje zahteva \(O(n)\) koraka.
int iti_na_mestu_i(const vector<int>& a) {
int n = a.size();
// pripremamo ga za pretragu a[i] = i akko je a[i] - i = 0,
// zato umesto niza a, pretrazujemo neopadajuci niz a[i] - i
vector<int> b(n);
for (int i = 0; i < n; i++)
b[i] = a[i] - i;
// trazimo poziciju nule u transformisanom nizu
// pronalazimo poziciju prvog elementa koji je >= 0
auto it = lower_bound(b.begin(), b.end(), 0);
// ako takav element postoji i ako je jednak nuli
if (it != b.end() && *it == 0)
// pronasli smo element i izracunavamo njegovo rastojanje od
// pocetka niza
return distance(b.begin(), it);
else
// u suprotnom element ne postoji u nizu
return -1;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int iti_na_mestu_i(const vector<int>& a) {
int n = a.size();
// pripremamo ga za pretragu a[i] = i akko je a[i] - i = 0,
// zato umesto niza a, pretrazujemo neopadajuci niz a[i] - i
vector<int> b(n);
for (int i = 0; i < n; i++)
b[i] = a[i] - i;
// trazimo poziciju nule u transformisanom nizu
// pronalazimo poziciju prvog elementa koji je >= 0
auto it = lower_bound(b.begin(), b.end(), 0);
// ako takav element postoji i ako je jednak nuli
if (it != b.end() && *it == 0)
// pronasli smo element i izracunavamo njegovo rastojanje od
// pocetka niza
return distance(b.begin(), it);
else
// u suprotnom element ne postoji u nizu
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int i = iti_na_mestu_i(a);
if (i >= 0)
cout << i << endl;
else
cout << "nema" << endl;
return 0;
}Binarna pretraga se može prilagoditi i primeniti tako da se ne modifikuje niz.
Jedan mogući pokušaj implementacije prati osnovnu varijantu binarne pretrage u kojoj se traži element unutar niza. Nakon nalaženja središnjeg elementa možemo proveriti sledeće uslove.
Kada se pronađe neki element koji zadovoljava dati uslov, potrebno je proveriti da li je najmanji. Pošto drugi elementi koji zadovoljavaju dati uslov mogu biti samo neposredno uz pronađeni element, najmanji element koji zadovoljava uslov pronalazimo krećući se ulevo tj. menjajući tekući element njemu prethodnim sve dok taj prethodni element zadovoljava traženi uslov (ili dok eventualno ne dođemo do samog početka niza). Naglasimo da je ovakva implementacija binarne pretrage zapravo loša, jer u slučaju kada u nizu postoji veliki broj elemenata koji su na svom mestu, pomeranje ulevo može trajati dugo.
Složenost binarne pretrage je \(O(\log{n})\), međutim, dalja pretraga za prvim elementom koji zadovoljava uslov je u najgorem slučaju složenosti \(O(n)\), što poništava prednosti binarne pretrage. Vremenom svakako dominira učitavanje i transformisanje niza koje zahteva \(O(n)\) koraka.
int iti_na_mestu_i(const vector<int>& a) {
// sprovodimo binarnu pretragu - ako trazeni element a[k] = k
// postoji, on se nalazi u intervalu [l, d]
int l = 0, d = a.size()-1;
// dok interval [l, d] nije prazan
while (l <= d) {
// pronalazimo sredinu intervala
int s = l + (d - l) / 2;
if (a[s] < s)
// trazeni element se moze nalaziti samo desno od s
l = s + 1;
else if (a[s] > s)
// trazeni element se moze nalaziti samo levo od s
d = s - 1;
else {
// pronasli smo element na poziciji s
// mozda postoji i neki pre njega?
// Opasnost - ovo može biti linearna pretraga
while (s - 1 >= 0 && a[s - 1] == s - 1)
s = s - 1;
return s;
}
}
// nismo nasli element
return -1;
}#include <iostream>
#include <vector>
using namespace std;
int iti_na_mestu_i(const vector<int>& a) {
// sprovodimo binarnu pretragu - ako trazeni element a[k] = k
// postoji, on se nalazi u intervalu [l, d]
int l = 0, d = a.size()-1;
// dok interval [l, d] nije prazan
while (l <= d) {
// pronalazimo sredinu intervala
int s = l + (d - l) / 2;
if (a[s] < s)
// trazeni element se moze nalaziti samo desno od s
l = s + 1;
else if (a[s] > s)
// trazeni element se moze nalaziti samo levo od s
d = s - 1;
else {
// pronasli smo element na poziciji s
// mozda postoji i neki pre njega?
// Opasnost - ovo može biti linearna pretraga
while (s - 1 >= 0 && a[s - 1] == s - 1)
s = s - 1;
return s;
}
}
// nismo nasli element
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int i = iti_na_mestu_i(a);
if (i >= 0)
cout << i << endl;
else
cout << "nema" << endl;
return 0;
}Razmotrimo niz brojeva \(210, 2310, 390, 30, 510, 66, 6, 138, 46, 106, 59, 17, 23\). On je interesantan iz nekoliko razloga. Na primer, prvih pet brojeva je deljivo sa 10, a posle nijedan broj nije deljiv sa 10. Prvih deset brojeva je parno, a posle su svi brojevi neparni. Prvih osam brojeva je deljivo sa 6, a posle nijedan broj nije deljiv sa 6. Prva dva broja su deljiva sa 210, a posle nijedan broj nije deljiv sa 210, itd. Pokušaj da pronađeš još ovakvih pravilnosti. Napiši program koji za svaki uneti delilac određuje koliko brojeva je deljivo njime. Smatrati da za svaki uneti delilac važi navedena pravilnost.
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 10^5\)), a zatim u narednom redu \(n\) prirodnih brojeva (manjih od \(10^{18}\)) razdvojenih po jednim razmakom. Nakon toga se do kraja ulaza unose delioci (svaki u posebnom redu). Za svaki delilac se sigurno zna (i to nije potrebno proveravati) da se u nizu nalaze prvo brojevi koji jesu, a zatim brojevi koji nisu deljivi tim deliocem.
Za svaki uneti delilac u posebnom redu ispisati broj elemenata niza koji su njime deljivi.
13 210 2310 390 30 510 66 6 138 46 106 59 17 23 10 2 6 2 4 15
5 10 8 10 0 5
Naivno rešenje može biti zasnovano na primeni linearne pretrage (brojanju elemenata filtrirane serije) da bi se odredilo koliko u nizu postoji elemenata deljivih sa učitanim deliocem.
Ako niz ima \(n\) elemenata, a postoji \(m\) delilaca, složenost ovog rešenja je \(O(mn)\). Primetimo da ovo rešenje ni na koji način ne koristi osobinu niza da prvo idu elementi koji su deljivi, a onda elementi koji nisu deljivi datim deliocem.
Zahvaljujući interesantnoj osobini niza, zadatak efikasno može biti rešen primenom algoritma binarne pretrage prelomne tačke. Zaista, po uslovu zadatka u nizu se nalaze prvo svi elementi zadovoljavaju uslov \(P\) (deljivi su sa tekućim brojem \(k\)), a zatim svi elementi koji ne zadovoljavaju uslov \(P\) (nisu deljivi sa tekućim brojem \(k\)). Stoga se može primeniti algoritam binarne pretrage prelomne tačke.
Pošto je složenost bibliotečke funkcije binarne pretrage \(O(\log{n})\), složenost odgovora na svih \(m\) upita je \(O(m\log{n})\).
int prviKojiNijeDeljiv(const vector<long long>& a, long long k) {
int n = a.size();
int l = 0, d = n-1;
while (l <= d) {
int s = l + (d - l) / 2;
if (a[s] % k != 0)
d = s - 1;
else
l = s + 1;
}
return l;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prviKojiNijeDeljiv(const vector<long long>& a, long long k) {
int n = a.size();
int l = 0, d = n-1;
while (l <= d) {
int s = l + (d - l) / 2;
if (a[s] % k != 0)
d = s - 1;
else
l = s + 1;
}
return l;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
long long k;
while (cin >> k)
cout << prviKojiNijeDeljiv(a, k) << '\n';
return 0;
}Zadatak možemo rešiti i pomoću bibliotečkih funkcija za binarnu pretragu, međutim, potrebno je prilagoditi ih zadavanjem funkcije poređenja (kojom se kodira uslov \(P\)).
Da bismo našli prvi element koji zadovoljava neki uslov, u jeziku C++ možemo upotrebiti funkciju upper_bound, na malo neobičan način. U slučaju pretrage prelomne tačke bitni su nam samo elementi niza, a ne element koji se traži (jer zapravo ne tražimo nikakav konkretan element unutar niza). Zato kao element koji tražimo možemo navesti bilo šta (na primer, nulu). Ključno je definisati funkciju poređenja (koja se prosleđuje kao poslednji argument funkciji upper_bound), tako da vraća informaciju o tome da su elementi koji ne zadovoljavaju uslov manji od traženog, dok elementi koji zadovoljavaju uslov nisu manji od traženog. Funkcija poređenja, dakle, treba samo da analizira svoj drugi element i da vrati informaciju o tome da li on zadovoljava uslov (u našem primeru, tražimo prvi element koji nije deljiv brojem \(d\) i to je uslov koji se proverava u sklopu funkcije poređenja).
Mogli bismo upotrebiti i funkciju lower_bound, ali bi tada u funkciji poređenja bilo potrebno razmeniti redosled argumenata (njoj je tražena vrednost uvek drugi argument) i negirati uslov.
Pošto je složenost bibliotečke funkcije binarne pretrage \(O(\log{n})\), složenost odgovora na svih \(m\) upita je \(O(m\log{n})\).
int prviKojiNijeDeljiv(const vector<long long>& a, long long d) {
auto it = upper_bound(begin(a), end(a), 0,
[d](long long _, long long x) {
return x % d != 0;
});
return distance(begin(a), it);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prviKojiNijeDeljiv(const vector<long long>& a, long long d) {
auto it = upper_bound(begin(a), end(a), 0,
[d](long long _, long long x) {
return x % d != 0;
});
return distance(begin(a), it);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
long long d;
while (cin >> d)
cout << prviKojiNijeDeljiv(a, d) << '\n';
return 0;
}Aplikacije za slanje mejlova čuvaju ranije korišćene mejl adrese a onda pomažu korisnicima tako što na osnovu njih dopunjavaju započet unos nove mejl adrese (tzv. opcija automatskog dopunjavanja, engl. aucomplete). Napisati program koji efikasno implementira ovu funkcionalnost.
Sa standardnog ulaza se učitava broj mejl adresa \(n\) (\(1 \leq n \leq 10^5\)), a zatim u \(n\) narednih redova po jedna mejl adresa. Nakon toga se unosi broj započetnih mejl adresa koje treba dopuniti \(m\) (\(1 \leq m \leq 10^5\)), a nakon toga i tih \(m\) započetih mejl adresa.
Na stadardni izlaz za svaku započetu mejl adresu ispisati broj mejl adresa koje je dopunjavaju.
9 pera@gmail.com lana123@yahoo.com andrija@yahoo.com laza@gmail.com ana.ilic@mail.ru lazica@hotmail.com milica@gmail.com larisa@zoho.com anaconda@python.org 3 laz milica@ a
2 1 3
Na primer, početak laz dopunjavaju adrese laza@gmail.com i lazica@hotmail.com.
Zadatak se može rešiti tako što se za svaki prefiks adrese linearnom pretragom celog niza pronađu one adrese koje počinju tim prefiksom.
Ako postoji \(n\) elemenata niza adresa, složenost linearne pretrage je \(O(n)\), pa ako se ispituje \(m\) prefiksa, ukupna složenost je \(O(mn)\).
Zadatak se efikasnije može rešiti tako što se adrese sortiraju, a zatim se za svaki prefiks binarnom pretragom pronalaze adrese koje počinju tim prefiksom. Prva takva adresa je najmanja adresa (u leksikografskom poretku) koja je veća ili jednaka od unetog prefiksa. Iako se može pomisliti da se nakon njenog pronalaska, ostale adrese mogu pronaći u petlji koja nastavlja dalje sve dok adrese počinju tim prefiksom, to rešenje je potencijalno neefikasno (jer može biti puno takvih adresa). Zato je bolje novom binarnom pretragom odrediti prvu adresu koja ne počinje tim prefiksom, što se može uraditi tako što se poslednji karakter tog prefiksa uveća i pronađe pozicija adrese koja je veća ili jednaka od tako transformisanog prefiksa.
Ako postoji \(n\) elemenata niza adresa, složenost inicijalnog sortiranja je \(O(n \log{n})\), a složenost svake od ove dve binarne pretrage je \(O(\log{n})\), pa ako se ispituje \(m\) prefiksa, ukupna složenost je \(O((n+m)\log{n})\).
// za dati sortiran niz mejlova odredjuju se interval
// [donja_granica, gornja_granica) u kom se nalaze svi mejlovi
// koji pocinju datim prefiksom
pair<int, int> dopunePrefiksaMejla(const vector<string>& mejlovi,
const string& prefiks) {
// odredjujemo poziciju prvog mejla koji je
// veci ili jednak od datog prefiksa
auto lb1 = lower_bound(begin(mejlovi), end(mejlovi), prefiks);
int donja_granica = distance(begin(mejlovi), lb1);
// odredjujemo sledeci prefiks uvecavanjem poslednjeg slova
// datog prefiksa
// (na primer, za dati prefiks abc sledeci prefiks je abd)
string sledeci_prefiks = prefiks;
sledeci_prefiks.back()++;
// odredjujemo poziciju prvog mejla koji je veci ili jednak
// od sledeceg prefiksa
auto lb2 = lower_bound(begin(mejlovi), end(mejlovi),
sledeci_prefiks);
int gornja_granica = distance(begin(mejlovi), lb2);
return make_pair(donja_granica, gornja_granica);
}#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
// za dati sortiran niz mejlova odredjuju se interval
// [donja_granica, gornja_granica) u kom se nalaze svi mejlovi
// koji pocinju datim prefiksom
pair<int, int> dopunePrefiksaMejla(const vector<string>& mejlovi,
const string& prefiks) {
// odredjujemo poziciju prvog mejla koji je
// veci ili jednak od datog prefiksa
auto lb1 = lower_bound(begin(mejlovi), end(mejlovi), prefiks);
int donja_granica = distance(begin(mejlovi), lb1);
// odredjujemo sledeci prefiks uvecavanjem poslednjeg slova
// datog prefiksa
// (na primer, za dati prefiks abc sledeci prefiks je abd)
string sledeci_prefiks = prefiks;
sledeci_prefiks.back()++;
// odredjujemo poziciju prvog mejla koji je veci ili jednak
// od sledeceg prefiksa
auto lb2 = lower_bound(begin(mejlovi), end(mejlovi),
sledeci_prefiks);
int gornja_granica = distance(begin(mejlovi), lb2);
return make_pair(donja_granica, gornja_granica);
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<string> mejlovi(n);
for (int i = 0; i < n; i++)
cin >> mejlovi[i];
sort(begin(mejlovi), end(mejlovi));
int m;
cin >> m;
vector<string> prefiksi(m);
for (int i = 0; i < m; i++) {
string prefiks;
cin >> prefiks;
const auto& [a, b] = dopunePrefiksaMejla(mejlovi, prefiks);
cout << b - a << endl;
}
return 0;
}Ako je \(s\) niska, onda neka \(s^n\) označava nisku koja se dobija ako se svako slovo ponovi \(n\) puta (npr. \((xyz)^3\) je \(xxxyyyzzz\)). Napiši program koji određuje najveći broj \(n\) takav da je \(s^n\) podniz date niske \(t\) (to znači da se sva slova niske \(s^n\) javljaju u niski \(t\), u istom redosledu kao u \(s^n\), ali ne obavezno uzastopno).
U prvom redu standardnog ulaza nalazi se niska \(s\), a u drugom niska \(t\).
Na standardni izlaz napiši traženi broj \(n\).
xyz xaxxybyxyxzyzzb
3
Definisaćemo funkciju kojom proveravamo da li je \(s^n\) podniz niske \(t\). Jedan način je da eksplicitno formiramo nisku \(s^n\) i da primenimo algoritam provere podniske. Malo bolje rešenje je da se algoritam modifikuje tako da se izbegne efektivno kreiranje niske \(s^n\). Funkcija provere prima nisku \(s\), broj \(n\) i nisku \(t\), a zatim svaki od karaktera iz \(s\) traži \(n\) puta unutar niske \(t\).
Kada na raspolaganju imamo funkciju za proveru, tada optimalnu vrednost \(n\) možemo naći linearnom pretragom. Ključna opaska je da ako \(s^n\) nije podniz \(t\) za neko \(n\), onda \(s^k\) nije podniz \(t\) ni za jedno \(k \geq n\). Zato ćemo stepen uvećavati krenuvši od \(1\) sve dok ne naiđemo na prvu vrednost \(n\) za koju \(s^n\) nije podniz \(t\) i tada ćemo znati da je optimalna vrednost \(n-1\).
Provera da li je niska \(s^n\) podniz niske \(t\) vrši se u linearnom vremenu u odnosu na zbir dužina niske. Ako je \(T\) dužina niske \(t\), vreme za jednu proveru je \(O(T)\). Provere se vrše sve dok se ne nađe optimalno \(n\). Ono najviše može biti \(\left\lfloor{\frac{T}{S}}\right\rfloor\), gde je \(S\) dužina niske \(s\) pa je složenost \(O(\frac{T^2}{S})\).
bool jeMucajuciPodniz(const string& podniz, const string& niz, int n) {
int i = 0;
for (char c : podniz) {
for (int k = 0; k < n; k++) {
while (i < niz.size() && niz[i] != c)
i++;
if (i == niz.size())
return false;
i++;
}
}
return true;
}
int najduziMucajuciPodniz(const string& podniz, const string& niz) {
int d = 1;
while (jeMucajuciPodniz(podniz, niz, d))
d++;
return d - 1;
}#include <iostream>
#include <string>
using namespace std;
bool jeMucajuciPodniz(const string& podniz, const string& niz, int n) {
int i = 0;
for (char c : podniz) {
for (int k = 0; k < n; k++) {
while (i < niz.size() && niz[i] != c)
i++;
if (i == niz.size())
return false;
i++;
}
}
return true;
}
int najduziMucajuciPodniz(const string& podniz, const string& niz) {
int d = 1;
while (jeMucajuciPodniz(podniz, niz, d))
d++;
return d - 1;
}
int main() {
string podniz;
string niz;
cin >> podniz >> niz;
cout << najduziMucajuciPodniz(podniz, niz) << endl;
return 0;
}Činjenica da postoji određeni oblik monotonosti u problemu, nam omogućava da traženu optimalnu vrednost nađemo binarnom pretragom. Važi da ako \(s^n\) nije podniz \(t\) za neko \(n\), onda \(s^k\) nije podniz \(t\) ni za jedno \(k \geq n\), a da ako je \(s^n\) podniz \(t\) za neko \(n\), onda je \(s^k\) podniz \(t\) za svako \(k \leq n\). Zato se sa porastom \(n\) javljaju se prvo one vrednosti za koje uslov važi, nakon koji idu vrednosti za koje uslov ne važi.
Sigurni smo da se optimalna vrednost nalazi u intervalu od \(0\) pa do \(\left\lfloor{\frac{|t|}{|s|}}\right\rfloor\). Binarnom pretragom pronalazimo prelomnu tačku, tj. najmanju vrednost \(n\) takvu da \(s^n\) nije podniz \(t\). Primetimo da u ovom slučaju ne pretražujemo vrednosti u nekom nizu, već je niz potencijalnih vrednosti \(n\) koji se pretražuje samo implicitan, pa binarnu pretragu implementiramo ručno.
Provera da li je niska \(s^n\) podniz niske \(t\) vrši se u linearnom vremenu u odnosu na zbir dužina niske. Ako je \(T\) dužina niske \(t\), vreme za jednu proveru je \(O(T)\). Interval koji se pretražuje je \([0, \frac{T}{S}]\), gde je \(S\) dužina niske \(s\), pa je složenost \(O(T \log{\frac{T}{S}})\).
int najduziMucajuciPodniz(const string& podniz, const string& niz) {
int l = 0, d = niz.size() / podniz.size();
while (l <= d) {
int s = l + (d - l) / 2;
if (jeMucajuciPodniz(podniz, niz, s))
l = s + 1;
else
d = s - 1;
}
return d;
}#include <iostream>
#include <string>
using namespace std;
bool jeMucajuciPodniz(const string& podniz, const string& niz, int n) {
int i = 0;
for (char c : podniz) {
for (int k = 0; k < n; k++) {
while (i < niz.size() && niz[i] != c)
i++;
if (i == niz.size())
return false;
i++;
}
}
return true;
}
int najduziMucajuciPodniz(const string& podniz, const string& niz) {
int l = 0, d = niz.size() / podniz.size();
while (l <= d) {
int s = l + (d - l) / 2;
if (jeMucajuciPodniz(podniz, niz, s))
l = s + 1;
else
d = s - 1;
}
return d;
}
int main() {
string podniz;
string niz;
cin >> podniz >> niz;
cout << najduziMucajuciPodniz(podniz, niz) << endl;
return 0;
}Grafički dizajner je preuredio nekoliko slova u jednom fontu i želi da svoje promene prikaže klijentu. U dugačkom tekstu je potrebno da odabere najkraći deo (segment uzastopnih slova) koji sadrži sva slova koja je promenio.
U prvoj liniji standardnog ulaza nalazi se tekst (jednostavnosti radi pretpostavimo da je sastavljen samo od malih slova engleskog alfabeta) čija je dužina najviše \(10^5\) karaktera. U drugoj liniji se nalazi skup slova (opet, pretpostavimo malih slova engleskog alfabeta) koje je dizajner promenio (slova su napisana jedno do drugog, bez razmaka i bez ponavljanja).
Na standardni izlaz ispisati jedan ceo broj koji predstavlja dužinu najkraćeg dela teksta koji sadrži sve karaktere datog skupa. Ako takav deo teksta ne postoji, ispisati nema.
dobardansvimakakoste arnk
10
ababababab abc
nema
Najdirektniji algoritam bio bi da se razmatraju sve podniske (one su određene indeksima \(0 \leq i \leq j < n\)), da se za svaku od njih proveri da li je ispravna tj. da li sadrži sve karaktere iz skupa \(S\) i da se među svim ispravnim podniskama pronađe najkraća. Ovakvu pretragu grubom silom je veoma jednostavno implementirati.
// proverava da li niska na pozicijama [i, j] sadrzi karakter c
bool podniskaSadrziKarakter(const string& niska,
int i, int j, char c) {
for (int k = i; k <= j; k++)
if (niska[k] == c)
return true;
return false;
}
// provera da li niska na pozicijama [i, j] sadrzi sve karaktere
// iz niske S
bool podniskaSadrziSveKaraktere(const string& niska,
int i, int j, const string& S) {
for (char c : S)
if (!podniskaSadrziKarakter(niska, i, j, c))
return false;
return true;
}
// "beskonacno"
const int INF = numeric_limits<int>::max();
// pronalazi duzinu najkrace podniske koja sadrzi sve karaktere
// iz skupa S
int duzinaPodniske(const string& niska, const string& S) {
// duzina najkrace do sada pronadjene niske koja sadrzi sve
// karaktere iz S
int min_duzina = INF;
// obradjujemo sve pozicije pocetka podniske
for (int i = 0; i < niska.size(); i++) {
// preskacemo karaktere koji nisu u skupu S
// jer najkraca podniska mora da pocne sa karakterom iz S
if (S.find(niska[i]) == string::npos) continue;
// obradjujemo sve pozicije kraja podniske koja pocinje na
// poziciji i
for (int j = i; j < niska.size(); j++)
if (podniskaSadrziSveKaraktere(niska, i, j, S)) {
int duzina = j - i + 1;
if (duzina < min_duzina)
min_duzina = duzina;
break;
}
}
return min_duzina;
}#include <iostream>
#include <string>
#include <limits>
using namespace std;
// proverava da li niska na pozicijama [i, j] sadrzi karakter c
bool podniskaSadrziKarakter(const string& niska,
int i, int j, char c) {
for (int k = i; k <= j; k++)
if (niska[k] == c)
return true;
return false;
}
// provera da li niska na pozicijama [i, j] sadrzi sve karaktere
// iz niske S
bool podniskaSadrziSveKaraktere(const string& niska,
int i, int j, const string& S) {
for (char c : S)
if (!podniskaSadrziKarakter(niska, i, j, c))
return false;
return true;
}
// "beskonacno"
const int INF = numeric_limits<int>::max();
// pronalazi duzinu najkrace podniske koja sadrzi sve karaktere
// iz skupa S
int duzinaPodniske(const string& niska, const string& S) {
// duzina najkrace do sada pronadjene niske koja sadrzi sve
// karaktere iz S
int min_duzina = INF;
// obradjujemo sve pozicije pocetka podniske
for (int i = 0; i < niska.size(); i++) {
// preskacemo karaktere koji nisu u skupu S
// jer najkraca podniska mora da pocne sa karakterom iz S
if (S.find(niska[i]) == string::npos) continue;
// obradjujemo sve pozicije kraja podniske koja pocinje na
// poziciji i
for (int j = i; j < niska.size(); j++)
if (podniskaSadrziSveKaraktere(niska, i, j, S)) {
int duzina = j - i + 1;
if (duzina < min_duzina)
min_duzina = duzina;
break;
}
}
return min_duzina;
}
int main() {
string niska, S;
getline(cin, niska);
getline(cin, S);
// prijavljujemo rezultat
int min_duzina = duzinaPodniske(niska, S);
if (min_duzina != INF)
cout << min_duzina << endl;
else
cout << "nema" << endl;
}Proverava se \(O(n^2)\) podniski, i za svaku se vrži \(m\) linearnih provera, pa se može pokazati da je složenost je \(O(n^3\cdot m)\) gde je \(n\) dužina teksta, a \(m\) broj karaktera u skupu \(S\). Parametar \(m\) ima malu vrednost, ali dimenzija \(n\) može biti velika, pa je ovaj algoritam veoma neefikasan.
Kada podniska određena pozicijama \(i\) i \(j\) sadrži sve karaktere iz skupa \(S\), onda i sve podniske određene većim vrednostima \(j\) takođe sadrže sve karaktere iz tog skupa, a za njih znamo da su duže i nema potrebe razmatrati ih (vršimo odsecanje u pretrazi).
Primer 3.A.6. Na primer, ako se unutar niske xCxxBxxBxxAxxBxxCxxxxBxAxAxCxxxBx traži podniska u kome se javljaju slova iz skupa ABC. Nakon pronalaska niske CxxBxxBxxA, koja sadrži sve potrebne karaktere, nema potrebe razmatrati njena proširenja nadesno (na primer, podnisku CxxBxxBxxAxxB).
Dakle prva pronađena ispravna podniska koja počinje na poziciji \(i\) ujedno je i najkraća ispravna podniska pronađena na toj poziciji. Zato je odmah nakon pronalaska prve ispravne pondiske i ažuriranja vrednosti najmanje dužine moguće prekinuti unutrašnju petlju (naredbom break).
Ova optimizacija ne popravlja asimptotsku složenost najgoreg slučaja (na primer, u slučajevima kada ne postoji tražena podniska), ali u mnogim slučajevima može dovesti do ubrzanja.
Primetimo da tražena najkraća podniska mora da počinje i da se završava karakterom iz skupa \(S\) (reći ćemo da su samo ti karakteri relevantni). U suprotnom bi karakteri na početku i na kraju podniske koji nisu u skupu \(S\) mogli da budu uklonjeni čime bi se dobila kraća podniska koja bi i dalje sadržala sve karaktere iz skupa \(S\). Takođe, prilikom provere da li određena podniska sadrži sve karaktere iz \(S\), potrebno je analizirati samo one njene pozicije na kojima su karakteri iz \(S\). Zato ćemo u fazi pretprocesiranja samo izgraditi niz pozicija relevantnih karaktera u niski (reći ćemo da su to relevantne pozicije) i zatim ćemo razmatrati samo podniske koji počinju i završavaju se na pozicijama unutar tog niza (na taj način vršimo odsecanje u pretrazi).
Ako se provera da li je pozicija relevantna vrši linearnom pretragom niske S, Vreme potrebno za izgradnju niza relevantnih pozicija je \(O(n\cdot m)\) (pošto je \(m\) veoma mali broj, ovo je praktično linearno tj. \(O(n)\), a može se sniziti i na \(O(m + n)\) ako bi se skup \(S\) predstavio svojom karakterističnom funkcijom – asocijativnim nizom 26 logičkih vrednosti).
Iako se ovim ne snižava složenost najgoreg slučaja (na primer, kada su svi karakteri niske u skupu \(S\)), u slučaju da postoji značajan broj karaktera u tekstu koji nisu u skupu \(S\), pretraga se može ubrzati.
Proveru da li se svi karakteri iz skupa \(S\) javljaju unutar podniske imeđu dve relevantne pozicije \(i\) i \(j\) možemo izvršiti tako što odredimo skup svih relevantnih karaktera na svim relevantnim pozicijama niske između \(i\) i \(j\) (uključujući i njih). Svi karakteri iz tako napravljenog skupa će biti u skupu \(S\) (jer razmatramo samo relevantne pozicije), pa je umesto ispitivanja da li je taj skup jednak skupu \(S\), dovoljno ispitati samo da li ima isti broj elemenata kao \(S\) (a pošto niska \(S\) po uslovima zadatka nema ponovljenih karaktera, broj elemenata skupa \(S\) jednak je dužini niske \(S\)). Izgradnju skupa relevantnih karaktera koji se pojavljuju unutar tekuće niske \(S\) možemo vršiti inkrementalno, tako što prilikom svakog povećanja \(j\), tj. prilikom prelaska na novu relevantnu poziciju \(j\) dodamo karakter na toj poziciji u taj skup, što zahteva samo konstantno vreme (ako skup karaktera predstavimo nizom ili bibliotečkim skupom, jer je ukupan broj mogućih karaktera samo 26).
Skup karaktera u jeziku C++ možemo predstaviti preko niza 26 logičkih vrednosti i dodatnog brojača koji predstavlja broj karaktera u skupu. Ipak, elegantnija implementacija se dobija ako upotrebi bibliotečka implementacija skupa (set ili unordered_set).
// "beskonacno"
const int INF = numeric_limits<int>::max();
// pronalazi duzinu najkrace podniske koja sadrzi sve karaktere iz skupa S
int duzinaPodniske(const string& niska, const string& S) {
// pozicije unutar niske na kojima su karakteri iz skupa karakteri
vector<int> relevantne_pozicije;
for (int i = 0; i < niska.size(); i++)
// ako se niska[i] nalazi u skupu karakteri
if (S.find(niska[i]) != string::npos)
// zapamti njegovu poziciju i
relevantne_pozicije.push_back(i);
int min_duzina = INF;
for (auto i = relevantne_pozicije.begin(); i != relevantne_pozicije.end(); i++) {
// relevantni karakteri koje sadrzi trenutna podniska
set<char> karakteri_podniske;
for (auto j = i; j != relevantne_pozicije.end(); j++) {
karakteri_podniske.insert(niska[*j]);
if (karakteri_podniske.size() == S.size()) {
int duzina = *j - *i + 1;
if (duzina < min_duzina)
min_duzina = duzina;
break;
}
}
}
return min_duzina;
}#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <set>
using namespace std;
// "beskonacno"
const int INF = numeric_limits<int>::max();
// pronalazi duzinu najkrace podniske koja sadrzi sve karaktere iz skupa S
int duzinaPodniske(const string& niska, const string& S) {
// pozicije unutar niske na kojima su karakteri iz skupa karakteri
vector<int> relevantne_pozicije;
for (int i = 0; i < niska.size(); i++)
// ako se niska[i] nalazi u skupu karakteri
if (S.find(niska[i]) != string::npos)
// zapamti njegovu poziciju i
relevantne_pozicije.push_back(i);
int min_duzina = INF;
for (auto i = relevantne_pozicije.begin(); i != relevantne_pozicije.end(); i++) {
// relevantni karakteri koje sadrzi trenutna podniska
set<char> karakteri_podniske;
for (auto j = i; j != relevantne_pozicije.end(); j++) {
karakteri_podniske.insert(niska[*j]);
if (karakteri_podniske.size() == S.size()) {
int duzina = *j - *i + 1;
if (duzina < min_duzina)
min_duzina = duzina;
break;
}
}
}
return min_duzina;
}
int main() {
string niska, S;
getline(cin, niska);
getline(cin, S);
int duzina = duzinaPodniske(niska, S);
if (duzina != INF)
cout << duzina << endl;
else
cout << "nema" << endl;
return 0;
}Složenost algoritma koji za svaku poziciju \(i\) određuje najkraću ispravnu podnisku koja počinje na poziciji \(i\) uz sve navedene optimizacije je \(O(n^2)\).
Zahvaljujući inkrementalnosti, proveru da li za datu dužinu podniske \(k\) postoji neka podniska koja sadrži sve date karaktere možemo uraditi u linearnom vremenu \(O(n)\), u jednom prolasku kroz niz. Koristićemo tehniku pokretnog prozora i prilikom prelaska sa jedne na narednu podnisku, iz skupa ćemo uklanjati prvi karakter tekuće podniske i dodavaćemo poslednji karakter nove podniske. Ovo dodatno možemo ubrzati (doduše ne asimptotski) ako je skup karaktera mali, tako što ćemo prolaziti samo kroz pozicije originalne niske na kojima znamo da se javljaju karakteri iz skupa.
Skup karaktera iz \(S\) unutar tekuće podniske ćemo predstaviti pomoću preslikavanja karaktera u njihov broj pojavljivanja. Najjednostavnije je upotrebiti bibliotečku implementaciju mape tj. rečnika, jer nam ona pruža mogućnost efikasnog određivanja broja karaktera iz \(S\) unutar podniske (podniska je ispravna tj. sadrži sve potrebne karaktere ako i samo ako je broj karaktere iz \(S\) koje sadrži jednak broju elemenata skupa \(S\)).
Nakon toga, najmanju dužinu \(k\) možemo naći tehnikom binarne pretrage tako što nađemo najmanju vrednost \(k\) za koju važi neki uslov. Bitno je naglasiti da problem zadovoljava svojstvo monotonosti tj. da ako za neko \(k\) ne postoji podniska dužine \(k\) koja sadrži sve karaktere skupa, onda takva podniska ne postoji ni za jedno manje \(k\) tj. da ako za neko \(k\) postoji takva podniska, onda ona postoji i za svako veće \(k\).
// provera da li postoji podniska niske niska duzine k koja sadrzi sve
// karaktere iz S
bool postojiPodniska(const string& niska, const string& S, int k) {
map<char, int> karakteri;
for (int i = 0; i < niska.length(); i++) {
if (i >= k && S.find(niska[i-k]) != string::npos)
if (--karakteri[niska[i-k]] == 0)
karakteri.erase(niska[i-k]);
if (S.find(niska[i]) != string::npos) {
karakteri[niska[i]]++;
if (karakteri.size() == S.size())
return true;
}
}
return false;
}
// pronalazi duzinu najkrace podniske koja sadrzi sve date karaktere
int duzinaPodniske(const string& niska, const string& karakteri) {
// binarnom pretragom odredjujemo najmanju duzinu k takvu da u T
// postoji podniska duzine k koja sadrzi sve karaktere skupa S
int l = 1, d = niska.length();
while (l <= d) {
int s = l + (d - l) / 2;
if (postojiPodniska(niska, karakteri, s))
d = s - 1;
else
l = s + 1;
}
return l;
}#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
// provera da li postoji podniska niske niska duzine k koja sadrzi sve
// karaktere iz S
bool postojiPodniska(const string& niska, const string& S, int k) {
map<char, int> karakteri;
for (int i = 0; i < niska.length(); i++) {
if (i >= k && S.find(niska[i-k]) != string::npos)
if (--karakteri[niska[i-k]] == 0)
karakteri.erase(niska[i-k]);
if (S.find(niska[i]) != string::npos) {
karakteri[niska[i]]++;
if (karakteri.size() == S.size())
return true;
}
}
return false;
}
// pronalazi duzinu najkrace podniske koja sadrzi sve date karaktere
int duzinaPodniske(const string& niska, const string& karakteri) {
// binarnom pretragom odredjujemo najmanju duzinu k takvu da u T
// postoji podniska duzine k koja sadrzi sve karaktere skupa S
int l = 1, d = niska.length();
while (l <= d) {
int s = l + (d - l) / 2;
if (postojiPodniska(niska, karakteri, s))
d = s - 1;
else
l = s + 1;
}
return l;
}
int main() {
string niska, karakteri;
getline(cin, niska);
getline(cin, karakteri);
int minDuzina = duzinaPodniske(niska, karakteri);
if (minDuzina <= niska.length())
cout << minDuzina << endl;
else
cout << "nema" << endl;
return 0;
}Binarnom pretragom se pretražuje interval \([1, n]\), gde je \(n\) dužina niske, pa se provera da li postoji podniska neke fiksne koja sadrži sva potrebna slova vrši najviše \(\log{n}\) puta. Ta provera se vrši jednim prolaskom kroz nisku. U svakom koraku vrši se linearna pretraga niske kojom je određen skup karaktera i vrše se operacije nad mapom tj. rečnikom u kom su ključevi karakteri iz skupa \(S\). Ako pretpostavimo da se operacije nad mapom izvršavaju u logaritamskoj složenosti, složenost jedne pretrage je zato \(n\cdot m \cdot \log{m}\), gde je \(m\) broj karaktera u \(S\). Pošto je \(m\) veoma mali broj, faktor \(m\log{m}\) možemo smatrati i konstantom i ukupnu složenost grubo oceniti sa \(O(n\log{n})\). Da je \(m\) veće, složenost bi se mogla popravljati time što bi se provera pripadnosti karaktera skupu \(S\) vršila na efikasniji način (na primer, predstavljanjem \(S\) pomoću bibilotečkih kolekcija za predstavljanje skupa ili pomoću niza logičkih vrednosti). Takođe je moguće unapred odrediti pozicije karaktera iz \(S\) unutar niske (što ne utiče na asimptotsku složenost najgoreg slučaja, jer svi karakteri u \(T\) mogu pripadati \(S\), ali može dosta smanjiti faktor \(n\) u svakoj pojedinačnoj proveri).
Računarski sistem raspoređuje poslove na dva procesora. Za svaki od procesora su poznati poslovi koji se na njemu mogu rasporediti i za svaki od poslova je poznato očekivano vreme izvršavanja. U cilju dobre balansiranosti sistema potrebno je rasporediti ona dva posla čije je vreme izvršavanja što sličnije. Napisati program koji to radi.
Sa standardnog ulaza se učitavaju dva niza koji predstavljaju očekivana vremena izvršavanja poslova na prvom i na drugom procesoru. Za svaki niz je zadata prvo dužina \(n\) (\(1 \leq m \leq 50000\)), a zatim u drugom redu \(n\) celih brojeva (celi brojevi između \(1\) i \(2\cdot 10^9\) razdvojeni po jednim razmakom).
Na standardni izlaz ispisati najmanju vrednost razlike dva posla koja će biti raspoređena.
5 4680 2120 7940 11530 17820 4 850 13420 5770 6300
1090
Najmanja razlika se postiže kada se na prvom procesoru pokrene proces čije je vreme izvršavanja 4680, a na drugom čije je vreme izvršavanja 5770.
Jedan mogući pristup je da odredimo razliku (preciznije, apsolutnu vrednost razlike) u između svakog elementa prvog i svakog elementa drugog niza, pa od tih razlika nađemo najmanju.
Složenost odgovara broju parova i procenjuje se kao \(O(m\cdot n)\), gde je \(m\) broj elemenata prvog, a \(n\) broj elemenata drugog niza.
// najmanja razlika a1[i] - a2[j]
int NajmanjaRazlika(const vector<int>& a1, const vector<int>& a2) {
int minRazlika = numeric_limits<int>::max();
for (int x1 : a1)
for (int x2: a2)
minRazlika = min(minRazlika, abs(x1 - x2));
return minRazlika;
}#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;
// najmanja razlika a1[i] - a2[j]
int NajmanjaRazlika(const vector<int>& a1, const vector<int>& a2) {
int minRazlika = numeric_limits<int>::max();
for (int x1 : a1)
for (int x2: a2)
minRazlika = min(minRazlika, abs(x1 - x2));
return minRazlika;
}
int main() {
ios_base::sync_with_stdio(false);
int n1; cin >> n1;
vector<int> a1(n1);
for (int i = 0; i < n1; i++)
cin >> a1[i];
int n2; cin >> n2;
vector<int> a2(n2);
for (int i = 0; i < n2; i++)
cin >> a2[i];
cout << NajmanjaRazlika(a1, a2) << endl;
return 0;
}Efikasniji pristup je da se nizovi najpre sortiraju, a da se zatim istovremeno prolazi kroz oba niza, računajući razliku tekućih elemenata i napredujući u onom nizu u kojem je vrednost trenutno manja, kao kod klasičnog algoritma objedinjavanja dva sortirana niza. Usput se, naravno, po potrebi ažurira najmanja zabeležena razlika. Kada se stigne do kraja bilo kojeg niza, postupak je završen i najmanja zabeležena razlika je tada i ukupno najmanja.
Zaista, pošto su nizovi sortirani, kada se uporede početni elementi iz oba niza, onaj koji je manji od njih nema potrebe upoređivati sa ostalim elementima niza kome on ne pripada, jer će razlika moći biti samo veća (jer je taj niz sortiran). Na taj način vršimo odsecanje, čime dobijamo na efikasnosti. Taj element onda možemo izbaciti iz daljeg razmatranja tako što ćemo u nizu u kom se on nalazi preći na sledeći element. U specijalnom slučaju kada su početni elementi oba niza jednaki, razlika je jednaka nuli, što je najmanja moguća razlika, pa nema potrebe vršiti dalju analizu.
Primer 3.A.7. Na primer, neka su nakon sortiranja vrednosti jednake sledećim.
1 14 28 33 45 8 21 22 41 56 68
Možemo zaključiti da je najmanja moguća razlika jednaka 4 (za brojeve 41 i 45).
Složenošću dominira sortiranje, koje se izvršava u vremenu \(O(m\log{m} + n\log{n})\). Nakon sortiranja, prolazak sa dva pokazivača se izvršava u vremenu \(O(m+n)\).
// najmanja razlika a1[i] - a2[j]
int NajmanjaRazlika(const vector<int>& a1, const vector<int>& a2) {
// pravimo sortirane kopije dva niza
auto a1s = a1;
sort(begin(a1s), end(a1s));
auto a2s = a2;
sort(begin(a2s), end(a2s));
// algoritmom objedinjavanja odredjujemo najmanju razliku
int i1 = 0, i2 = 0;
int minRazlika = numeric_limits<int>::max();
while (i1 < a1s.size() && i2 < a2s.size())
if (a1s[i1] <= a2s[i2]) {
minRazlika = min(minRazlika, a2s[i2] - a1s[i1]);
i1++;
} else {
minRazlika = min(minRazlika, a1s[i1] - a2s[i2]);
i2++;
}
return minRazlika;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
// najmanja razlika a1[i] - a2[j]
int NajmanjaRazlika(const vector<int>& a1, const vector<int>& a2) {
// pravimo sortirane kopije dva niza
auto a1s = a1;
sort(begin(a1s), end(a1s));
auto a2s = a2;
sort(begin(a2s), end(a2s));
// algoritmom objedinjavanja odredjujemo najmanju razliku
int i1 = 0, i2 = 0;
int minRazlika = numeric_limits<int>::max();
while (i1 < a1s.size() && i2 < a2s.size())
if (a1s[i1] <= a2s[i2]) {
minRazlika = min(minRazlika, a2s[i2] - a1s[i1]);
i1++;
} else {
minRazlika = min(minRazlika, a1s[i1] - a2s[i2]);
i2++;
}
return minRazlika;
}
int main() {
ios_base::sync_with_stdio(false);
int n1; cin >> n1;
vector<int> a1(n1);
for (int i = 0; i < n1; i++)
cin >> a1[i];
int n2; cin >> n2;
vector<int> a2(n2);
for (int i = 0; i < n2; i++)
cin >> a2[i];
cout << NajmanjaRazlika(a1, a2) << endl;
return 0;
}Napiši program koji određuje na koliko načina možemo da odaberemo dva elementa niza tako da im je razlika jednaka datom broju \(r\).
Sa standardnog ulaza se unosi prvo pozitivan prirodan broj \(r\), u narednom redu dužina niza \(n\) (\(1 \leq n \leq 50000\)), a nakon toga elementi niza.
Na standardni izlaz ispiši broj parova elemenata niza čija je razlika jednaka \(r\).
2350 5 15745 18095 15745 16234 13395
4
Moguće je napraviti parove od prvog i drugog, od prvog i petog, od drugog i trećeg i od trećeg i petog elementa niza.
Naivan način da se zadatak reši je da se ispitaju svi uređeni parovi elemenata niza i da se prebroje oni čija je razlika jednaka traženoj. Pošto uređenih parova učenika ima \(n^2\), složenost ovakvog algoritma je \(O(n^2)\).
Zadatak možemo rešiti tehnikom dva pokazivača. Niz mora biti sortiran, a oba pokazivača se kreću sleva nadesno. Jednostavnosti radi, pretpostavimo prvo da u nizu nema duplikata.
Primer 3.A.8. Prikažimo kako bi algoritam radio na primeru određivanja broja elemenata čija je razlika 8 u narednom nizu.
1 3 7 8 11 14 16 30 38
Krećemo od para 1 3. Pošto je razlika manja od tražene element 3 ne može biti umanjenik, pa povećavamo umanjenik na 7.
Analiziramo par 1 7. Situacija je opet ista, pa opet povećavamo umanjenik na 8. Naime, pomeranjem umanjioca sa 1 na 3, razlika bi se samo smanjila, pa 7 zaista ne može biti umanjenik.
Analiziramo par 1 8. I tu je situacija ista, pa opet povećavamo umanjenik na 11 (ponovo zaključujemo da se pomeranjem umanjioca sa 1 nadesno, na 3 ili 7 razlika smanjuje, pa 8 zaista ne može biti umanjenik).
Analiziramo par 1 11. Ovaj put je razlika veća od tražene. Stoga možemo zaključiti da 1 ne može biti umanjilac (daljim pomeranjem umanjenika nadesno, razlika bi se samo povećala). Stoga prelazimo na naredni umanjilac, a to je 3. Ključna napomena je da su razlike svih umanjenika ispred 11 i broja 3 manje od tražene razlike 8 (jer su takve bile razike i kada je umanjilac bio manji)
Analiziramo par 3 11. To je prvi par koji ima datu razliku. Ako su elementi različiti, tada se za sve umanjenike posle 11 dobija veća razlika u odnosu na umanjilac 3, pa možemo da pomerimo umanjilac na 7. Slično, umanjenik 11 ne može da napravi ni jedan dalji par čija bi razlika bila jednaka traženoj, pa možemo da pomerimo umanjenik na 14.
Analiziramo par 7 14. Razlika je manja od tražene, pa povećavamo umanjenik na 16.
Analiziramo par 7 16 razlika je veća od tražene, pa pomeramo umanjilac na 8.
Analiziramo par 8 16 čija je razlika jednaka traženoj. Nakon toga možemo povećati i umanjilac na 11 i umanjenik na 17.
Analiziramo par 11 30 i pošto mu je razlika veća od tražene, pomeramo umanjilac na 14.
Analiziramo par 14 30 i pošto mu je razlika veća od tražene, pomeramo umanjilac na 16.
Analiziramo par 16 30 i pošto mu je razlika veća od tražene, pomeramo umanjilac na 30.
Analiziramo par 30 30 kome je razlika manja od tražene, pa pomeramo umanjenik na 38.
Analiziramo par 38 30 kome je razlika jednaka traženoj, pa pomeramo i umanjilac i umanjenik. Pošto ne postoji veći umanjenik, algoritam se završava.
Opišimo formalno prethodni postupak i dokažimo njegovu korektnost. Odredimo koliko parova date razlike \(r\) postoji u intervalu \([i, n)\), ako znamo da važi invarijanta da je je \(a_{j-1} - a_i < r\). Vršimo inicijalizaciju \(i=0\) i \(j=1\), tako da određujemo broj parova i intervalu \([0, n)\), a invarijanta je zadovoljena jer je \(a_{j-1} - a_i = a_0 - a_0 = 0 < r\).
Ako je \(j = n\), tada u intervalu \([i, n)\) ne postoji ni jedan par date razlike. Zaista, na osnovu invarijante važi da je \(a_{n-1} - a_i < r\). Pošto je niz sortiran, i povećanjem \(i\) i smanjivanjem \(j\) razlika se smanjuje. Zato parovi brojeva unutar intervala \([i, n)\) imaju manju razliku od \(r\).
Ako je \(a_j - a_i < r\), tada znamo da u intervalu \([i, j]\) ne postoji ni jedan par brojeva čija je razlika jednaka \(r\) (jer je razlika elemenata unutar intervala uvek manja neko razlika krajnjih elemenata). Invarijanta je zadovoljena za par \((i, j+1)\) pa uvećavamo \(j\) i nastavljamo postupak.
Ako je \(a_j - a_i > r\), tada ni jedan par \(a_{j'} - a_i\) za \(i < j' < n\) nema razliku \(r\). Na osnovu invarijante znamo da je \(a_{j-1} - a_i\) manje od \(r\), pa pošto je niz sortiran to važi i za sve elemente \(i < j' < j\). Pošto je \(a_j - a_i > r\) i pošto je niz sortiran povećanjem \(j\) se povećava razlika, pa su razlike za \(j \leq j' < n\) veće od \(r\). Zato se u intervalu \([i, n)\) svi eventualni parovi čija je razlika \(r\) nalaze u intervalu \([i+1, n)\) i postupak nastavljamo tako što uvećavamo \(i\) za 1. Još moramo dokazati da tada invarijanta važi tj. da je \(a_{j-1} - a_{i+1} < r\), međutim to važi jer je niz sortiran i važi \(a_i < a_{i+1}\), a na osnovu invarijante je važilo da je \(a_{j-1} - a_i < r\).
Na kraju, ako je \(a_j - a_i = r\), tada smo pronašli jedan par. Pošto smo pretpostavili da u nizu nema duplikata i da je niz sortiran, \(a_i\) ne može biti član ni jednog drugog para sa razlikom \(r\) u intervalu \([i, n)\) - pošto je niz sortiran pomeranjem umanjenika nalevo razlika se smanjuje, a pomeranjem nadesno, ona se povećava. Dakle, svi eventualni parovi čija je razlika \(r\) nalaze se u intervalu \([i+1, n)\). Postupak se može nastaviti uvećavanjem i indeksa \(i\) i indeksa \(j\) za 1. Zaista, invarijanta je zadovoljena jer je \(a_{j+1 - 1} - a_{i+1} = a_j - a_{i+1} < a_j - a_i = r\).
Složenost ovog pristupa je \(O(n\log{n})\) zahvaljujući početnom sortiranju, dok je složenost druge faze, nakon sortiranja linearna tj. \(O(n)\). Zaista i umanjenik i umanjilac se kreću u istom smeru (vrednost oba pokazivača se samo uvećava), pa se može napraviti najviše \(2n\) koraka.
Pređimo sada na slučaj u kom se elementi u nizu mogu ponavljati.
Ako se elementi u nizu ponavljaju, onda u trenutku kada nađemo prvi par \((i, j)\) takav da je \(a_i - a_j = r\), određujemo broj pojavljivanja \(n_i\) elementa \(a_i\) i broj pojavljivanja \(n_j\) elementa \(a_j\), broj parova uvećavamo za \(n_i \cdot n_j\) (jer svako pojavljivanje vrednosti \(a_i\) možemo iskombinovati sa svakim pojavljivanjem vrednosti \(a_j\)) i nakon toga postupak nastavljamo od indeksa \((i+n_i, j+n_j)\).
// broj parova elemenata niza a kojima je razlika jednaka datom broju
int brojParovaDateRazlike(const vector<int>& a, int razlika) {
// pravimo sortiranu kopiju niza a
auto as = a;
sort(begin(as), end(as));
int broj = 0;
int i = 0, j = 1;
while (j < as.size()) {
if (as[j] - as[i] < razlika)
j++;
else if (as[j] - as[i] > razlika)
i++;
else {
// pronalazimo sve elemente jednake as[i]
int ii;
for (ii = i+1; ii < as.size() && as[ii] == as[i]; ii++)
;
// odredjujemo koliko ih ima
int broj_ai = ii - i;
// preskacemo ih
i = ii;
// pronalazimo sve elemente jednake as[j]
int jj;
for (jj = j+1; jj < as.size() && as[jj] == as[j]; jj++)
;
// odredjujemo koliko ih ima
int broj_aj = jj - j;
// preskacemo ih
j = jj;
// uvecavamo brojac za broj parova (as[i], as[j])
broj += broj_ai * broj_aj;
}
}
return broj;
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// broj parova elemenata niza a kojima je razlika jednaka datom broju
int brojParovaDateRazlike(const vector<int>& a, int razlika) {
// pravimo sortiranu kopiju niza a
auto as = a;
sort(begin(as), end(as));
int broj = 0;
int i = 0, j = 1;
while (j < as.size()) {
if (as[j] - as[i] < razlika)
j++;
else if (as[j] - as[i] > razlika)
i++;
else {
// pronalazimo sve elemente jednake as[i]
int ii;
for (ii = i+1; ii < as.size() && as[ii] == as[i]; ii++)
;
// odredjujemo koliko ih ima
int broj_ai = ii - i;
// preskacemo ih
i = ii;
// pronalazimo sve elemente jednake as[j]
int jj;
for (jj = j+1; jj < as.size() && as[jj] == as[j]; jj++)
;
// odredjujemo koliko ih ima
int broj_aj = jj - j;
// preskacemo ih
j = jj;
// uvecavamo brojac za broj parova (as[i], as[j])
broj += broj_ai * broj_aj;
}
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false);
int razlika;
cin >> razlika;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << brojParovaDateRazlike(a, razlika) << endl;
return 0;
}Složenošću i dalje dominira sortiranje čija je složenost \(O(n\log{n})\), dok je složenost druge faze i dalje linearna tj. \(O(n)\).
Još jedan način da se reši problem ponavljanja elemenata je da se u prvoj fazi niz vrednosti transformiše u niz parova koji sadrže vrednosti i njihov broj pojavljivanja.
// broj parova elemenata niza a kojima je razlika jednaka datom broju
int brojParovaDateRazlike(const vector<int>& a, int razlika) {
// pravimo sortiranu kopiju niza
auto as = a;
sort(begin(as), end(as));
// odredjujemo broj pojavljivanja svakog elementa
vector<pair<int, int>> b;
b.reserve(as.size());
b.emplace_back(as[0], 1);
for (int i = 1; i < as.size(); i++) {
if (as[i] == b.back().first)
b.back().second++;
else
b.emplace_back(as[i], 1);
}
// trazimo elemente cija je razlika jednaka datoj
int broj = 0;
int i = 0, j = 0;
while (j < b.size()) {
if (b[j].first - b[i].first < razlika)
j++;
else if (b[j].first - b[i].first > razlika)
i++;
else {
broj += b[j].second * b[i].second;
i++; j++;
}
}
return broj;
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// broj parova elemenata niza a kojima je razlika jednaka datom broju
int brojParovaDateRazlike(const vector<int>& a, int razlika) {
// pravimo sortiranu kopiju niza
auto as = a;
sort(begin(as), end(as));
// odredjujemo broj pojavljivanja svakog elementa
vector<pair<int, int>> b;
b.reserve(as.size());
b.emplace_back(as[0], 1);
for (int i = 1; i < as.size(); i++) {
if (as[i] == b.back().first)
b.back().second++;
else
b.emplace_back(as[i], 1);
}
// trazimo elemente cija je razlika jednaka datoj
int broj = 0;
int i = 0, j = 0;
while (j < b.size()) {
if (b[j].first - b[i].first < razlika)
j++;
else if (b[j].first - b[i].first > razlika)
i++;
else {
broj += b[j].second * b[i].second;
i++; j++;
}
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false);
int razlika;
cin >> razlika;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << brojParovaDateRazlike(a, razlika) << endl;
return 0;
}Sortiranje je složenosti \(O(n\log{n})\). Prebrojavanje elemenata se nakon toga izvršava u složenosti \(O(n)\), jednim prolaskom kroz niz, nakon čega se sa dva pokazivača prolazi kroz niz opet u složenosti \(O(n)\). Ukupna složenost je, dakle, \(O(n\log{n})\). Implementacija koristi i pomoćni niz, ali memorijska složenost ostaje \(O(n)\).
U datom nizu pozitivnih prirodnih brojeva naći sve segmente (njihov početak i kraj) čiji je zbir jednak datom pozitivnom broju (brojanje pozicija počinje od nule).
U prvoj liniji standardnog ulaza nalazi se zadati pozitivan prirodni broj \(z\) koji predstavlja dati zbir \(0 < z < 10^6\), u drugoj broj elemenata niza, \(N\) (\(2 \leq N \leq 50000\)), a zatim, u narednoj liniji \(N\) elemenata niza (pozitivni prirodni brojevi manji od \(200\)).
U svakoj liniji standardnog izlaza ispisuju se dva broja (celi brojevi) odvojena prazninom, koji predstavljaju indekse početka i kraja segmenta (brojano od nule). Ako postoji više traženih segmenata njihove indekse ispisati sortirano na osnovu levog kraja.
125 10 60 40 25 50 50 100 25 35 30 35
0 2 2 4 5 6 6 9
Naivno rešenje grubom silom pretpostavlja da se izračunaju zbirovih svih segmenata i da se proveri da li su jednaki datom broju. Čak i kada zbirove segmenata računamo inkrementalno, dobijamo neefikasno rešenje.
Postoji \(O(n^2)\) segmenata, a zbir svakog segmenta na osnovu zbira prethodnog segmenta dobijamo u složenosti \(O(1)\), pa je ukupna složenost \(O(n^2)\).
Pretragu segmenata grubom silom možemo korišćenjem odsecanja načiniti mnogo efikasnijom.
Primer 3.A.9. Posmatrajmo primer pronalaženja prvog segmenta u nizu 1 2 3 5 15 1 2 5 koji ima zbir 21.
Krećemo da ispitujemo zbirove segmenata koji počinju na poziciji \(0\). Sve dok je zbir tekućeg segmenta strogo manji od 21, potrebno je da proširujemo segmente.
i a[i] zbir 0 1 1 1 2 3 2 3 6 3 5 11 4 15 26
U trenutku kada je zbir postao strogo veći od tražene vrednosti 21, sigurni smo da ni jedan segment koji počinje na poziciji 0 ne može imati zbir 21. Naime, pošto su svi dalji elementi striktno pozitivni, njihovim uključivanjem bi se dobio samo još veći zbir. Zbog toga možemo da pređemo na segmente koji počinju na poziciji 1. Važna (i ne baš trivijalna) opaska je to da svi segmenti koji počinju na poziciji 1 i završavaju se pre tekuće pozicije 4 imaju zbir strogo manji od 21 i stoga ih nije potrebno eksplicitno ispitivati. Naime, svi segmenti koji počinju na poziciji 0, a završavaju se pre tekuće pozicije su imali zbir manji od 21, pa se uklanjanjem elementa na poziciji 0 dobijaju segmenti čiji je zbir još manji. Dakle, prvi kandidat za zbir 21, je segment koji počinje na poziciji 1 i završava se na poziciji 4. Njegov zbir lako dobijamo oduzimanjem početne vrednosti 1 sa pozicije 0 od zbira tekućeg segmenta.
i a[i] zbir 1 2 2 2 3 5 3 5 10 4 15 25
Pošto i taj segment ima zbir veći od 21, takav zbir će imati i svi dalji segmenti koji počinju na poziciji 1, pa možemo preći na segmente koji počinju na poziciji 2. Ponovo je prvi kandidat onaj koji se završava na poziciji 4 (jer svi koji se ranije završavaju sigurno imaju zbir manji od 21).
i a[i] zbir 2 3 3 3 5 8 4 15 23
Ponovo je zbir preveliki, pa prelazimo na segmente koji počinju na poziciji 3. Prvi kandidat je segment koji se završava na poziciji 4.
i a[i] zbir 3 5 5 4 15 20
Ovaj put taj segment ima zbir manji od traženog, pa ga je potrebno proširiti nadesno. Dodavanjem narednog elementa dobijamo segment čiji je zbir jednak traženom.
i a[i] zbir 3 5 5 4 15 20 5 1 21
Nakon ovoga smo sigurni da nema više segmenata traženog zbira koji počinju na poziciji 3, pa prelazimo na poziciju 4 i postupak se po istom principu nastavlja dalje.
Dakle, održavamo tekući segment i njegov zbir. Dok je taj zbir manji od traženog proširujemo segment nadesno (dok je to moguće), a kada zbir postane veći ili jednak traženom skraćujemo segment sa leve strane.
Dokažimo i formalno da je prethodni postupak korektan. Obeležimo sa \(z_{ij} = \sum_{k=i}^j a_k\) zbir elemenata niza \(a\) čiji indeksi pripadaju segmentu \([i, j]\), a sa \(z\) traženi zbir elemenata. Pošto su svi elementi niza \(a\) pozitivni, zbirovi elemenata segmenta zadovoljavaju svojstvo monotonosti tj. važi da iz \(i < i' \leq j\) sledi \(z_{ij} > z_{i'j}\) i da iz \(i \leq j < j' < n\) sledi \(z_{ij} < z_{ij'}\).
Pretpostavimo da za neki interval \([i, j]\) znamo da za svako \(j'\) takvo da je \(i \leq j' < j\) važi da je \(z_{ij'} < z\). Postoje sledeći slučajevi za odnos \(z_{ij}\) i \(z\).
Prvo, ako je \(z_{ij} < z\), tada ni za jedan interval koji počinje na poziciji \(i\), a završava se najkasnije na poziciji \(j\) ne može važiti da mu je zbir elemenata \(z\), i proveru je potrebno nastaviti od intervala \([i, j+1]\), uvećavajući \(j\) za 1. Ako takav interval ne postoji (ako je \(j + 1 = n\)), onda se pretraga može završiti (jer je i za svako \(i'\) takvo da je \(i < i' \leq j = n-1\) važi \(z_{i'j} < z_{ij} < z\), a zato i za svako \(j'\) takvo da je \(i' \leq j' < j = n-1\) važi da je \(z_{i'j'} < z_{i'j} < z\), tako da za svaki interval \([i', j']\) takav da je \(i \leq i' \leq j' < n\) važi da je \(z_{i'j'} < z\)).
Drugo, pretpostavimo da je \(z_{ij} \geq z\). Ako je \(z_{ij} = z\), tada je pronađen jedan zadovoljavajući interval i potrebno je obraditi njegove granice \(i\) i \(j\). To je jedini segment koji počinje na poziciji \(i\) sa zbirom \(z\). Ako je \(z_{ij} > z\), onda takvih segmenata nema. Naime, pošto su svi elementi niza \(a\) pozitivni, za svako \(j''\) takvo da je \(j < j'' < n\) važi da je \(z \leq z_{ij} < z_{ij''}\). Dakle, pretragu možemo nastaviti uvećavajući vrednost \(i\). Za sve vrednosti \(j'\) takve da je \(i+1 \leq j' < j\) važi da je \(z_{(i+1)j'} < z\). Naime, pošto je \(a_i > 0\) važi da je \(z_{(i+1)j'} < z_{ij'} < z\). Dakle, na segment \([i+1, j]\) može se primeniti analiza slučajeva istog oblika kao na interval \([i, j]\).
Još jedan način da obrazložimo korektnost ovog postupka je da posmatramo sve zbirove segmenta.
1 3 6 11 26 27 29 34 2 5 10 25 26 28 33 3 8 23 24 26 31 5 20 21 23 28 15 16 18 23 1 3 8 2 7 5
Pošto su elementi niza strogo pozitivni, svaka vrsta ove matrice je strogo rastuća, a svaka kolona je strogo opadajuća. Kada je tekući zbir manji od traženog i svi elementi njegove kolone ispod njega su manji od traženog i oni ne moraju biti razmatrani. Moguće je “precrtati” sve elemente u koloni ispod tekućeg i preći se na razmatranje narednog zbira u tekućoj vrsti (ako on postoji). Kada je tekući zbir veći od traženog, veći su i svi elementi u njegovoj vrsti desno od njega. Moguće je njih precrtati i preći na razmatranje narednog zbira u tekućoj koloni (ako on postoji). Elementi u toj narednoj vrsti levo od tekuće kolone su već ranije precrtani i nije potrebno vraćati se na njih.
Prilikom implementacije održavaćemo interval \([i, j]\) i njegov zbir ćemo izračunavati inkrementalno - prilikom povećanja broja \(j\) zbir ćemo uvećavati za \(a_j\), a prilikom povećanja broja \(i\) zbir ćemo umanjivati za \(a_i\).
Jedan način da se na osnovu prethodne analize napravi implementacija je da se u svakom koraku petlje održavaju dve promenljive \(i\) i \(j\) i promenljiva \(zbir\). Obezbedićemo da pri svakom ulasku u telo petlje važi da promenljiva \(zbir\) čuva tekuću vrednost \(z_{ij}\) i da je za svako \(j' < j\) ispunjeno da je \(z_{ij'} < z\). Ako se \(i\) i \(j\) inicijalizuju na nulu, tada se \(zbir\) treba inicijalizovati na \(a_0\), čime se zadovoljava prethodni uslov.
U telu petlje provervamo da li je \(zbir\) manji od traženog i ako jeste, uvećavamo vrednost \(j\). Ako \(j\) dostigne vrednost \(n\), tada možemo prekinuti petlju i završiti pretragu. Ako je uvećano \(j\) manje od \(n\), onda zbir uvećavamo za \(a_j\) i prelazimo na naredni korak petlje (uslov koji smo nametnuli da važi pri ulasku u petlju će biti ovim biti zadovoljen).
Ako vrednost promenljive \(zbir\) nije manja od tražene vrednosti \(z\) proveravamo da li joj je jednaka. Ako jeste, prijavljujemo pronađeni interval \([i, j]\). Zatim prelazimo na obradu narednog intervala tako što zbir umanjujemo za vrednost \(a_i\) i \(i\) uvećavamo za 1 (uslov koji smo nametnuli da važi pri ulasku u petlju će ovim biti opet zadovoljen).
void ispisiSegmenteDatogZbira(const vector<int>& a, int trazeniZbir) {
// granice segmenta
int i = 0, j = 0;
// zbir segmenta
int zbir = a[0];
while (true) {
// na ovom mestu vazi da je zbir = sum(ai, ..., aj) i da
// za svako i <= j' < j vazi da je sum(ai, ..., aj') < trazeniZbir
if (zbir < trazeniZbir) {
// prelazimo na interval [i, j+1]
j++;
// ako takav interval ne postoji, zavrsili smo pretragu
if (j >= a.size())
break;
// izracunavamo zbir intervala [i, j+1] na osnovu
// zbira intervala [i, j]
zbir += a[j];
} else {
// ako je zbir jednak trazenom, vazi da je
// sum(ai, ..., aj) = trazeniZbir, pa prijavljujemo interval
if (zbir == trazeniZbir)
cout << i << " " << j << endl;
// prelazimo na interval [i+1, j]
// izracunavamo zbir intervala [i+1, j] na osnovu
// zbira intervala [i, j]
zbir -= a[i];
i++;
}
}
}#include <iostream>
#include <vector>
using namespace std;
void ispisiSegmenteDatogZbira(const vector<int>& a, int trazeniZbir) {
// granice segmenta
int i = 0, j = 0;
// zbir segmenta
int zbir = a[0];
while (true) {
// na ovom mestu vazi da je zbir = sum(ai, ..., aj) i da
// za svako i <= j' < j vazi da je sum(ai, ..., aj') < trazeniZbir
if (zbir < trazeniZbir) {
// prelazimo na interval [i, j+1]
j++;
// ako takav interval ne postoji, zavrsili smo pretragu
if (j >= a.size())
break;
// izracunavamo zbir intervala [i, j+1] na osnovu
// zbira intervala [i, j]
zbir += a[j];
} else {
// ako je zbir jednak trazenom, vazi da je
// sum(ai, ..., aj) = trazeniZbir, pa prijavljujemo interval
if (zbir == trazeniZbir)
cout << i << " " << j << endl;
// prelazimo na interval [i+1, j]
// izracunavamo zbir intervala [i+1, j] na osnovu
// zbira intervala [i, j]
zbir -= a[i];
i++;
}
}
}
int main() {
// ubrzavamo ucitavanje
ios_base::sync_with_stdio(false);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// ucitavamo elemente niza
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
ispisiSegmenteDatogZbira(a, trazeniZbir);
return 0;
}Još jedna moguća implementacija sadrži dve ugnežđene petlje. U prvoj desni kraj segmenta pomeramo nadesno sve dok ne stignemo do kraja ili dok je zbir tekućeg segmenta manji od traženog. U drugoj levi kraj segmenta pomeramo nadesno sve dok je zbir veći ili jednak od traženog (pri tom proveravajući da li je zbir jednak traženom i ako jeste, prijavljujući pronađeni interval).
void ispisiSegmenteDatogZbira(const vector<int>& a, int trazeniZbir) {
int i = 0, j = 0; // granice segmenta
int zbir = 0; // zbir segmenta [i, j-1]
while (j < n) {
// prosirujemo segment nadesno dok god je zbir manji od trazenog
while (j < n && zbir < trazeniZbir) {
// dodajemo novi element
zbir += a[j];
j++;
}
// skracujemo interval sve dok je zbir veci od trazenog
while (zbir >= trazeniZbir) {
// ako je zbir intervala jednak trazenom ispisujemo
// pronadjeni interval
if (zbir == trazeniZbir)
cout << i << " " << j - 1 << endl;
// uklanjamo pocetni element
zbir -= a[i];
i++;
}
}
}#include <iostream>
#include <vector>
using namespace std;
void ispisiSegmenteDatogZbira(const vector<int>& a, int trazeniZbir) {
int i = 0, j = 0; // granice segmenta
int zbir = 0; // zbir segmenta [i, j-1]
while (j < n) {
// prosirujemo segment nadesno dok god je zbir manji od trazenog
while (j < n && zbir < trazeniZbir) {
// dodajemo novi element
zbir += a[j];
j++;
}
// skracujemo interval sve dok je zbir veci od trazenog
while (zbir >= trazeniZbir) {
// ako je zbir intervala jednak trazenom ispisujemo
// pronadjeni interval
if (zbir == trazeniZbir)
cout << i << " " << j - 1 << endl;
// uklanjamo pocetni element
zbir -= a[i];
i++;
}
}
}
int main() {
// ubrzavamo ucitavanje
ios_base::sync_with_stdio(false);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// ucitavamo elemente niza
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
ispisiSegmenteDatogZbira(a, trazeniZbir);
return 0;
}Iako sadrži ugnežđene petlje, ovo rešenje je linearne složenosti u odnosu na dužinu niza tj. složenosti je \(O(n)\). Naime, promenljive \(i\) i \(j\) se u svakom koraku uvećavaju za jedan i nikada se ne umanjuju, tako da je ukupan broj koraka ograničen vrednošću \(2n\).
Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.
Poreska inspekcija želi da proveri prevare tako što će proveravati bankovne račune na kojima se nalazi tačno neki specifičan iznos (na primer, tačno 100 hiljada dinara). U tom cilju potrebno je implementirati bankovni sistem. Sistem ima najviše \(k\) različitih korisnika. Svaki korisnik na početku ima račun sa početnim stanjem 0. Potrebno je podržati dve vrste operacija:
ime x dodaje \(x\) dinara na račun osobe sa korisničkim imenom ime (\(x\) može biti i negativno)provera x određuje koliko postoji korisnika čiji račun sadrži tačno \(x\) dinaraNapisati program koji pordržava izvršavanje \(n\) ovakvih operacija.
Sa standardnog ulaza se unose brojevi \(n\) i \(k\). Nakon toga se u \(n\) redova unosi po jedna operacija.
Za svaki upit (operaciju prvog tipa) ispisati odgovor, svaki u zasebnom redu.
6 4 marko 2300 milan 5200 dragana 4000 provera 0 milan -1200 provera 4000
1 2
Zadatak se jednostavno i lako može rešiti upotrebom dve mape tj. rečnika. Jedna se koristi da preslika ime korisnika u iznos na njegovom računu, a druga da preslika iznos na računu u broj računa koji sadrže taj iznos.
// broj upita i broj korisnika
int n, k;
cin >> n >> k;
// iznos na racunu
map<string, int> racun;
// broj korisnika sa datim iznosom novca
map<int, int> brPojavljivanja;
// na pocetku svih k korisnika ima 0 dinara
brPojavljivanja[0] = k;
// obradjujemo sve upite
for (int i = 0; i < n; i++) {
string s;
cin >> s >> x;
if (s == "provera")
cout << brPojavljivanja[x] << '\n';
else {
brPojavljivanja[racun[s]]--;
racun[s] += x;
brPojavljivanja[racun[s]]++;
}
}#include <iostream>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// broj upita i broj korisnika
int n, k;
cin >> n >> k;
// iznos na racunu
map<string, int> racun;
// broj korisnika sa datim iznosom novca
map<int, int> brPojavljivanja;
// na pocetku svih k korisnika ima 0 dinara
brPojavljivanja[0] = k;
// obradjujemo sve upite
for (int i = 0; i < n; i++) {
string s;
cin >> s >> x;
if (s == "provera")
cout << brPojavljivanja[x] << '\n';
else {
brPojavljivanja[racun[s]]--;
racun[s] += x;
brPojavljivanja[racun[s]]++;
}
}
return 0;
}Napiši program koji za dati niz celih brojeva određuje broj nepraznih segmenata uzastopnih elemenata niza čiji je zbir jednak datom broju.
Sa standardnog ulaza se u prvoj liniji unosi tražena vrednost zbira \(z\) (ceo broj \(-10000\) i \(10000\)), zatim, u narednoj liniji dimenzija niza \(n\) (\(3\leq n \leq 50000\)) i zatim u narednoj liniji elementi niza (celi brojevi između -100 i 100, razdvojeni razmakom).
Na standardni izlaz ispiši broj segmenata čiji je zbir jednak \(z\).
11 10 1 2 3 5 1 -1 1 5 3 2
7
Objašnjenje: sledeći segmenti imaju zbir 11
1 2 3 5 1 2 3 5 1 -1 2 3 5 1 1 2 3 5 1 -1 5 1 -1 1 5 1 -1 1 5 3 2 1 5 3 2
Direktno rešenje grubom silom podrazumevalo bi da se provere svi segmenti uzastopnih elemenata, da se za svaki izračuna zbir i da se proveri da li je taj zbir jednak traženom. Svi segmenti se mogu nabrojati ugnežđenim petljama, gde spoljna petlja prolazi kroz leve krajeve segmenta (\(i\) uzima vrednosti od \(0\) pa do \(n-1\)), a unutrašnja petlja prolazi kroz desne krajeve segmenata (od vrednosti \(i\) pa do \(n-1\)).
Složenost ovog pristupa je kubna u odnosu na dimenziju \(n\) tj. \(O(n^3)\).
Algoritam grube sile koji posebno računa zbir svakog segmenta se može unaprediti ako se zbirovi računaju inkrementalno tj. ako se iskoristi činjenica da se zbir svakog segmenta koji se dobija proširivanjem prethodnog segmenta jednim elementom može lako izračunati na osnovu zbira prethodnog segmenta, tako što se zbir prethodnog segmenta uveća za tekući element niza.
Dakle, opet možemo nabrajati sve segmente ugnežđenim petljama, na početku tela spoljašnje petlje zbir inicijalizujemo na nulu, u unutrašnjoj petlji zbir uvećavamo za element \(a_j\) i, ako je on jednak traženom, ispisujemo indekse intervala \([i, j]\).
int brojSegmenataDatogZbira(const vector<int>& a,
int trazeniZbir) {
// broj elemenata niza
int n = a.size();
// broj segmenata trazenog zbira
int broj = 0;
// prolazimo sve segmente
for (int i = 0; i < n; i++) {
// zbir segmenta [i, j]
int zbir = 0;
for (int j = i; j < n; j++) {
// izracunavamo zbir segmenta [i, j] na osnovu zbira
// segmenta [i, j-1]
zbir += a[j];
// proveravamo da li je zbir tog segmenta jednak
// trazenom
if (zbir == trazeniZbir)
broj++;
}
}
return broj;
}#include <iostream>
#include <vector>
using namespace std;
int brojSegmenataDatogZbira(const vector<int>& a,
int trazeniZbir) {
// broj elemenata niza
int n = a.size();
// broj segmenata trazenog zbira
int broj = 0;
// prolazimo sve segmente
for (int i = 0; i < n; i++) {
// zbir segmenta [i, j]
int zbir = 0;
for (int j = i; j < n; j++) {
// izracunavamo zbir segmenta [i, j] na osnovu zbira
// segmenta [i, j-1]
zbir += a[j];
// proveravamo da li je zbir tog segmenta jednak
// trazenom
if (zbir == trazeniZbir)
broj++;
}
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// brojimo segmente datog zbira
cout << brojSegmenataDatogZbira(a, trazeniZbir) << endl;
return 0;
}Ovim je izbegnuta linearna složenost za izračunavanje zbira trenutnog intervala tj. da se zbir svakog narednog intervala dobija u konstantnom vremenu, tako da je složenost celog algoritma redukovana na kvadratnu tj. \(O(n^2)\).
Zadatak se, može rešiti i dosta efikasnije od ovoga.
Jedan elegantan i često primenjivan način da se dobiju zbirovi svih segmenata niza je da se zbir segmenta predstavi kao razlika zbira dva prefiksa niza. U pomoćni niz \(b\) (ili u sam niz \(a\), ako je memorija kritičan resurs), inkrementalno, u linearnoj složenosti \(O(n)\), na svaku poziciju \(k\) od \(0\) do \(n\) možemo smestiti zbir prvih \(k\) elemenata niza tj. zbir elemenata segmenta \([0, k)\).
Nakon toga možemo proveriti sve parove prefiksa i videti da li je njihova razlika jednaka traženom zbiru segmenata. Ako proveravamo svaki segment \([i, j]\) za \(0 \leq i < j < n\) i za svaki zbir određujemo na osnovu razlike zbirova prefiksa (što možemo uraditi u konstantnom vremenu) dobijamo algoritam kvadratne složenosti \(O(n^2)\).
Ovo nije efikasnije od inkrementalnog rešenja grubom silom, ali se uz korišćenje pogodne strukture podataka može unaprediti.
Izražavanje zbira segmenta u obliku razlike zbira dva prefiksa nam daje mogućnost da stignemo do efikasnijeg rešenja. Problem možemo formulisati i ovako. Za svaki zbir \(b_{j+1}\) prefiksa \([0, j+1)\) potrebno je da pronađemo da li postoji zbir \(b_{i}\) prefiksa \([0, i)\) za neko \(i < j\) takva da je \(b_{j+1} - b_{i} = z\), gde je \(z\) traženi zbir, tj. da se proveri da li se među zbirovima prethodnih prefiksa nalazi vrednost \(b_{i} = b_{j+1} - z\). Ako se ta pretraga vrši linearno, dolazimo do implementacije veoma slične prethodnoj, koja ispituje svaki par elemenata \(i < j\). Pošto među elementima niza može biti i negativnih, zbirovi prefiksa nisu sortirani i ne možemo primeniti ni binarnu pretragu. Ostaje nam, međutim, mogućnost da u nekoj strukturi podataka koja omogućava efikasno pretraživanje čuvamo sve zbirove prefiksa za indekse \(i < j\). Ako algoritam organizujemo tako da \(j\) uvećavamo od \(0\) do \(n-1\), tada se na kraju svakog koraka u tu strukturu može dodati i zbir tekućeg segmenta (\(b_{j+1}\)). Struktura treba da realizuje pretragu po ključu, tako da je najbolje upotrebiti asocijativni niz (mapu tj. rečnik).
Pošto se u zadatku traži samo određivanje broja segmenata sa datim zbirom, ključevi mogu biti zbirovi prefiksa, a vrednost pridružena svakom ključu može biti broj prefiksa sa tim zbirom. Da se tražila samo provera da li postoji segment sa datim zbirom, mogli smo umesto asocijativnog niza (mape, rečnika) čuvati samo skup ranije viđenih vrednosti zbirova prefiksa, a da su se eksplicitno tražili svi prefiksi, onda bismo svaki ključ preslikavali u niz vrednosti \(i\) takvih da je \(b_i\) jednako tom ključu.
Ako računamo da će pretraga biti realizovana u \(O(\log{n})\) (što je najčešće slučaj ako se koriste strukture podataka zasnovane na binarnim stablima), tada će ukupna složenost ove implementacije biti \(O(n\log{n})\). Napomenimo da smo dobitak na efikasnosti platili dodatnom memorijom koju smo angažovali, međutim, u ovom scenariju nije potrebno pamtiti učitan niz, tako da memorijska složenost neće biti značajno povećana.
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// zbir prefiksa
int zbirPrefiksa = 0;
// broj segmenata sa trazenim zbirom
int broj = 0;
// broj pojavljivanja svakog vidjenog zbira prefiksa
map<int, int> zbiroviPrefiksa;
// zbir pocetnog praznog prefiksa je 0 i on se za sada pojavio
// jednom
zbiroviPrefiksa[0] = 1;
// ucitavamo elemente niza niz
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// prosirujemo prefiks tekucim elementom
zbirPrefiksa += x;
// trazimo broj pojavljivanja vrednosti
// zbirPrefiksa - trazeniZbir i azuriramo broj
// pronadjenih segmenata
auto it = zbiroviPrefiksa.find(zbirPrefiksa - trazeniZbir);
if (it != zbiroviPrefiksa.end())
broj += it->second;
// povecavamo broj pojavljivanja trenutnog zbira
zbiroviPrefiksa[zbirPrefiksa]++;
}
cout << broj << endl;#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// zbir prefiksa
int zbirPrefiksa = 0;
// broj segmenata sa trazenim zbirom
int broj = 0;
// broj pojavljivanja svakog vidjenog zbira prefiksa
map<int, int> zbiroviPrefiksa;
// zbir pocetnog praznog prefiksa je 0 i on se za sada pojavio
// jednom
zbiroviPrefiksa[0] = 1;
// ucitavamo elemente niza niz
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// prosirujemo prefiks tekucim elementom
zbirPrefiksa += x;
// trazimo broj pojavljivanja vrednosti
// zbirPrefiksa - trazeniZbir i azuriramo broj
// pronadjenih segmenata
auto it = zbiroviPrefiksa.find(zbirPrefiksa - trazeniZbir);
if (it != zbiroviPrefiksa.end())
broj += it->second;
// povecavamo broj pojavljivanja trenutnog zbira
zbiroviPrefiksa[zbirPrefiksa]++;
}
cout << broj << endl;
return 0;
}Đaci sede u krugu obeleženi brojevima od \(0\) do \(n-1\) i igraju se razbrajalice tako da u svakom brojanju jedan đak ispadne. Brojanje kreće od đaka 0 i svaki \(m\)-ti đak ispada. Napiši program koji određuje koji đak će ostatati poslednji.
U prvoj liniji standardnog ulaza nalazi se početni broj đaka \(n\) (\(1 \leq n \leq 10^5\)), a u drugom dužina brojalice \(m\) (\(2 \leq m \leq n\)).
Na standardni izlaz ispisati broj preostalog đaka.
8 3
6
Đaci koji sede u krugu na početku i nakon svakog ispadanja su:
0 1 2 3 4 5 6 7 0 1 3 4 5 6 7 0 1 3 4 6 7 1 3 4 6 7 1 3 6 7 3 6 7 3 6 6
Struktura podataka koja dopušta efikasno izbacivanje elemenata iz sredine je lista (npr. dvostruko povezana). Kružno kretanje po listi možemo ostvariti tako što nakon svakog pomeranja iteratora proverimo da li smo stigli do kraja liste i ako jesmo, iterator ručno ponovo postavimo na početak liste.
// efekat postfiksnog uvecavanja iteratora u kruznoj listi tj. efekat it++
// iterator se pomera na sledece mesto, ali se vraca polazna vrednost
list<int>::iterator uvecaj(list<int>& lista, list<int>::iterator& it) {
list<int>::iterator polazni = it;
it++;
if (it == lista.end())
it = lista.begin();
return polazni;
}
int josif(int n, int m) {
list<int> lista;
for (int i = 0; i < n; i++)
lista.emplace_back(i);
auto it = lista.begin();
while (lista.size() > 1) {
for (int i = 0; i < m - 1; i++)
uvecaj(lista, it);
lista.erase(uvecaj(lista, it));
}
return *it;
}#include <iostream>
#include <list>
using namespace std;
// efekat postfiksnog uvecavanja iteratora u kruznoj listi tj. efekat it++
// iterator se pomera na sledece mesto, ali se vraca polazna vrednost
list<int>::iterator uvecaj(list<int>& lista, list<int>::iterator& it) {
list<int>::iterator polazni = it;
it++;
if (it == lista.end())
it = lista.begin();
return polazni;
}
int josif(int n, int m) {
list<int> lista;
for (int i = 0; i < n; i++)
lista.emplace_back(i);
auto it = lista.begin();
while (lista.size() > 1) {
for (int i = 0; i < m - 1; i++)
uvecaj(lista, it);
lista.erase(uvecaj(lista, it));
}
return *it;
}
int main() {
int n;
cin >> n;
int m;
cin >> m;
cout << josif(n, m) << endl;
return 0;
}Kružnu listu možemo jednostavno realizovati korišćenjem reda. U svakom koraku brojanja jednog đaka sa početka reda ćemo prebaciti na kraj reda. Nakon prebacivanja \(m-1\) učenika, onog koji je na početku reda trajno izbacujemo.
int josif(int n, int m) {
queue<int> red;
for (int i = 0; i < n; i++)
red.push(i);
while (red.size() > 1) {
for (int i = 0; i < m - 1; i++) {
red.push(red.front());
red.pop();
}
red.pop();
}
return red.front();
}#include <iostream>
#include <queue>
using namespace std;
int josif(int n, int m) {
queue<int> red;
for (int i = 0; i < n; i++)
red.push(i);
while (red.size() > 1) {
for (int i = 0; i < m - 1; i++) {
red.push(red.front());
red.pop();
}
red.pop();
}
return red.front();
}
int main() {
int n;
cin >> n;
int m;
cin >> m;
cout << josif(n, m) << endl;
return 0;
}Data su dva niza koja sadrže prirodne brojeve. Napiši program koji određuje \(k\)-ti najveći zbir koji se može dobiti kada se sabere jedan element prvog i jedan element drugog niza. Voditi računa o memorijskoj efikasnosti programa.
Sa standardnog ulaza se učitava broj \(m\) (\(1 \leq m \leq 5000\)), a zatim iz narednog reda \(m\) elemenata prvog niza razdvojenih razmakom. Iz narednog reda se učitava broj \(n\) (\(1 \leq n \leq 5000\)), a zatim iz narednog reda \(n\) elemenata drugog niza razdvojenih razmakom. Elementi oba niza su prirodni brojevi između \(0\) i \(10^6\). Na kraju se učitava broj \(k\) (\(0 \leq k < mn\)).
Na standardni izlaz ispisati zbir koji se nalazi na poziciji \(k\) u nizu koji bi se dobio kada bi se niz svih zbirova parova jednog elementa prvog i jednog elementa drugog niza sortirao nerastuće (pozicije se broje od nule).
3 1 5 3 3 6 4 2 4
7
Zbirovi koji se mogu dobiti, poređani od najvećeg ka najmanjeg su \(5+6=11\), \(5+4=9\), \(3+6=9\), \(5+2=7\), \(3+4=7\), \(1+6=7\), \(3+2=5\), \(1+4=5\), \(1+2=3\), pa se na poziciji \(4\) nalazi zbir \(7\).
5 5 3 8 6 1 6 1 10 9 7 12 2 9
15
Rešenje grubom silom podrazumeva da se formira niz svih zbirova, da se sortira nerastuće i da se pročita element sa pozicije \(k\).
Parova elemenata ima \(m\cdot n\), pa je memorijska složenost kvadratna i iznosi \(O(mn)\). Vremenskom složenošću dominira sortiranje i ona iznosi \(O(mn\log{(mn)})\).
Umesto sortiranja, moguće je primeniti i malo efikasniji algoritam QuickSelect, koji pronalazi element na poziciji \(k\) i bez sortiranja niza, no time rešenje ne bi značajno bilo unapređeno.
// formiramo sve zbirove parova elemenata dva niza
vector<int> zbirovi;
zbirovi.reserve(m*n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
zbirovi.push_back(a[i] + b[j]);
// sortiramo niz zbirova nerastuce
sort(begin(zbirovi), end(zbirovi), greater<int>());
// ispisujemo k-ti element sortranog niza zbirova
cout << zbirovi[k] << endl;#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
int m;
cin >> m;
vector<int> a(m);
for (int i = 0; i < m; i++)
cin >> a[i];
int n;
cin >> n;
vector<int> b(n);
for (int i = 0; i < n; i++)
cin >> b[i];
int k;
cin >> k;
// formiramo sve zbirove parova elemenata dva niza
vector<int> zbirovi;
zbirovi.reserve(m*n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
zbirovi.push_back(a[i] + b[j]);
// sortiramo niz zbirova nerastuce
sort(begin(zbirovi), end(zbirovi), greater<int>());
// ispisujemo k-ti element sortranog niza zbirova
cout << zbirovi[k] << endl;
return 0;
}Problem se može svesti na problem objedinjavanja nekoliko sortiranih nizova, koji se ne moraju istovremeno čuvati u memoriji. Naime, ako sortiramo oba niza opadajuće, možemo razmatrati sledeće nizove:
\[ \begin{array}{c} a_0 + b_0, a_0 + b_1, \ldots, a_0 + b_{n-1},\\ a_1 + b_0, a_1 + b_1, \ldots, a_1 + b_{n-1},\\ \ldots\\ a_{m-1} + b_0, a_{m-1} + b_1, \ldots, a_{m-1} + b_{n-1}. \end{array} \]
Svi oni su sortirani nerastuće i mogu se objediniti korišćenjem reda sa prioritetom. U početku u red ubacujemo prvi element svake liste tj. sve zbirove oblika \(a_i + b_0\). U svakom koraku izbacujemo najveći zbir iz reda i dodajemo u red naredni element liste kojoj on pripada. Da bismo nakon vađenja elementa iz reda mogli dodati naredni element liste kojoj on pripada, pored vrednosti zbira \(a_i + a_j\) (na osnovu kojih je red uređen) u redu moramo čuvati i indekse \(i\) i \(j\). Zapravo dovoljno je čuvati samo indeks \(j\), jer se na osnovu zbira \(z = a_i + b_j\), zbir \(a_i + b_{j+1}\) može dobiti kao \(z-b_j+b_{j+1}\).
U redu se u svakom trenutku nalazi najviše \(m\) elemenata. Pošto se čuvaju i originalni nizovi (da bi se sortirali), memorijska složenost je \(O(m+n)\). Ažuriranje reda vrši se \(k\) puta. Pošto je složenost inicijalnih sortiranja nizova \(O(m\log{m} + n\log{n})\), složenost jednog ažuriranja reda je \(O(\log{m})\), a važi \(k < mn\), vremenska složenost je \(O(m\log{m} + n\log{n} + mn\log{m})\). Složenošću jasno dominira faza objedinjavanja, pa se vremenska složenost može proceniti i samo sa \(O(mn\log{m})\).
// sortiramo nizove opadajuce
sort(begin(a), end(a), greater<int>());
sort(begin(b), end(b), greater<int>());
// objedinjavamo sortirane nizove
// a[i] + b[0], ..., a[i] + b[n-1], za svako i od 0 do m-1
// u redu cuvamo zbirove a[i] + b[j] i pozicije j
priority_queue<pair<int, int>> pq;
// dodajemo u red prvi element svakog niza
for (int i = 0; i < m; i++)
pq.emplace(a[i] + b[0], 0);
// k puta azuriramo red
for (int K = 0; K < k; K++) {
// skidamo element sa vrha reda
int j, z;
tie(z, j) = pq.top(); pq.pop();
// ako lista u kojoj je bio skinuti elemnt nije ispraznjena,
// u red dodajemo njen naredni element
if (j + 1 < n)
pq.emplace(z - b[j] + b[j+1], j+1);
}
// element na poziciji k je trenutno na pocetku reda
cout << pq.top().first << endl;#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
int m;
cin >> m;
vector<int> a(m);
for (int i = 0; i < m; i++)
cin >> a[i];
int n;
cin >> n;
vector<int> b(n);
for (int i = 0; i < n; i++)
cin >> b[i];
int k;
cin >> k;
// sortiramo nizove opadajuce
sort(begin(a), end(a), greater<int>());
sort(begin(b), end(b), greater<int>());
// objedinjavamo sortirane nizove
// a[i] + b[0], ..., a[i] + b[n-1], za svako i od 0 do m-1
// u redu cuvamo zbirove a[i] + b[j] i pozicije j
priority_queue<pair<int, int>> pq;
// dodajemo u red prvi element svakog niza
for (int i = 0; i < m; i++)
pq.emplace(a[i] + b[0], 0);
// k puta azuriramo red
for (int K = 0; K < k; K++) {
// skidamo element sa vrha reda
int j, z;
tie(z, j) = pq.top(); pq.pop();
// ako lista u kojoj je bio skinuti elemnt nije ispraznjena,
// u red dodajemo njen naredni element
if (j + 1 < n)
pq.emplace(z - b[j] + b[j+1], j+1);
}
// element na poziciji k je trenutno na pocetku reda
cout << pq.top().first << endl;
return 0;
}U zavodu za statistiku žele da što nepristrasnije procene koja je prosečna plata. Zaključili su da izračunavanje aritmetičke sredine može dati malo iskrivljenu sliku jer nekoliko ljudi sa veoma visokim platama mogu značajno povećati prosek. Zato su odlučili da umesto aritmetičke sredine izračunaju medijanu, koja se dobija tako što se sve plate poređaju u neopadajući niz i onda se uzme središnji element tog niza. Ako u nizu ima paran broj elemenata, onda se za medijanu uzima aritmetička sredina dva središnja elementa. Na primer, medijana niza brojeva 1, 2, 4, 7, 9 je 4 (jer je on središnji), a niza brojeva 1, 2, 4, 5, 7, 9 je 4.5 (jer je to aritmetička sredina brojeva 4 i 5 koji su središnji elementi). Podaci o platama pristižu u zavod, a softver mora da može da u svakom trenutku da podatak o medijani do tada unetih plata.
Sa standardnog ulaza se unose linije, sve do kraja standardnog ulaza. Linija ili sadrži slovo d i zatim iznos plate razdvojen razmakom (ceo broj), što znači da se unosi podatak o novoj plati ili sadrži slovo m što znači da je potrebno na standardni izlaz ispisati podatak o medijani do tada unetih plata. Prva linija sigurno sadrži d.
Na standardnom izlazu su ispisane tražene medijane, svaka u posebnom redu, zaokružene na jednu decimalu.
d 5 d 7 d 6 m d 8 m
6.0 6.5
Direktan način da se zadatak reši je taj da se sve učitane plate smeštaju u niz (ili još bolje vektor tj. listu, pošto ne znamo unapred koliko će plata biti učitano) i da se svaki put kada se zatraži izračunavanje medijane pozove funkcija koja računa medijanu niza. Ta funkcija može biti zasnovana na sortiranju i čitanju središnjeg elementa (tj. središnjih elemenata kada je niz parne dužine), a postoje i malo efikasnija rešenja od toga.
Složenost takvog rešenja zavisi od složenosti sortiranja koji je \(O(n\log(n))\) kada se koristi bibilotečka funkcija sortiranja, tako da je ukupna složenost \(O(n^2\cdot \log(n))\), pri čemu pretpostavljamo da će se medijana računati \(O(n)\) puta za niz koji ima \(O(n)\) elemenata (tj. da su i broj dodavanja i broj upita za medijanom određeni brojem \(n\)).
Medijana se može naći i bez sortiranja celog niza, korišćenjem ideje particionisanja tj. algoritma brze selekcije (QuickSelect).
U jeziku C++ ovo je najlakše ostvariti pomoću funkcije nth_element. Recimo i da je u slučaju parne dimenzije funkciju nth_element potrebno pozvati dva puta, da bi se odredila dva središnja elementa.
Složenost pronalaženja medijane algoritmom brze selekcije je u najgorem slučaju \(O(n)\), što dovodi do ukupnog rešenja složenosti \(O(n^2)\).
Efikasno rešenje se može dobiti ako u svakom trenutku u jednoj (reći ćemo levoj) kolekciji čuvamo sve elemente koji su manji od središnjeg, a u drugoj (reći ćemo desnoj) sve one koji su veći ili jednaki središnjem (ako postoji paran broj elemenata, te dve kolekcije treba da sadrže isti broj elemenata, a ako postoji neparan broj elemenata, desna kolekcija može da sadrži jedan element više). Ako ima neparan broj elemenata, tada je medijana jednaka najmanjem elementu desne kolekcije, a u suprotnom je jednaka aritmetičkoj sredini između najvećeg elementa leve i najmanjeg elementa desne kolekcije. Svaki novi element se poredi sa najmanjim elementom desne kolekcije i ako je manji ili jednak njemu ubacuje se u levu kolekciju, a ako je veći od njega, ubacuje se u desnu kolekciju. Tada se proverava da li se sredina promenila. Ako se desilo da leva kolekcija ima više elemenata od desne (što ne dopuštamo), najveći element leve kolekcije treba da prebacimo u desnu. Ako se desilo da u desnoj kolekciji ima dva elementa više nego u levoj, tada najmanji element desne kolekcije prebacujemo u levu. Dakle, leva kolekcija treba da bude takva da lako možemo da pronađemo i izbacimo njen najveći element, a desna da bude takva da lako možemo da pronađemo i izbacimo njen najmanji element, pri čemu obe kolekcije moraju da podrže efikasno ubacivanje proizvoljnih elemenata. Jasno je da te kolekcije treba da budu hipovi (u jeziku C++ možemo upotrebiti priority_queue) u kojima se najmanja tj. najveća vrednost može očitati u konstantnom vremenu, ukloniti u logaritamskom, isto koliko je potrebno i da se umetne novi element.
Primer 3.A.10. Prikažimo rad ovog algoritma na jednom primeru.
Na početku su oba hipa prazna.
Pretpostavimo da se na ulazu pojavljuje element 5. Njega ubacujemo u desni hip (jer on može da sadrži jedan element više). Stanje je sada sledeće:
\(\mathit{levi}: []\quad \mathit{desni}: [5]\)
Medijana je element na vrhu desnog hipa tj. 5.
Pretpostavimo sa se na ulazu sada pojavljuje element 6. Pošto je on veći od elementa 5 koji je na vrhu desnog hipa, element 5 prebacujemo u levi, a element 6 ubacujemo u desni hip. Stanje je sada sledeće:
\(\mathit{levi}: [5]\quad \mathit{desni}: [6]\)
Medijana je prosek elemenata na vrhu oba hipa tj. 5,5.
Pretpostavimo da se sada na ulazu pojavljuje element 3. Pošto je on manji od elementa 5 na vrhu levog hipa element 5 prebacujemo u desni hip, a element 3 ubacujemo u levi. Stanje je sada sledeće:
\(\mathit{levi}: [3]\quad \mathit{desni}: [5, 6]\)
Medijana je element na vrhu desnog hipa tj. 5.
Pretpostavimo da se sada na ulazu pojavljuje element 1. Pošto je on manji od elementa 5 na vrhu desnog hipa, dodajemo ga u levih hip.
Stanje je sada sledeće:
\(\mathit{levi}: [1, 3]\quad \mathit{desni}: [5, 6]\)
Medijana je prosek elemenata na vrhu oba hipa tj. 4.
Pretpostavimo da se sada na ulazu pojavljuje element 8. Pošto je on veći od elementa 5 na vrhu desnog hipa, dodajemo ga u desni hip.
Stanje je sada sledeće:
\(\mathit{levi}: [1, 3]\quad \mathit{desni}: [5, 6, 8]\)
Medijana je elemenat na vrhu desnog hipa, tj. 5.
Ideja da se umesto u jedne podaci čuvaju u dve strukture podataka često može dovesti do efikasnog rešenja.
priority_queue<int, vector<int>, greater<int>> desni;
priority_queue<int, vector<int>, less<int>> levi;
double medijana() {
if (levi.size() == desni.size())
return (levi.top() + desni.top()) / 2.0;
else
return desni.top();
}
void dodaj(int x) {
if (desni.empty())
desni.push(x);
else {
if (x <= desni.top())
levi.push(x);
else
desni.push(x);
if (levi.size() > desni.size()) {
desni.push(levi.top());
levi.pop();
} else if (desni.size() > levi.size() + 1) {
levi.push(desni.top());
desni.pop();
}
}
}#include <iostream>
#include <iomanip>
#include <queue>
#include <string>
#include <vector>
#include <functional>
using namespace std;
priority_queue<int, vector<int>, greater<int>> desni;
priority_queue<int, vector<int>, less<int>> levi;
double medijana() {
if (levi.size() == desni.size())
return (levi.top() + desni.top()) / 2.0;
else
return desni.top();
}
void dodaj(int x) {
if (desni.empty())
desni.push(x);
else {
if (x <= desni.top())
levi.push(x);
else
desni.push(x);
if (levi.size() > desni.size()) {
desni.push(levi.top());
levi.pop();
} else if (desni.size() > levi.size() + 1) {
levi.push(desni.top());
desni.pop();
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
while (true) {
string s;
if (!(cin >> s))
break;
if (s == "m")
cout << fixed << showpoint << setprecision(1)
<< medijana() << '\n';
else if (s == "d") {
int x;
cin >> x;
dodaj(x);
}
}
return 0;
}