У наставку ћемо приказати још неке примере који илуструју примену описаних техника побољшања сложености алгоритама.
Напиши програм који одређује колико у интервалу \([a, b]\) постоји бројева дељивих бројем \(k\).
Са стандардног улаза уносе се три цела броја, сваки у посебном реду: \(a\) (\(0 \leq a \leq 10^9\)), \(b\) (\(a \leq b \leq 10^9\)), \(k\) (\(1 \leq k \leq 10^9\)).
На стандардни излаз исписати тражени цео број.
30 53 5
5
Бројеви су 30, 35, 40, 45 и 50.
Могуће је направити решење засновано на претрази грубом силом, и које редом пролази кроз све бројеве од \(a\) до \(b\), проверава за сваки да ли је дељив бројем \(k\) и за сваки који јесте, увећава бројач пронађених бројева. То решење је најједноставније за разумевање и имплементацију, међутим може бити неефикасно.
// 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;
}Сложеност овог решења је линеарна у односу на број елемената у интревалу тј. \(O(b-a)\).
Да би број \(x\) био дељив бројем \(k\) потребно је да постоји неко \(n\) тако да је \(x=n\cdot k\). Пошто \(x\) мора бити у интервалу \([a, b]\), мора да важи да је \(a \leq n\cdot k\) и \(n \cdot k \leq b\). Најмање \(n\) које задовољава прву неједначину једнако је \(n_l = \left\lceil{\frac{a}{k}}\right\rceil\), највеће \(n\) које задовољава другу неједначину једнако је \(n_d = \left\lfloor{\frac{b}{k}}\right\rfloor\). Било који број из интервала \([n_l, n_d]\) задовољава обе неједнакости и представља количник неког броја из интервала \([a, b]\) бројем \(k\). Слично, било који број из интервала \([a, b]\) дељив бројем \(k\) даје неки количник из интервала \([n_l, n_d]\). Зато је тражени број бројева из интервала \([a, b]\) који су дељиви бројем \(k\) једнак броју бројева у интервалу \([n_l, n_d]\) а то је \(n_d - n_l + 1\) ако је \(n_d \geq n_l\), тј. \(0\) ако је тај интервал празан тј. ако је \(n_d < n_l\). Бројеви \(n_l\) и \(n_d\) се могу одредити, на пример, гранањем.
// 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;
}Сложеност овог решења је, очигледно, константна тј. \(O(1)\).
Дат је правоугаоник димензије \(a \times b\), где су бројеви \(a\) и \(b\) цели. Колика је максимална површина правоугаоника који се може добити продужавањем страница тог правоугаоника за укупну дужину \(c\), где је \(c\) цео број и дужине страница новог правоугаоника су такође цели бројеви?
Са стандардног улаза се учитавају природни бројеви \(a, b, c \leq 10^9\), раздвојени са по једним размаком.
На стандардни излаз исписати максималну површину након продужења страница.
5 10 3
80
Димензија након проширења ће бити \(8 \times 10\).
9 10 4
132
Димензија након проширења ће бити \(11 \times 12\).
14 17 5
324
Задатак може бити решен грубом силом, тј. испробавањем свих могућности расподеле додатне дужине. За сваку дужину \(i\) између \(0\) и \(c\), додајемо \(i\) страници \(a\) и \(c-i\) страници \(b\), израчунавамо површину и тражимо максимум тако добијених површина.
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;
}Сложеност овог решења је \(O(c)\).
Докажимо да од свих правоугаоника датог фиксираног обима, највећу површину има квадрат. Нека је обим правоугаоника једнак \(2(x + y) = 2s\). Његова површина једнака је \(x\cdot y = x \cdot (s - x) = x\cdot s - x\cdot x = s^2/4 - (x - s/2)^2\). Пошто је \((x - s/2)^2 \geq 0\), површина не може бити већа од \(s^2/4\), а једнака је тој вредности када је \(x = y = s/2\). Дакле, у задатом проблему, увећање треба направити тако да се добије облик који је што сличнији квадрату (добијање квадрата у неким случајевима није могуће).
Нека је \(a \leq b\). Ако је \(a + c \leq b\), тада целокупан износ увећања \(c\) треба додати на мању страницу \(a\). У супротном, прво се краћа страница \(a\) продужи тако да постане једнака дужој страници \(b\), а затим се преостали износ увећања (\(c - (b - a)\)) подели што равномерније могуће (ако је то паран број може се добити квадрат, а ако није, тада се добија правоугаоник код којег је једна страница за један дужа од друге). У имплементацији дужине нових страница можемо израчунати тако што дужу страницу \(b\) увећамо за \(\left\lfloor{\frac{c - (b - a)}{2}}\right\rfloor\) и за \(\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;
}Сложеност овог решења је \(O(1)\).
Приметимо да смо у овом оптимизационом проблему успели да дамо прецизну математичку карактеризацију траженог максимума (што је било могуће јер је функција која се оптимизовала била једноставна, у овом случају - квадратна) и тиме избегли итеративну претрагу. Генерално, када се решавају оптимизациони проблеми увек има смисла размислити да ли је функција која се оптимизује можда таква да се максимум може израчунати математичким методама да би се у потпуности избегла претрага или бар окарактерисати на неки начин који омогућава да се значајно редукује број кандидата које треба проверити.
Бројеви од 0 до \(n^2 - 1\) ређају се у квадрат. На пример, за \(n=5\) добија се следећи квадрат:
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
Напиши програм који израчунава збир бројева у датој врсти и датој колони квадрата (и њих ћемо бројати од нуле).
Са стандардног улаза учитавају се следећи цели бројеви (сваки у посебном реду).
На стандардни излаз исписати два цела броја, сваки у посебном реду:
Ако су ови збирови већи или једнаки од \(10^9\), исписати њихових последњих 9 цифара.
5 1
35 55
Решење се може добити употребом петљи и алгоритма за сабирање серије бројева, при чему је свако сабирање потребно вршити по модулу \(10^9\) (да не би дошло до прекорачења и да би се код великих бројева добило само последњих 9 цифара).
Почетак врсте \(i\) израчунавамо тако што број \(n\) саберемо \(i\) пута (почетак сваке наредне врсте већи је за \(n\) од претходне, док прва врста почиње нулом). Наравно, јасно је да ће се добити вредност \(i\cdot n\), па би ова петља лако могла да се избегне. Збир врсте израчунавамо тако што сабирамо један по један елемент те врсте, при чему је сваки елемент за један већи од претходног (ако је почетак врсте \(p\), сабирамо бројеве \(p\), \(p+1\), , \(p+n-1\)).
Први елемент колоне са редним бројем \(i\) је \(i\). Сваки наредни елемент те колоне за \(n\) је већи од претходног. На тај начин израчунавамо свих \(n\) елемената те колоне, додајући их један по један на збир.
Сложеност итеративног алгоритма за израчунавање збира сваке врсте и сваке колоне је \(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;
}Квадрат садржи следеће бројеве:
\[ \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} \]
Елементи \(i\)-те врсте чине аритметички низ. Први члан је \(a_1 = i\cdot n\), а разлика између суседна два члана \(d = 1\). Применом формуле за збир \(n\) елемената аритметичког низа \(S_n = a_1 + \ldots + a_n = n\cdot a_1 + d\cdot\frac{n(n-1)}{2}\) добијамо да је збир елемената у \(i\)-тој врсти једнак
\[i\cdot n^2 + \frac{n(n-1)}{2}.\]
Слично, елементи \(i\)-те колони такође чине аритметички низ у коме је први члан \(a_0=i\), а разлика између суседна два члана једнака је \(n\). Зато је њен збир једнак
\[n\cdot i + n\cdot \frac{n(n-1)}{2}.\]
Пошто је бар један од бројева \(n\) или \(n-1\) паран, резултат је увек цео број и могуће је све операције изводити над целим бројевима (укључујући и целобројно дељење са 2). Имплементацију је могуће направити директно на основу ових формула, водећи рачуна о томе да се све операције изводе по модулу \(10^9\), да не би дошло до прекорачења и да би се одредило последњих 9 цифара дужих бројева.
Сложеност овог програма је, јасно, \(O(1)\). У имплементацији би могао бити смањен број примене израчунавања остатка (ово је скупа операција), међутим, пошто се она примењује само константан број пута, тиме се не би добило значајно убрзање, а код би постао теже разумљив и лакше би могло доћи до грешке.
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;
}Могуће је и дефинисати функцију за израчунавање збира елемената аритметичког низа и два пута је употребити. И у овом решењу је потребно све аритметичке операције изводити по модулу \(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;
}Напиши програм који одређује на колико се начина дати природни број \(n\) може представити као збир два или више узастопних природних бројева (већих или једнаких 1).
Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 10^9\)).
На стандардни излаз исписати тражени број начина.
15
3
Važi: \(15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8.\)
Први покушај може бити решавање проблема грубом силом, тј. испробавање свих могућих првих чланова збира. Најмањи могући први члан је \(a_0 = 1\). Пошто збир мора да буде бар двочлан, највећи могући први члан је онај број \(a_0\) такав да је \(a_0 + (a_0 + 1) \leq n\). Када смо одредили први члан, одређујемо колико сабирака треба узети да би се добио збир \(n\). Крећемо од двочланог низа и затим додајемо један по један наредни сабирак све док збир не достигне или не престигне збир \(n\). Бројач увећавамо ако је након петље збир једнак вредности \(n\) (тада је успешно нађено једно решење).
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;
}Спољашња петља се извршава око \(\frac{n}{2}\) пута. Број извршавања унутрашње петље је теже проценити. Питамо се који је број сабирака \(m\) потребан, тако да је \(a_0 + (a_0 + 1) + \ldots + (a_0 + (m-1)) \geq n\). Ако применимо формулу за збир аритметичког низа, видимо да је тај збир једнак \(m \cdot a_0 + \frac{m(m-1)}{2}\). Веома груба процена када је \(a_0\) мало даје нам процену за \(m\) око \(\sqrt{2n}\). Мада, чим \(a_0\) крене да расте, овај број крене да опада. Веома грубо, сложеност можемо ограничити одозго као \(O(n \sqrt{n})\).
Редослед петљи може бити другачији. Спољашњом петљом можемо одређивати број сабирака \(m\), а унутрашњом испробавати вредности почетног сабирка. Крећемо од два сабирка. Највећи могући број сабирака наступа када је \(a_0 = 1\), и пошто је \(a_0 + (a_0 + 1) + \ldots + (a_0 + (m-1)) = m \cdot a_0 + \frac{m(m-1)}{2}\), да би збир могао да евентуално буде \(n\) мора да важи да је \(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;
}Сложеност је идентична као у претходном приступу и може се грубо проценити са \(O(n \sqrt{n})\).
Кључна оптимизација наступа када увидимо да нам унутрашња петља није потребна. Наиме, нема потребе испробавати различите вредности \(a_0\), већ се \(a_0\) може израчунати на основу \(m\) и \(n\). Ако је \(m \cdot a_0 + \frac{m(m-1)}{2} = n\), тада је \(a_0 = \frac{n - \frac{m(m-1)}{2}}{m}\). Збир са \(m\) сабирака постоји ако и само ако је ово цео број (што се може проверити испитивањем остатка при дељењу бројева \(n - \frac{m(m-1)}{2}\) и \(m\)). Услов \(m + \frac{m(m-1)}{2} \leq n\) гарантује да је \(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;
}Сложеност једине петље, па и целог програма се може грубо оценити са \(O(\sqrt{n})\) (у њеном телу се провера постојања броја \(a_0\) врши у сложености \(O(1)\)).
Приметимо да се након примене формуле за збир аритметичког низа задатак свео на проналажење целобројних решења једне једначине са две непознате (\(a_0\) и \(m\))
\[m\cdot a_0 + \frac{m(m-1)}{2} = n.\]
Пошто број целобројних решења не можемо унапред одредити, користимо итеративни поступак да проверимо разне кандидате.
До ефикасног решења овог задатка смо дошли тако што смо уместо провере разних парова вредности, увидели да се након фиксирања једне вредности она друга може експлицитно израчунати. Редослед провера је веома важан, јер је једначина линеарна по \(a_0\), а квадратна по \(m\), тако да је за фиксирано \(m\), \(a_0\) прилично једноставно израчунати, док за фиксирано \(a_0\) није једноставно израчунати \(m\). Дакле, у овом задатку видимо одличан спој рачунарског и математичког приступа: пошто једначину са две променљиве не можемо да решимо математички, користимо итеративни поступак и испробавамо разне вредности \(m\). Након тога добија се једначина која се може решити математички и тада избегавамо коришћење итеративног поступка који би испробавао разне вредности \(a_0\).
Један класичан инкрементални алгоритам је Бресенхамов алгоритам који се користи за цртање правих линија на екрану који се састоји од пиксела. Претпоставимо да је координатни систем постављен тако да је ширина сваког пиксела 1 и да су пиксели постављени тако да им центри леже у тачкама са целобројним координатама. Цртаћемо дуж од пиксела чији је центар у тачки \((x_0, y_0)\) до пиксела чији је центар у тачки \((x_1, y_1)\). Разматраћемо само случај када је \(x_0 < x_1\) и када је нагиб дужи \(\Delta y / \Delta x\) мањи од 1 (дуж је “претежно хоризонтална”).
Размотримо Бресенхамов алгоритам илустрован на слици 15.
Обрађиваћемо све целобројне координате од \(x_0\) до \(x_1\) и за сваку ћемо цртати тачно један пиксел. Прво се црта леви пиксел са центром у \((x_0, y_0)\). Положај сваког наредног пиксела се одређује тако да тај наредни пиксел буде или на истој висини са тренутним (хоризонтални корак) или на висини за један већој (дијагонални корак). Два потенцијална пиксела (она лево и онај горе лево) дели хоризонтална права чија је висина \(y_i + 1/2\) (дуж горње ивице текућег пиксела). Који од њих треба узети зависи од тога да ли тзв. средишња тачка \((x_i+1, y_i+1/2)\) лежи испод или изнад дужи која спаја тачке \((x_0, y_0)\), као што је илустровано на слици 15.
Координата у којој дуж сече вертикалну праву \(x=x_i\) се може израчунати као \(y_0 + \Delta y / \Delta x \cdot (x_i-x_0)\), али пошто тренутна висина \(y_i\) зависи од претходних пиксела, њу не можемо израчунати унапред неком формулом. Стога се алгоритам природно изражава инкрементално, тј. сав рачун се организује тако да потребне координате наредног пиксела зависе само од координата претходног пиксела. Дуж креће од координате \((x_0, y_0)\) и у сваком кораку се десно помери за 1, а навише за \(\Delta y / \Delta x\). Средишња тачка се иницијално налази на \((x_0+1, y_0+1/2)\). У сваком кораку јој се \(x\)-координата повећава за 1, док се \(y\)-координата или не мења (ако је направљен хоризонтални корак) или се повећа за 1 (ако је направљен дијагонални корак).
Нека променљива \(p\) означава вертикалну разлику између висине дужи и висине средишње тачке. Иницијално (за \(x=x_0+1\), где се доноси прва одлука), је та разлика једнака \((y_0 + \Delta y / \Delta x) - (y_0 + 1/2)\) \(=\) \(\Delta y / \Delta x - 1/2\). Како се та разлика мења у сваком кораку?
На тај начин добијамо наредни инкрементални алгоритам.
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++;
}Важна оптимизација (константног фактора) коју је Бресеман приметио је да се уместо рада се реалним бројевима алгоритам може спровести само у целобројној аритметици. Пошто је вредност \(\Delta x\) по нашим претпоставкама позитивна, знак разлике \(p\) се не мења ако се уместо разлике све време разматра разлика помножена вредношћу \(2\cdot \Delta x\). Пошто је иницијално \(p=\Delta y/\Delta x + 1/2\), овим множењем добијамо да је целобројна разлика \(p' = 2\Delta x\cdot p = 2\Delta y - \Delta x\). И кораци ажурирања се лако прилагођавају (множењем додела у којима се ажурира \(p\) са \(2\Delta x\)). У дијагоналном кораку се целобројна разлика увећава за \(2\Delta y - 2 \Delta x\), док се у хоризонталном увећава само за \(2\Delta y\). Тиме се добија ефикаснија верзија.
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;
}У наредном аплету можете видети како овај алгоритам функционише.
Панграми су речи које садрже бар једно појављивање сваког слова абецеде или азбуке (слова се могу појављивати и више пута). Чувени панграм у енглеском језику је ниска "the quick brown fox jumps over a lazy dog". Напиши програм који проверава да ли се у датом тексту налази неки подтекст (низ узастопних карактера) дужине \(k\) који је панграм.
Прва линија стандардног улаза садржи ниску састављену само од малих слова енглеске абецеде, дужине највише \(10^5\) карактера. Наредни ред садржи природан број \(k\) (\(1 \leq k \leq 10^5\)).
На стандардни излаз исписати da ако у унетом тексту постоји панграм дужине \(k\), односно ne у супротном.
xxxabcdefghijklmnopqrstuvwxyzxxx 26
da
xxxabcdefghijklmxxxnopqrstuvwxyzxxx 28
ne
xxxabcdefghijklmxxxnopqrstuvwxyzxxx 29
da
Решење грубом силом подразумева да се за сваку подниску дужине \(k\) провери да ли садржи све карактере абецеде. За сваку подниску и свако слово абецеде можемо линеарном претрагом утврдити да ли подниска садржи то слово (линеарна претрага може бити реализована било библиотечком функцијом, било ручно имплементирана). Ако су сва слова пронађена, подниска је панграм и тада можемо прекинути даљу анализу, док у супротном прелазимо на анализу наредне подниске.
Провера да ли је подниска панграм захтева 26 линеарних претрага дужине \(k\). У принципу, можемо сматрати да је сложеност \(O(k)\), иако је константа 26 прилично велика. Подниски има укупно \(n-k\), па у најгорем случају (када је \(k\) око пола дужине низа), добијамо алгоритам квадратне сложености \(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;
}Ефикасније решење можемо добити захваљујући принципу инкременталности. Да бисмо проверили да ли је нека реч панграм, довољно је да знамо скуп карактера који се у њој јављају и да проверимо да ли тај скуп садржи 26 елемената. Приликом преласка са једне на другу подниску, већина карактера се поклапа. Разликују се само први карактер прве подниске и последњи карактер друге подниске. Зато приликом преласка са подниске на подниску треба из скупа уклонити први, а додати последњи карактер. Међутим, пошто се карактери јављају више пута, ово може бити погрешно, па заправо уместо скупова треба разматрати мултискупове. Најједноставнији начин је да уведемо пресликавање које сваком карактеру додељује његов број појављивања у подниски (оно може бити реализовано помоћу низа бројача или, једноставније, преко мапе тј. речника). Приликом преласка на наредну подниску умањујемо бројач првог карактера (и ако достигне нулу, уклањамо га из мапе) и увећавамо бројач последњег карактера. Након тога, проверавамо да ли је број карактера у мапи једнак 26 и ако јесте, текућа подниска представља панграм.
Пошто се у сваком тренутку одржавају подаци о неком сегменту оригиналног низа крактера дужине \(k\) и тај сегмент се полако помера слева надесно, некада се каже да се примењује техника покретног прозора и тај прозор се ажурира инкрементално.
У петљи се анализира сваки карактер ниске. Ако претпоставимо да су операције са мапом тј. речником константне сложености (што је прилично оправдано, јер постоји само 26 различитих кључева), сложеност целог алгоритма се може оценити са \(O(n)\), где је \(n\) дужина ниске која се проверава.
// 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;
}Неки блокови меморије су заузети, а неки слободни. Да би се у меморију могао сместити дугачак низ података, потребно је пронаћи што дужи низ узастопних слободних блокова.
Са стандардног улаза се уноси природан број \(N\) (\(5 \leq N \leq 50000\)), а затим и \(N\) бројева 1 (што означава да је блок заузет) или 0 (што означава да је блок слободан).
На стандардни излаз исписати један природан број који представља тражену дужину најдуже серије узастопних слободних блокова.
8 0 0 1 0 0 0 1 1
3
Задатак захтева да се одреди дужина најдуже серије узастопних нула.
У наивном приступу решавању овог проблема улазни подаци се смештају и чувају у низу. То није неопходно, али ћемо најпре приказати и таква решења, да бисмо систематично илустровали неке технике поступне оптимизације кода.
Једно веома наивно решење је да анализирамо све могуће сегменте низа одређене свим могућим вредностима променљивих \(0 \leq i \leq j < n\). Њих можемо набројати угнежђеним петљама. За сваки сегмент можемо применом линеарне претраге проверити да ли садржи само нуле и ако садржи, ажурирати максимум у складу са тим.
// 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;
}Пошто се подаци смештају у помоћни низ, меморијска сложеност је \(O(n)\). Ово решење је изразито неефикасно, јер му је временска сложеност чак кубна тј. \(O(n^3)\). Са друге стране коректност овог решења је заиста тривијално образложити (оно се потпуно директно изводи из саме формулације задатка).
Мало бољи приступ је да за сваку позицију \(i\) одредимо најдужу серију узастопних нула која почиње на тој позицији. То се може урадити тако што се серија који почиње на позицији \(i\) проширује од позиције \(i\) надесно, све док се у њој налазе само нуле. Важна уштеда на овом месту је то што ако знамо да су у сегменту \([i, j]\) све нуле и да се нула налази и на позицији \(j+1\), онда знамо и да су све нуле и у сегменту \([i, j+1]\) (кажемо да проверу вршимо инкрементално).
Када се наиђе на број различит од нуле (или на крај низа), нађена је најдужа серија узастопних нула која почиње на позицији \(i\), јер ће сва продужавања те серије надесно, ако их има, садржати и ову вредност различиту од нуле. Дакле, на овом месту вршимо одсецање претраге прескачући многе сегменте низа за које се унапред зна да не могу задовољити наметнути услов. Такође, поређење са максималном дужином вршимо тек када максимално проширимо текући сегмент, јер унапред знамо да су сви подсегменти тог максимално проширеног сегмента краћи од њега (и овде заправо вршимо одређено одсецање).
// 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;
}Ово решење је сложености \(O(n^2)\), што је боље од првог, међутим и даље субоптимално. Пошто се подаци смештају у помоћни низ, меморијска сложеност је \(O(n)\).
Програм се може додатно значајно убрзати даљим одсецањем. Једном када одредимо да је најдужи сегмент који садржи узастопне нуле и почиње на позицији \(i\) сегмент \([i, j]\), време значајно можемо уштедети тако што приметимо да ни један сегмент који садржи узастопне нуле и почиње на позицијама након \(i\), а закључно са \(j\) не може бити дужи од сегмента који почиње са \(i\) (јер ако позиција \(j\) није последња у низу, на позицији иза ње се не налази нула и ти сегменти се не могу проширити даље од позиције \(j\)). Зато је након ширења сегмента који почиње на позицији \(i\) надесно и одређивања серије нула која почиње на позицији \(i\) могуће директно прећи на израчунавање најдужег сегмента узастопних нула који почиње на позицији \(j+1\) (ако таква постоји). Ово заправо одговара томе да цео низ изделимо на сегменте узастопних нула који се надовезују (пресечени сегментима узастопних јединица). Сложеност таквог приступа је \(O(n)\), јер се границе сегмената само увећавају и никада не смањују.
Овај алгоритам је заправо и врло интуитиван и вероватно је први алгоритам који би програмер са мало искуства имплементирао: крећемо од почетка, проналазимо серију узастопних нула који почиње на почетку, након тога тражимо серију узастопних нула након те прве серијe, затим серију узастопних нула након те друге и тако даље. Дакле, цео низ делимо на мање сегменте који садрже једнаке елементе и надовезују се један иза другог, при чему је подела таква да је сваки од тих сегмената оптималан у смислу да га није могуће продужити (ни на лево, ни на десно).
Можемо приметити да нам током имплементације није више неопходно да памтимо све резултате у низу истовремено. У једној петљи ћемо читати редом елементе низа и у сваком тренутку одржавати дужину текуће и дужину најдуже до тада обрађене серије (сегмента) узастопних нула. Пошто на почетку нисмо видели још ни један елемент низа, обе променљиве иницијализујемо на нулу. Ако учитамо нулу, тада се текућа серију узастопних нула продужава и њену дужину увећавамо за један. Ако није нула, тада се текућа серија прекида и започиње нова, која има дужину 0 (јер је за сада празна и не садржи ни једну нулу).
Након завршетка читања сваке серије узастопних нула потребно је ажурирати дужину најдуже серије. То се дешава или када се наиђе на податак различит од нуле или након петље, када је последња евентуална серија нула завршена. Треба бити веома обазрив да се не заборави на последњу серију, тј. да се не заборави поређење текуће и најдуже серије након завршетка петље. Алтернатива је да се максимум ажурира приликом сваког увећања дужине текуће серије узастопних нула (на тај начин се заправо одређује дужина најдуже серије узастопних нула која се завршава на текућој позицији).
// 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;
}Сложеност овог алгоритма је \(O(n)\). Меморијска сложеност је \(O(1)\).
Дат је низ \(a\) целих бројева, дужине \(n\). Написати програм којим се одређује на колико начина можемо изабрати растуће сегменте у низу. Растући сегмент чине узастопни елементи низа \(a_p < a_{p+1} < \ldots < a_q\), за \(0 \leq p < q < n\).
Прва линија стандардног улаза садржи природан број \(n\) (\(2 \leq n\leq 10000\)), број елемената низа. У свакој од \(n\) наредних линија стандардног улаза, налази по један члан низа.
На стандардном излазу приказати број растућих сегмената датог низа.
5 1 3 4 -2 10
4
То су сегменти \([1, 3]\), \([1, 3, 4]\), \([3, 4]\), \([-2, 10]\).
Задатак можемо решити анализирајући све сегменте датог низа \(a\) и за сваки сегмент \(a_i, a_{i+1}, ..., a_j\) где је \(0 \leq i < j < n\) проверити да ли је растући и у складу са тим увећати бројач растућих сегмената. Пошто сегмената има \(O(n^2)\) и сваком се провера монотоности врши у линеарној сложености, ово решење је сложености \(O(n^3)\) (наравно, нису сви сегменти исте дужине и прецизна анализа би требало да у обзир узме дужине свих сегмената, међутим, и на тај начин би се израчунало да је алгоритам кубне сложености). Елементи су смештени у низ, па је меморијска сложеност \(O(n)\).
Ефикасније решење се може добити ако се провера монотоности врши инкрементално (да би се проверило да је сегмент \([i, j]\) растући довољно је да је \(a_j > a_{j-1}\) и да је сегмент \([i, j-1]\) растући или једночлан).
Време извршавања можемо унапредити и одсецањем. Приметимо да ако сегмент који чине елементи на позицијама \([i, j]\) није растући, онда нису растући ни сегменти \([i, j']\) за \(j \leq j' < n\), па за те сегменте не треба вршити проверу, што значи да је бројање растућих сегмената који почињу на позицији \(i\) могуће прекинути чим се пронађе неки сегмент који почиње на тој позицији и није растући.
Дакле, за сваку позицију \(i\) у низу (за свако \(0 \leq i < n-1\)) анализирамо један по један сегмент \([i, j]\) који на тој позицији почиње све док су ти сегменти растући и за сваки растући сегмент увећавамо бројач растућих сегмената за 1. Чим наиђемо на сегмент који није растући (тј. на елемент који је мањи од претходног), прелазимо на наредну позицију \(i\).
Пример 3.A.1. На пример у низу \([1, 3, 4, 5, 2, 6]\) анализирамо сегменте који почињу првим елементом низа тј. елементом \(a_0\) све док су сегменти растући, при томе пребројимо растуће сегменте \([1, 3]\); \([1, 3, 4]\) и \([1, 3, 4, 5]\). Слично полазећи од другог елемента низа пребројимо растуће сегменте \([3, 4]\) и \([3, 4, 5]\). Настављајући исти поступак за остале елементе низа пребројимо и растући сегмент \([4, 5]\), а затим и \([2, 6]\).
Сложеност овог алгоритма је \(O(n^2)\) и њиме се најефикасније могуће експлицитно набрајају сви растући сегменти. Меморијска сложеност је \(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;
}У претходно решењу се набрајају сви растући сегменти, међутим, у задатку је потребно израчунати само њихов број (а не и набројати их експлицитно), а то се може урадити и ефикасније.
Приметимо да у претходном примеру анализирајући растући сегмент који почиње од елемента \(a_0\) пролазимо и по растућим сегментима низа који почињу са \(a_1\) и \(a_2\). Ако је сегмент \([a_i, a_{i+1}, ..., a_{j}]\) растући, онда унапред знамо да су растући и сегменти \([a_i, a_{i+1}]\), \([a_i, a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{j}]\), затим \([a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{j}]\), па све до \([a_{j-1}, a_j]\), а да сегменти \([a_i, a_{i+1}, \ldots, a_{j+1}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{n-1}]\), затим \([a_{i+1}, a_{i+2}, \ldots, a_{j+1}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{n-1}]\) итд., закључно са \([a_{j}, \ldots, a_{n-1}]\) нису растући. Дакле, за сваку позицију из интервала \([i, j]\) тачно знамо све растуће сегменте који на њој почињу.
Растући сегмент \([a_i, a_{i+1}, \ldots, a_{i+k-1}]\) дужине \(k\) у себи садржи:
укупно \((k-1) + (k-2) + ... + 1\) растућих сегмената што износи \(\frac {k \cdot (k - 1)}{2}\).
До истог закључка можемо доћи и на следећи начин: сваки подсегмент \(a_p, a_{p+1}, \ldots, a_q\) где је \(i \leq p < q \leq i+k-1\) растућег сегмента \(a_i, a_{i+1}, ..., a_{i+k-1}\) је растући, почетак \(p\) и крај \(q\) подсегмента можемо изабрати на \(\frac {k \cdot (k - 1)}{2}\) начина.
Дакле, потребно је пронаћи дужине максималних растућих сегмената (оних који се не могу продужити додатним елементом тако да и даље остају растући), а затим број њихових растућих подсегмената уместо итерацијом, израчунати формулом. Наиме, након налажења неког максималног растућег сегмента \([i, j]\), можемо непосретно да израчунамо број растућих сегмената који почињу на свим позицијама између \(i\) и \(j\).
Према томе, у петљи анализирамо низ члан по члан почев од првог члана (\(i = 0\)) и одређујемо дужину \(t\) текућег растућег сегмента (ако је \(a_i < a_{i+1}\) увећавамо \(t\) за 1). Када дођемо до краја текућег растућег сегмента, увећавамо укупан број растућих сегмената \(br\) за \(\frac{t \cdot (t - 1)}{2}\) и почињемо анализу следећег растућег сегмента (\(t = 1\)). До краја максималног растућег сегмента се може стићи на два начина: или када је \(a_i \geq a_{i+1}\) или када се дође до краја низа. Напоменимо да за тај последњи растући сегмент увећавамо укупан број растућих сегмената изван петље (честа грешка је да се то заборави).
У сваком тренутку је довољно поредити само суседна члана низа, тако да није неопходно цео низ памтити у меморији, већ само два суседна члана низа (претходни и текући).
На претходно описан начин добијамо решење једним проласком по низу и временска сложеност му је \(O(n)\). Меморијска сложеност је \(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;
}Чувена веб-платформа жели да направи систем за анализу посете свом веб-сајту. Сакупљен је број посета током сваког минута у претходних неколико година (највише \(10\)). Написати програм који омогућава кориснику да за задате временске распоне (одређене минутима од почетка бројања) израчуна број посета током тих временских распона.
Са стандардног улаза се уноси број минута \(n\) (\(1 \leq n \leq 60\cdot 24\cdot 365\cdot 10\)), а затим у наредном реду \(n\) целих бројева између \(0\) и \(100\), раздвојених са по једним размаком, који представљају број посетилаца током сваког од тих \(n\) минута. Након тога се уноси број упита \(m\) (\(1 \leq m \leq 100000\)) и у наредних \(m\) редова се уносе временски периоди одређени редним бројем почетног минута \(a\) и крајњег минута \(b\) (\(0 \leq a \leq b < n\)).
На стандардни излаз исписати \(m\) целих бројева који представљају укупан број посетилаца у сваком од тих \(m\) периода.
5 1 2 3 4 5 3 0 4 1 3 2 2
15 9 3
Учитан је број посетилаца током 5 минута.
Директно решење подразумева да све бројеве учитамо у низ, а затим да за сваки упит изнова рачунамо збир одговарајућег сегмента низа.
// 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;
}Сложеност оваквог приступа је \(O(nm)\). Пошто се фаза учитавања и исписа података преплићу, учитавање би и испис података би требало додатно убрзати, но то не може поправити неефикасност овог наивног алгоритма.
Једноставно ефикасно решење је засновано на наредној идеји: уместо чувања елемената низа, можемо чувати низ збирова префикса низа. Збир сваког сегмента \([l, d]\) можемо разложити на разлику збира префикса до елемента \(d\) и префикса до елемента \(l-1\). Ако користимо ознаку \(\sum_{k=m}^{n} a_k\) која означава збир \(a_m + a_{m+1} + \ldots + a_n\), можемо записати да је
\[\sum_{k=l}^d a_k = \sum_{k=0}^{d} a_k - \sum_{k=0}^{l-1} a_k.\]
Збирови свих префикса се могу израчунати и сместити у додатни (а ако је уштеда меморије битна, онда чак и у оригинални) низ. Дакле, током учитавања елемената можемо формирати низ збирова префикса (рачунаћемо их инкрементално, јер се сваки наредни збир префикса добија увећавањем претходног збира префикса за текући елемент низа). Нека \(z_i\) означава збир елемената префикса одређеног позицијама из интервала \([0, i)\). Формирамо, дакле, низ \(z_i = \sum_{k=0}^{i-1} a_k\) (при чему је \(z_0 = 0\), збир празног префикса). Тада збир елемената у сегменту позиција \([l, d]\) израчунавамо као \(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;
}За учитавање бројева и формирање низа збирова префикса потребно нам је \(O(n)\) корака. Након оваквог претпроцесирања, збир сваког сегмента се може израчунати у времену \(O(1)\), па је укупна сложеност \(O(n + m)\).
Пошто се у овом задатку преплићу фаза учитавања и фаза исписа података на стандардни улаз и излаз, потребно је обратити пажњу на неефикасност која настаје због честог пражњења излазног бафера. Потребно је развезати cin и cout коришћењем cin.tie(0) и уместо помоћу endl у нови ред прелазити помоћу \n. Наравно, ово има смисла само у случају аутоматске примене програма на велике улазе и излазе - овим изменама програм престаје да ради коректно у интерактивном режиму.
Дат је низ \(a\) природних бројева дужине \(n\) и природан број \(k\). Написати програм који одређује број сегмента низа \(a\) (непразних поднизова узастопних елемената) чији је збир дељив са \(k\).
У првој линији стандардног улаза налази се природан број \(k\) (\(k\leq 10^5\)). Друга линија стандардног улаза садржи природан број \(n\) (\(n \leq 10^5\)). У следећој линији се налази \(n\) природних бројева (ти бројеви представљају редом елементе низа \(a\)), раздвојених са по једним размаком.
На стандарном излазу приказати колико постоји сегмената низа \(a\) чији је збир дељив са \(k\).
3 5 1 8 2 3 4
4
То су сегменти \((1,8)\), \((3)\), \((2,3,4)\) и \((1,8,2,3,4)\).
Директан начин да се задатак реши је да се угнежђеним петљама наброје сви сегменти, да се за сваки израчуна сума и да се провери да ли је дељива са \(k\), бројећи успут такве сегменте. Број је дељив са \(k\) ако и само ако даје остатак \(0\) при дељењу са \(k\), а знамо да је остатак при дељењу збира са бројем \(k\) заправо једнак збиру остатака тј. да важи да је \((a + b) \,\mathrm{mod}\,k = (a \,\mathrm{mod}\,k + b \,\mathrm{mod}\,k) \,\mathrm{mod}\,k\).
Дакле, за сваки сегмент довољно је израчунати збир по модулу \(k\), при чему за фиксирани леви крај сегмента, збир сваког наредног сегмента \([i, j]\) добијамо инкрементално, од збира сегмента \([i, j-1]\), додајући на њега број \(a_j\) и израчунавајући остатак добијеног збира при дељењу са \(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;
}Уз овако инкрементално израчунавање збира, сложеност алгоритма једнака је броју сегмената што је \(O(n^2)\).
Тражимо број сегмената \(a_p, a_{p+1}, \ldots, a_q\), за \(0\leq p\leq q < n\), таквих да је збир \(S_{pq} = a_p + a_{p+1} + ... + a_q\) дељив са \(k\).
Обележимо са \(S_0 = 0\), \(S_1 = a_0\), \(S_2 = a_0 + a_1\), итд., тј. обележимо са \(S_i\), \(0<i\leq n\) збир првих \(i\) елемената низа (\(S_i = a_0 + a_1 + ... +a_{i-1}\)). Збир \(S_{pq}\) можемо изразити као \(S_{q+1} - S_p\).
На основу особина операција по модулу важи да је \(S_{pq} \,\mathrm{mod}\,k = (S_{q+1} \,\mathrm{mod}\,k - S_p \,\mathrm{mod}\,k + k) \,\mathrm{mod}\,k\).
Према томе збир \(S_{pq}\) је дељив са \(k\) (тј. важи \(S_{pq} \,\mathrm{mod}\,k = 0\)) акко збирови \(S_{q+1}\) и \(S_p\) имају исти остатак при дељењу са \(k\) тј. ако је \(S_{q+1} \,\mathrm{mod}\,k = S_p\,\mathrm{mod}\,k\).
Обележимо са \(b_r\) број збирова \(S_i\) (за \(0 \leq i \leq n\)) који при дељењу са \(k\) дају остатак \(r\) (за свако \(0 \leq r < k\)). Сваки пар (различитих) збирова префикса који дају исти остатак \(r\) одређује тачно један сегмент чији је збир елемената дељив са \(k\). У скупу од \(m\) различитих елемената постоји тачно \(\frac{m(m-1)}{2}\) различитих парова. Зато је за свако \(r\) број сегмената који се добија комбинујући два збира који дају остатак \(r\) једнак \(\frac{b_r \cdot (b_r - 1)}{2}\). Према томе укупан број сегмената дељивих са \(k\) је \(\sum_{r=0}^{k-1}\frac{b_r \cdot (b_r - 1)}{2}\).
Остаје још само питање како избројати збирове префикса за сваки дати остатак тј. како израчунати све бројеве \(b_r\). Низом \(b\) дужине \(k\) памтимо број префикса чији збирови елемената дају остатке редом \(0, 1, 2, \ldots, k-1\) тако да је \(b_r\) једнак броју префикса чији збир елемената при дељењу са \(k\) даје остатак \(r\) (што је могуће, с обзиром на дату горњу границу броја \(k\)). Збирове префикса, наравно, израчунавамо инкрементално.
Полазни збир је \(S_0 = 0\), тако да све елементе низа \(b\) иницијализујемо на 0, осим вредности на позицији 0 коју иницијализујемо на 1. Збир текућег префикса одржавамо у променљивој \(S\) коју иницијализујемо на нулу. Учитавамо члан по члан низа \(x\), и при томе ажурирамо збир префикса (\(S\) постављамо на \((S + x)\,\mathrm{mod}\,k\)), увећавајући одговарајући бројач (вредност \(b_S\) увећавамо за 1).
Пример 3.A.2. Прикажимо рад овог алгоритма на примеру одређивања броја сегмената низа \(1, 8, 2, 3, 4\) који су дељиви са \(3\). Могући остаци су \(0\), \(1\) и \(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
Зато је коначан резултат \(\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 даје остатак 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 даје остатак 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;
}Временска сложеност овог алгоритма је, јасно, \(O(n)\). Приметимо да у овом решењу није било потребно користити низ за бројеве које уносимо, јер при уносу обрадимо сваки елемент, међутим, користимо помоћни низ дужине \(k\), па је меморијска сложеност \(O(k)\). Обратимо пажњу на то да ово може бити ограничавајући фактор, ако \(k\) може бити јако велики број (што у овом задатку није случај).
Камион превози терет током \(N\) километара пута. На пут креће празан и током пута утоварује и истоварује пакете. Ако се за сваки пакет зна на ком је километру пута утоварен, на ком је километру пута истоварен и колика му је маса, напиши програм који одређује колико је оптерећење камиона на сваком километру пута. Сматрати да се предмет утоварује на почетку, а истоварује на крају датог километра.
Са стандардног улаза се уноси број километара \(N\) (\(10\leq N 10000\)), затим, у наредном реду, број предмета \(M\) (\(0 \leq M \leq 10000\)), а након тога, у наредних \(M\) редова по три цела броја раздвојена размацима који представљају број километра на чијем је почетку утоварен предмет (цео број између \(0\) и \(N-1\)), број километра на чијем крају је истоварен (цео број између \(0\) и \(N-1\)) и на крају маса предмета (цео број између 1 и 10).
На стандардни излаз исписати масу терета у килограмима на сваком километру пута (иза сваке масе написати по један размак).
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
Директан начин је да се одржава низ \(M\) у којем се памти маса на камиону током сваког километра пута. Након учитавања сваког податка о предмету (почетног километра \(a\), завршног километра \(b\) и масе \(m\)), све вредности у низу \(M\) на позицијама од \(a\) до \(b\) (укључујући и њих) се увећавају за \(m\).
Проблем са овим решењем је то што предмети могу путовати велики број километара па се у сваком кораку врши ажурирање великог броја чланова низа (сложеност је у најгорем случају \(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;
}Задатак можемо решити ефикасније ако уместо да у низу \(M\) одржавамо масу у камиону у километру \(i\), одржавамо разлику између масе у километру \(i\) и \(i-1\) (на позицији \(0\) се чува маса у камиону у нултом километру). Дакле, уводимо низ \(R_i\) такав да је \(R_0 = M_0\), а \(R_i = M_i - M_{i-1}\), за \(1 \leq i < n\). Посматрајмо шта се дешава са низом \(R\) када се у низу \(M\) сви елементи на позицијама \(a\) до \(b\) увећају за \(m\).
Рецимо да ако је \(b = n-1\), тада не морамо разматрати вредност \(R_{b+1} = R_n\) (мада, униформности ради, можемо, што захтева да низ \(R\) садржи \(n+1\) елемент). Дакле, приликом сваког учитавања бројева \(a\), \(b\) и \(m\) потребно је само да увећавамо елемент \(R_a\) за \(m\), а да елемент \(R_{b+1}\) умањимо за \(m\).
Када знамо елементе низа \(R\) елементе низа \(M\) можемо једноставно реконструисати сабирањем елемената низа \(R\). Наиме, важи да је \(M_0 = R_0\), док је \(M_i = M_{i-1} + R_i\), тако да сваки наредни елемент низа \(M\) можемо израчунати као збир претходног елемента низа \(M\) и њему одговарајућег елемента низа \(R\). Приметимо да је заправо елемент \(M_i\) једнак збиру свих елемената од \(R_0\) до \(R_i\), јер је \(R_0 + R_1 + \ldots + R_i = M_0 + (M_1 - M_0) + \ldots + (M_i - M_{i-1}) = M_i\).
Укупна сложеност овог приступа је \(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;
}Идеја коришћена у овом задатку донекле је слична (заправо инверзна) техници одређивања збира сегмената као разлике два збира префикса. Може се приметити да се реконструкција низа врши заправо израчунавањем префиксних збирова низа разлика суседних елемената, што указује на дубоку везу између ове две технике. Заправо, разлике суседних елемената представљају одређени дискретни аналогон извода функције, док префиксни збирови представљају аналогију одређеног интеграла. Израчунавање збира сегмента као разлике два збира префикса одговара Њутн-Лајбницовој формули.
Познато је \(n\) рачунских послова које треба извршити и за сваки од њих је познато колико је времена потребно процесору да га изврши. Сваком од \(k\) идентичних процесора треба доделити тачно по један посао, при чему је циљ да сви процесори буду што равномерније оптерећени. Колика је најмања могућа разлика између времена извршавања два посла додељена тим процесорима?
Са стандардног улаза се уноси природан број \(n\) (\(1 \leq n \leq 50000\)) а затим и \(n\) природних бројева (између \(1\) и \(10^6\), раздвојених по једним размаком) који представљају време потребно за извршавање сваког од послова. У последњем реду се уноси број процесора \(k\) (\(1 \leq k \leq n\)).
На стандардни излаз исписати вредност најмање разлике између два посла додељена овим процесорима.
8 3 8 1 17 4 7 12 9 4
5
Најмања разлика се добија ако процесори извршавају послове који трају 8, 4, 7 и 9 јединица времена.
Најдиректнији начин да се реши задатак је да се испитају сви подскупови од \(k\) елемената скупа од \(n\) елемената и да се међу њима одабере најбољи. Ово решење је релативно компликовано имплементирати, а уз то је и веома неефикасно (број подскупова је \({n \choose k}\), што је \(O(n^k)\)).
Боље и ефикасније решење се заснива на сортирању. Наиме, када се полазни послови сортирају по времену извршавања, процесорима треба доделити неких узастопних \(k\) послова. Претпоставимо да након сортирања имамо низ \(a_0, a_1, \ldots, a_{n-1}\). Процесорима треба доделити редом послове од \(a_i\), до \(a_{i+k-1}\), за неко \(0 \leq i \leq n - k\).
Докажимо претходну чињеницу. Претпоставимо супротно, да послови који дају најмањи распон не чине узастопан низ и да сваки узастопни низ послова дужине \(k\) има строго већи распон од распона скупа узетих пакета. Нека је први узети посао \(a_i\). Тада сигурно постоји неки посао \(a_j\) за \(i < j < i+k\) који није узет, а уместо њега је узет неки пакет \(a_{j'}\) за неко \(i + k \leq j' < n\). Нека је \(j'\) последњи пакет који је узет. Међутим, када би процесор који извршава посао \(a_{j'}\) заменио тај посао за \(a_{j}\), распон би се сигурно смањио или бар остао исти (јер би последњи узети пакет тада био неки пакет \(a_{j''}\), за \(j'' < j'\), а пошто је низ сортиран неопадајуће, важи да је \(a_{j''} \leq a_{j}\), па и \(a_{j''} - a_i \leq a_{j'} - a_i\). Даљим заменема истог типа можемо доћи до тога да су сви узети пакети узастопни, а да је распон мањи или једнак полазном, што је у контрадикцији са тим да је распон полазног скупа узетих пакета строго мањи од распона било којег низа \(k\) узастопних пакета.
Разматрање претходног типа је карактеристично за такозване грамзиве (тј. похлепне) алгоритме, о којима ће више речи бити касније.
На основу претходног, јасно је да низ трајања послова треба најпре сортирати и затим одредити минимум разлика вредности \(a_{i+k-1} - a_{i}\), за \(0 \leq i \leq n - k\), коришћењем уобичајеног алгоритма за налажење минимума.
Сложеношћу овог алгоритма доминира сложеност корака сортирања, а она је \(O(n\log n)\), ако се користе библиотечке имплементације. Након сортирања, минимум се одређује у \(n-k\) корака, тј. у линеарној сложености \(O(n)\) (када је \(k\) мало, број корака може бити веома близак \(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;
}Две речи су анаграми ако се једна може добити од друге само променом редоследа слова (на пример, трава и ватра). Напиши програм који у датом скупу речи проналази највећи подскуп речи које су међусобни анаграми.
Са стандардног улаза се уноси број речи \(n\) (\(0 \leq n \leq 50000\)), а затим у \(n\) наредних линија по једна реч полазног скупа (све речи се састоје само од малих слова енглеског алфабета и имају највише 200 карактера).
На стандардни излаз исписати величину највећег подскупа полазног скупа речи, у коме су све речи једна другој анаграми.
10 tommarvoloriddle viviandarkbloom iamlordvoldemort danabnormal normdanabal vladimirnabokov vladimirkoborov bladvakvinomori damonalbarn dorianvivalkomb
4
Најбројнију скуп анаграма чине речи
viviandarkbloom vladimirnabokov bladvakvinomori dorianvivalkomb
Провера да ли су две речи анаграми може се заснивати на сортирању слова две речи и затим поређењу да ли су добијене речи исте. Алтернативно, провера да ли су две речи анаграми може се урадити тако што се израчунају бројеви појављивања сваког од 26 карактера енглеске абецеде и затим се пореде ти бројеви за две задате речи. У оба приступа, сваку реч канонизујемо и уместо поређења полазних речи, можемо да поредимо њихове канонске облике. Канонизовањем добијамо низ канонских представника и желимо да у том низу пронађемo скуп еквивалентних елемената (једнаких канонских представника) који је највеће кардиналности од свих таквих подскупова.
Једно могуће решење је да сортирамо карактере сваке учитане речи (абецедно), а затим да сортирамо тако добијени низ речи (лексикографски абецедно), да би се идентичне сортиране речи нашле једна иза друге. На тако добијен низ примењујемо проналажење најдуже серије једнаких узастопних елемената.
Сложеност сортирања слова свих појединачних речи је \(O(n\cdot m\log{m})\), где је \(n\) број речи, а \(m\) максимални број слова у речи. Сложеност сортирања низа свих речи се може проценити на \(O(n \log{n})\), јер је реално очекивати да ће се лексикографско поређење две речи вршити веома ефикасно (речи су кратке, а реално је очекивати и да су “шаренолике”, тј. да ће се њихов поредак моћи одредити већ након поређења малог броја почетних карактера). Пошто је број слова \(m\) веома мали, можемо га сматрати константим и сложеност алгоритма грубо оценити са \(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;
}Дат је низ који садржи природне бројеве и цео број \(D\). Напиши програм који одређује који се од неколико датих низова може од полазног добити разменама елемената који су тачно на растојању \(D\).
Са стандардног улаза се учитава цео број \(d\) (\(1 \leq d \leq k\)), затим цео број \(k\) (\(5 \leq k \leq 10^5\)), затим цео број \(n\) (\(1 \leq n \leq 10\)) и након тога \(n\) низова дужине \(k\) чији су елементи раздвојени размацима.
На стандардни излаз за сваки низ од другог до последњег исписати da ако се може трансформисати у први разменама елемената на растојању \(d\), тј. ne у супротном.
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
Приметимо да се елемент на позицији \(0\), након пермутације може наћи само на позицији \(d\), \(2d\), \(3d\) итд. Елемент на позицији \(1\) се може наћи само на позицијама \(d+1\), \(2d+1\), \(3d+1\) итд. На крају, елемент на позицији \(d-1\) се може наћи само на позицијама \(d+d-1\), \(2d+d-1\), \(3d+d-1\) итд.
Пример 3.A.3. На пример, у низу, \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), ако је растојање \(d\) једнако \(3\), можемо размењивати само елементе \(1\), \(4\) и \(7\), затим елементе \(2\), \(5\) и \(8\) и на крају \(3\), \(6\) и \(9\). Не постоји никакав начин да се, на пример, елемент \(2\) или елемент \(9\) нађу на позицији елемента \(1\) или елемента \(7\).
Дакле, низ је суштински издељен на \(d\) партиција, тако што су два елемента у истој партицији ако и само ако су на растојању \(i\cdot d\), за неко целобројно \(i\). Партиције су међусобно независне у смислу да се разменама могу пермутовати само они елементи који се налазе у истој партицији. Један низ се може трансформисати у други разменама елемената на растојању \(d\), ако и само ако се свака партиција може трансформисати у одговарајућу партицију другог низа, разменама суседних елемената у оквиру те партиције.
Пример 3.A.4. На пример, низ \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\) се може трансформисати у низ \(7\), \(2\), \(9\), \(1\), \(8\), \(6\), \(4\), \(5\), \(3\), зато што се партиција \((1, 4, 7)\) може трансформисати у \((7, 1, 4)\), партиција \((2, 5, 8)\) се може трансформисати у \((2, 8, 5)\), а партиција \((3, 6, 9)\) се може трансформисати у партицију \((9, 6, 3)\). Пошто свака партиција чини низ за себе, остаје да се реши питање: да ли се дати низ бројева може трансформисати у други низ операцијама размене суседних елемената?
Постоје разни начини да се на ово питање одговори, а један од најефикаснијих се заснива на чињеници да се сваки низ може сортирати искључиво разменама узастопних елемената (на пример, Bubble Sort алгоритам врши управо такво сортирање). То значи да се један низ трансформацијама узастопних елемената може трансформисати у други низ ако и само ако се сортирањем и једног и другог добија исти низ. При том, сортирање не мора бити вршено само разменама узастопних елемената већ и много ефикаснијим алгоритмима (јер је резултат сортирања јединствено одређен и ако знамо да се неким ефикасним алгоритмом сортирања од почетног низа добија неки сортиран низ, тај исти низ би се добио и да се сортирање врши само разменама узастопних елемената). Један од начина да претходна разматрања искомбинујемо у решење је да уведемо операцију проналажења канонског представника за сваки низ у односу на дати параметар \(d\), тако што ћемо сваку његову партицију канонизовати тј. сортирати.
Пример 3.A.5. На пример, за \(d=3\) низ \(2, 16, 41, 15, 12, 31, 11, 9\) се дели на партиције \((2, 15, 11)\), \((16, 12, 9)\), \((41, 31)\), свака се партиција се независно сортира и тиме се добија \((2, 11, 15)\), \((9, 12, 16)\), и \((31, 41)\), чиме се добија канонски представник \(2, 9, 31, 11, 12, 41, 15, 16\). Два низа ће се моћи d-пермутовати један у други ако и само ако су њихови овако дефинисани канонски представници једнаки.
Пошто у оквиру канонизације користимо библиотечки алгоритам сортирања можемо претпоставити да ће његова сложеност за низ дужине \(m\) бити \(O(m\cdot \log{(m)})\). Пошто се сортира \(d\) партиција, а свака је дужине око \(k/d\), и врши се пребацивање елемената у помоћни низ и назад, сложеност најгорег случаја канонизације се може проценити као \(O(d\cdot (k/d\cdot \log{(k/d)} + 2(k/d)))\) тј. \(O(k\cdot \log{(k/d)})\). Зато израчунавање канонских представника свих низова може да се процени на \(O(n\cdot k\cdot \log{(k/d)})\). С обзиром на то да се поређење једнакости два канонска представника врши у времену \(O(k)\), а ово поређење се врши \(n-1\) пут, имамо додатно још \(O(nk)\) операција. За укупну сложеност алгоритма се зато може узети \(O(n\cdot k \cdot \log{(k/d)})\), тј. \(O(k\cdot \log{(k/d)})\) јер \(n\), за разлику од \(k\) има веома малу вредност (практично се може сматрати константом).
Напоменимо да је након канонизације сваке партиције низа \(T_i\) било могуће проверавати једнакост са одговарајућом партицијом низа \(S\), чиме би се мало брже могло констатовати да се низ не може трансформисати, али би се код донекле закомпликовао. Слично, коришћење помоћног низа није било неопходно за чување партиција, већ је било могуће канонизацију вршити у оквиру низа \(S\), разменама његових елемената из истих партиција, али тада не би било могуће користити библиотечку функцију сортирања, што би такође доста закомпликовало код. Асимптотска сложеност најгорег случаја би остала иста.
#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 akо i samo ako su im kanonski predstavnici jednaki)
// i ispisujemo rezultat u trazenom formatu
cout << (s == t ? "da" : "ne") << endl;
}
return 0;
}Написати програм који за низ затворених интервала \([a_i, b_i], i=0, 1, \cdots, n-1\) одређује укупну дужину делова праве које покривају и минимални број интервала којим се може постићи покривање истог скупа тачака праве (тај скуп интервала може се добити укрупњивањем полазних интервала, тј. обједињавањем полазних интервала који се секу).
У првој линији стандардног улаза учитава се број интервала \(n\) (\(1 \le n \le 50000\)), а у наредних \(n\) линија парови целих бројева за које важи \(-10^6 \le L_i < R_i \le 10^6\) који представљају леви и десни крај интервала.
Два броја: у првом реду стандардног излаза број који представља дужину дела праве коју покривају учитани интервали, у следећем реду број интервала формираних укрупњавањем међусобно повезаних интервала.
4 1 3 5 8 2 4 6 7
6 2
Интервали \([1, 3]\) и \([2, 4]\) се могу укрупнити у интервал \([1, 4]\), а интервали \([5, 8]\) и \([6, 7]\) у интервал \([5, 8]\).
Задатак можемо решити тако што један по један интервал додајемо у скуп укрупњених интервала формираних на основу претходно обрађених интервала. Додавање новог интервала у колекцију укрупњених може се реализовати тако што се сви укрупњени интервали који се секу са интервалом који се тренутно обрађује уклоне из колекције укрупњених интервала, затим се направи њихова унија са интервалом који се додаје и да се тако добијен укрупњени интервал дода у тренутну колекцију укрупњених интервала. За ово нам је потребно да имплементирамо проверу да ли се два интервала секу и израчунавање уније два интервала (што можемо урадити коришћењем минимума и максимума). С обзиром на то да нам је потребно да из колекције укрупњених интервала (ефикасно) уклањамо елементе док je обилазимо, погодно је да је представимо повезаном листом. У језику C++ можемо употребити колекцију list.
Уклањање елемента листе врши се у времену \(O(1)\). Пошто се приликом додавања сваког новог интервала обилазе сви претходно укрупњени интервали (а њих може бити исто онолико колико и полазних интервала, ако су интервали дисјунктни), сложеност у најгорем случају је \(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;
}Ефикасан алгоритам можемо добити ако приликом додавања новог интервала некако избегнемо потребу да се обилазе сви до тада укрупњени интервали. Основна идеја је да интервале обилазимо у неопадајућем поретку координата левих крајева. Ако интервале представимо уређеним паровима, библиотечке функције сортирања ће их сортирати управо на тај начин. С обзиром на такав редослед обиласка, сваки нови интервал се може сећи само са последњим укрупњеним интервалом (и стога се може прескочити анализа осталих укрупњених интервала).
С обзиром на то да нас не занимају сами укрупњени интервали, већ само њихов број и дужина, током извршавања петље у којој обрађујемо један по један интервал одржаваћемо само три податка: дужину дела праве коју покривају до тада обрађени интервали, број укрупњених интервала који покривају тај део праве (покривач тог дела праве) и позицију \(D_{max}\) десног краја последњег укрупњеног интервала (то је уједно најдешња тачка свих до сада обрађених интервала).
Иницијализацију можемо извршити на основу првог интервала (он сам покрива део праве чија је дужина једнака његовој, тренутно је формиран један укрупњени интервал и десни крај је једнак десном крају тог првог интервала).
У сваком кораку проширујемо досадашњи покривач интервалом \([L_i, D_i]\), при чему је последњи укрупњени интервал \([L, D_{max}]\). Могућа су следећа 3 случаја:
\(D_{max} < L_i\) — интервал \([L_i, D_i]\) се не може прикључити ни једном већ постојећем укрупњеном интервалу, нити се то може урадити ни са једним наредним интервалом (јер су због сортираности сви они десно од текућег). Текући интервал зато започиње нови укрупњени интервал, па увећавамо број укрупњених интервала за 1, дужину покривеног дела праве повећавамо за дужину текућег интервала, док се \(D_{max}\) коригује на \(D_i\).
\(L \leq L_i \leq D_{max} \leq D_i\) — досадашњи покривач тј. његов последњи укрупњени интервал \([L, D_{max}]\) се сече са интервалом \([L_i, D_i]\) па се проширује за дужину \(D_i - D_{max}\), а крај \(D_{max}\) се коригује на \(D_i\), при чему се број укрупњених интервала не мења.
\(L \leq L_i \leq D_i \le D_{max}\) — текући интервал \([L_i, D_i]\), је комплетно садржан у неком укрупњеном интервалу \([L, D_{max}]\) и може се прескочити без ажурирања покривача који се конструише.
Сортирање \(n\) интервала врши се у времену \(O(n\log{n})\). Након тога, обрада интервала врши се једним проласком кроз низ и сложеност те фазе је \(O(n)\). Укупном сложеношћу, дакле, доминира сортирање и она износи \(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) {
// zapоcinjemo 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) {
// zapоcinjemo 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;
}Овај задатак је поновљен у циљу илустровања различитих техника решавања.
За сваког купца исписати по један цео број у засебном реду – цену најскупљег поклона који је мањи или једнак од \(x_i\).
Уколико такав поклон не постоји, исписати \(-1\).
5 20 10 70 35 50 3 5 40 70
-1 35 70
Након што се низ цена сортира, задатак се веома ефикасно може решити бинарном претрагом, примењену изнова на сваки буџет \(b_i\). Кренимо од следеће инваријанте. Током петље одржаваћемо два показивача l и d, тако да су све цене лево од показивача l такве да се поклон може купити за дати буџет, а све цене десно од показивача d такве да се поклон не може купити за дати буџет, док су на позицијама из интервала \([l, d]\) цене које алгоритам још није испитао. Дакле, претпоставимо да је стање низа следеће:
| l | d | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | ? | ? | ? | ? | ? | > | > | > |
У почетку су све цене непрегледане, па интервал \([l, d]\) треба да се поклопи са целим низом, тј. \(l\) треба иницијализовати на \(0\), а \(d\) на \(n-1\).
У сваком кораку петље одређујемо средишњу позицију \(s\) у интервалу \([l, d]\). Да би се смањила могућност прекорачења, ту позицију уместо помоћу \(\left\lfloor{\frac{l+d}{2}}\right\rfloor\), можемо израчунати помоћу \(l + \left\lfloor{\frac{d-l}{2}}\right\rfloor\).
Ако се елемент на позицији \(s\) уклапа у дати буџет тј. ако је цена \(c_s \leq b_i\), тада се, због сортираности, могу приуштити и сви поклони на позицијама лево од \(s\), па инваријанта остаје на снази ако се \(l\) помери на позицију \(s+1\).
У супротном, ако је \(b_i < c_s\), тада се, због сортираности, не може пришутити ни један поклон на позицијама десно од \(s\), па инваријанта остаје на снази ако се \(l\) помери на позицију \(s-1\).
Петља се извршава док год има непрегледаних цена, тј. док је интервал \([l, d]\) непразан. Када се претрага заврши, стање у низу је следеће.
| d | l | |||||||||
| \(\leq\) | \(\leq\) | \(\leq\) | \(\leq\) | \(\leq\) | > | > | > | > | > | > |
На основу инваријанте знамо да се сваки елемент лево од \(l\) може приуштити, а да се ни један десно од \(d\) не може, па се стога тражени највреднији поклон налази на позицији \(d=l-1\). Ако су сви поклони прескупи, крајње вредности ће бити \(d=-1\) и \(l=0\), па се враћањем вредности \(d\) и у том случају добија коректан резултат.
Функција се зауставља јер се у сваком кораку ширина интервала \([l, d]\) стриктно смањује (захваљујући заокруживању наниже приликом одређивања средишње позиције \(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;
}Написати програм који проверава да ли у строго растућем низу елемената постоји позиција \(i\) таква да се на позицији \(i\) налази вредност \(i\) тј. да важи да је \(a_i = i\) (позиције се броје од нуле).
Са стандардног улаза се уноси број \(n\) (\(0 \leq n \leq 10^5\)), а затим и строго растући низ од \(n\) целих бројева (раздвојених размацима).
На стандардни излаз исписати индекс \(i\) такав да је \(a_i = i\) или текст nema ако такав индекс не постоји у низу. Ако у низу постоји више таквих индекса исписати најмањи од њих.
6 -3 -1 1 3 5 7
3
Директан начин да се задатак реши је да се употреби линеарна претрага и да се позиције проверавају редом, од \(0\) до \(n-1\) све док се не пронађе прва позиција која задовољава услов или док се не дође до краја низа.
Сложеност линеарне претраге је \(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;
}Размотримо низ -10 -4 1 3 4 9 11. Елемент -10 је мањи од своје позиције 0 за 10. Елемент -4 је мањи од своје позиције 1 за 5, елемент 1 је мањи од своје позиције 2 за 1. Елементи 3 и 4 су једнаки својим позицијама. Елемент 9 је већи од своје позиције 5 за 4 док је елемент 11 већи од своје позиције 6 за 5. Примећујемо одређену монотоност у овом низу, што није случајно. Покажимо да је низ \(a_i - i\) неопадајући. Посматарајмо два елемента \(a_i\) и \(a_j\) на позицијама на којима је \(0 \leq i < j\). Пошто је низ \(a\) строго растући, важи да је \(a_{i+1} > a_i\), па је \(a_{i+1} \geq a_i + 1\). Слично је \(a_{i+2} > a_{i+1}\), па је \(a_{i+2} \geq a_{i+1} + 1 \geq a_{i} + 2\). Настављањем оваквог закључивања добијамо да важи да је \(a_j \geq a_i + (j-i)\). Зато је \(a_j - j \geq a_i - i\). Ако је \(a_i = i\), тада је \(a_i - i = 0\). Решење, дакле, можемо одредити тако што бинарном претрагом проверимо да ли неопадајући низ \(a_i - i\) садржи нулу и ако садржи, тада је решење прва позиција на којој се та нула налази.
Један од најлакших начина да реализујемо бинарну претрагу је да употребимо библиотечку функцију. Пошто нам је потребна прва позиција нуле у трансформисаном низу, не можемо употребити функцију binary_search, већ морамо употребити функцију lower_bound.
Сложеност бинарне претраге је \(O(\log{n})\), међутим, временом доминира учитавање и трансформисање низа које захтева \(O(n)\) корака.
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;
}Бинарна претрага се може прилагодити и применити тако да се не модификује низ.
Један могући покушај имплементације прати основну варијанту бинарне претраге у којој се тражи елемент унутар низа. Након налажења средишњег елемента можемо проверити следеће услове.
Када се пронађе неки елемент који задовољава дати услов, потребно је проверити да ли је најмањи. Пошто други елементи који задовољавају дати услов могу бити само непосредно уз пронађени елемент, најмањи елемент који задовољава услов проналазимо крећући се улево тј. мењајући текући елемент њему претходним све док тај претходни елемент задовољава тражени услов (или док евентуално не дођемо до самог почетка низа). Нагласимо да је оваква имплементација бинарне претраге заправо лоша, јер у случају када у низу постоји велики број елемената који су на свом месту, померање улево може трајати дуго.
Сложеност бинарне претраге је \(O(\log{n})\), међутим, даља претрага за првим елементом који задовољава услов је у најгорем случају сложености \(O(n)\), што поништава предности бинарне претраге. Временом свакако доминира учитавање и трансформисање низа које захтева \(O(n)\) корака.
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;
}Размотримо низ бројева \(210, 2310, 390, 30, 510, 66, 6, 138, 46, 106, 59, 17, 23\). Он је интересантан из неколико разлога. На пример, првих пет бројева је дељиво са 10, а после ниједан број није дељив са 10. Првих десет бројева је парно, а после су сви бројеви непарни. Првих осам бројева је дељиво са 6, а после ниједан број није дељив са 6. Прва два броја су дељива са 210, а после ниједан број није дељив са 210, итд. Покушај да пронађеш још оваквих правилности. Напиши програм који за сваки унети делилац одређује колико бројева је дељиво њимe. Сматрати да за сваки унети делилац важи наведена правилност.
Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 10^5\)), а затим у наредном реду \(n\) природних бројева (мањих од \(10^{18}\)) раздвојених по једним размаком. Након тога се до краја улаза уносе делиоци (сваки у посебном реду). За сваки делилац се сигурно зна (и то није потребно проверавати) да се у низу налазе прво бројеви који јесу, а затим бројеви који нису дељиви тим делиоцем.
За сваки унети делилац у посебном реду исписати број елемената низа који су њиме дељиви.
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
Наивно решење може бити засновано на примени линеарне претраге (бројању елемената филтриране серије) да би се одредило колико у низу постоји елемената дељивих са учитаним делиоцем.
Ако низ има \(n\) елемената, а постоји \(m\) делилаца, сложеност овог решења је \(O(mn)\). Приметимо да ово решење ни на који начин не користи особину низа да прво иду елементи који су дељиви, а онда елементи који нису дељиви датим делиоцем.
Захваљујући интересантној особини низа, задатак ефикасно може бити решен применом алгоритма бинарне претраге преломне тачке. Заиста, по услову задатка у низу се налазе прво сви елементи задовољавају услов \(P\) (дељиви су са текућим бројем \(k\)), а затим сви елементи који не задовољавају услов \(P\) (нису дељиви са текућим бројем \(k\)). Стога се може применити алгоритам бинарне претраге преломне тачке.
Пошто је сложеност библиотечке функције бинарне претраге \(O(\log{n})\), сложеност одговора на свих \(m\) упита је \(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;
}Задатак можемо решити и помоћу библиотечких функција за бинарну претрагу, међутим, потребно је прилагодити их задавањем функције поређења (којом се кодира услов \(P\)).
Да бисмо нашли први елемент који задовољава неки услов, у језику C++ можемо употребити функцију upper_bound, на мало необичан начин. У случају претраге преломне тачке битни су нам само елементи низа, а не елемент који се тражи (јер заправо не тражимо никакав конкретан елемент унутар низа). Зато као елемент који тражимо можемо навести било шта (на пример, нулу). Кључно је дефинисати функцију поређења (која се прослеђује као последњи аргумент функцији upper_bound), тако да враћа информацију о томе да су елементи који не задовољавају услов мањи од траженог, док елементи који задовољавају услов нису мањи од траженог. Функција поређења, дакле, треба само да анализира свој други елемент и да врати информацију о томе да ли он задовољава услов (у нашем примеру, тражимо први елемент који није дељив бројем \(d\) и то је услов који се проверава у склопу функције поређења).
Могли бисмо употребити и функцију lower_bound, али би тада у функцији поређења било потребно разменити редослед аргумената (њој је тражена вредност увек други аргумент) и негирати услов.
Пошто је сложеност библиотечке функције бинарне претраге \(O(\log{n})\), сложеност одговора на свих \(m\) упита је \(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;
}Апликације за слање мејлова чувају раније коришћене мејл адресе а онда помажу корисницима тако што на основу њих допуњавају започет унос нове мејл адресе (тзв. опција аутоматског допуњавања, енгл. aucomplete). Написати програм који ефикасно имплементира ову функционалност.
Са стандардног улаза се учитава број мејл адреса \(n\) (\(1 \leq n \leq 10^5\)), а затим у \(n\) наредних редова по једна мејл адреса. Након тога се уноси број започетних мејл адреса које треба допунити \(m\) (\(1 \leq m \leq 10^5\)), а након тога и тих \(m\) започетих мејл адреса.
На стадардни излаз за сваку започету мејл адресу исписати број мејл адреса које је допуњавају.
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
На пример, почетак laz допуњавају адресе laza@gmail.com и lazica@hotmail.com.
Задатак се може решити тако што се за сваки префикс адресе линеарном претрагом целог низа пронађу оне адресе које почињу тим префиксом.
Ако постоји \(n\) елемената низа адреса, сложеност линеарне претраге је \(O(n)\), па ако се испитује \(m\) префикса, укупна сложеност је \(O(mn)\).
Задатак се ефикасније може решити тако што се адресе сортирају, а затим се за сваки префикс бинарном претрагом проналазе адресе које почињу тим префиксом. Прва таква адреса је најмања адреса (у лексикографском поретку) која је већа или једнака од унетог префикса. Иако се може помислити да се након њеног проналаска, остале адресе могу пронаћи у петљи која наставља даље све док адресе почињу тим префиксом, то решење је потенцијално неефикасно (јер може бити пуно таквих адреса). Зато је боље новом бинарном претрагом одредити прву адресу која не почиње тим префиксом, што се може урадити тако што се последњи карактер тог префикса увећа и пронађе позиција адресе која је већа или једнака од тако трансформисаног префикса.
Ако постоји \(n\) елемената низа адреса, сложеност иницијалног сортирања је \(O(n \log{n})\), а сложеност сваке од ове две бинарне претраге је \(O(\log{n})\), па ако се испитује \(m\) префикса, укупна сложеност је \(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;
}Ако је \(s\) ниска, онда нека \(s^n\) означава ниску која се добија ако се свако слово понови \(n\) пута (нпр. \((xyz)^3\) је \(xxxyyyzzz\)). Напиши програм који одређује највећи број \(n\) такав да је \(s^n\) подниз дате ниске \(t\) (то значи да се сва слова ниске \(s^n\) јављају у ниски \(t\), у истом редоследу као у \(s^n\), али не обавезно узастопно).
У првом реду стандардног улаза налази се ниска \(s\), а у другом ниска \(t\).
На стандардни излаз напиши тражени број \(n\).
xyz xaxxybyxyxzyzzb
3
Дефинисаћемо функцију којом проверавамо да ли је \(s^n\) подниз ниске \(t\). Један начин је да експлицитно формирамо ниску \(s^n\) и да применимо алгоритам провере подниске. Мало боље решење је да се алгоритам модификује тако да се избегне ефективно креирање ниске \(s^n\). Функција провере прима ниску \(s\), број \(n\) и ниску \(t\), а затим сваки од карактера из \(s\) тражи \(n\) пута унутар ниске \(t\).
Када на располагању имамо функцију за проверу, тада оптималну вредност \(n\) можемо наћи линеарном претрагом. Кључна опаска је да ако \(s^n\) није подниз \(t\) за неко \(n\), онда \(s^k\) није подниз \(t\) ни за једно \(k \geq n\). Зато ћемо степен увећавати кренувши од \(1\) све док не наиђемо на прву вредност \(n\) за коју \(s^n\) није подниз \(t\) и тада ћемо знати да је оптимална вредност \(n-1\).
Провера да ли је ниска \(s^n\) подниз ниске \(t\) врши се у линеарном времену у односу на збир дужина ниске. Ако је \(T\) дужина ниске \(t\), време за једну проверу је \(O(T)\). Провере се врше све док се не нађе оптимално \(n\). Оно највише може бити \(\left\lfloor{\frac{T}{S}}\right\rfloor\), где је \(S\) дужина ниске \(s\) па је сложеност \(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;
}Чињеница да постоји одређени облик монотоности у проблему, нам омогућава да тражену оптималну вредност нађемо бинарном претрагом. Важи да ако \(s^n\) није подниз \(t\) за неко \(n\), онда \(s^k\) није подниз \(t\) ни за једно \(k \geq n\), а да ако је \(s^n\) подниз \(t\) за неко \(n\), онда је \(s^k\) подниз \(t\) за свако \(k \leq n\). Зато се са порастом \(n\) јављају се прво оне вредности за које услов важи, након који иду вредности за које услов не важи.
Сигурни смо да се оптимална вредност налази у интервалу од \(0\) па до \(\left\lfloor{\frac{|t|}{|s|}}\right\rfloor\). Бинарном претрагом проналазимо преломну тачку, тј. најмању вредност \(n\) такву да \(s^n\) није подниз \(t\). Приметимо да у овом случају не претражујемо вредности у неком низу, већ је низ потенцијалних вредности \(n\) који се претражује само имплицитан, па бинарну претрагу имплементирамо ручно.
Провера да ли је ниска \(s^n\) подниз ниске \(t\) врши се у линеарном времену у односу на збир дужина ниске. Ако је \(T\) дужина ниске \(t\), време за једну проверу је \(O(T)\). Интервал који се претражује је \([0, \frac{T}{S}]\), где је \(S\) дужина ниске \(s\), па је сложеност \(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;
}Графички дизајнер је преуредио неколико слова у једном фонту и жели да своје промене прикаже клијенту. У дугачком тексту је потребно да одабере најкраћи део (сегмент узастопних слова) који садржи сва слова која је променио.
У првој линији стандардног улаза налази се текст (једноставности ради претпоставимо да је састављен само од малих слова енглеског алфабета) чија је дужина највише \(10^5\) карактера. У другој линији се налази скуп слова (опет, претпоставимо малих слова енглеског алфабета) које је дизајнер променио (слова су написана једно до другог, без размака и без понављања).
На стандардни излаз исписати један цео број који представља дужину најкраћег дела текста који садржи све карактере датог скупа. Ако такав део текста не постоjи, исписати nema.
dobardansvimakakoste arnk
10
ababababab abc
nema
Најдиректнији алгоритам био би да се разматрају све подниске (оне су одређене индексима \(0 \leq i \leq j < n\)), да се за сваку од њих провери да ли је исправна тј. да ли садржи све карактере из скупа \(S\) и да се међу свим исправним поднискама пронађе најкраћа. Овакву претрагу грубом силом је веома једноставно имплементирати.
// 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;
}Проверава се \(O(n^2)\) подниски, и за сваку се вржи \(m\) линеарних провера, па се може показати да је сложеност је \(O(n^3\cdot m)\) где је \(n\) дужина текста, а \(m\) број карактера у скупу \(S\). Параметар \(m\) има малу вредност, али димензија \(n\) може бити велика, па је овај алгоритам веома неефикасан.
Када подниска одређена позицијама \(i\) и \(j\) садржи све карактере из скупа \(S\), онда и све подниске одређене већим вредностима \(j\) такође садрже све карактере из тог скупа, а за њих знамо да су дуже и нема потребе разматрати их (вршимо одсецање у претрази).
Пример 3.A.6. На пример, ако се унутар ниске xCxxBxxBxxAxxBxxCxxxxBxAxAxCxxxBx тражи подниска у коме се јављају слова из скупа ABC. Након проналаска ниске CxxBxxBxxA, која садржи све потребне карактере, нема потребе разматрати њена проширења надесно (на пример, подниску CxxBxxBxxAxxB).
Дакле прва пронађена исправна подниска која почиње на позицији \(i\) уједно је и најкраћа исправна подниска пронађена на тој позицији. Зато је одмах након проналаска прве исправне пондиске и ажурирања вредности најмање дужине могуће прекинути унутрашњу петљу (наредбом break).
Ова оптимизација не поправља асимптотску сложеност најгорег случаја (на пример, у случајевима када не постоји тражена подниска), али у многим случајевима може довести до убрзања.
Приметимо да тражена најкраћа подниска мора да почиње и да се завршава карактером из скупа \(S\) (рећи ћемо да су само ти карактери релевантни). У супротном би карактери на почетку и на крају подниске који нису у скупу \(S\) могли да буду уклоњени чиме би се добила краћа подниска која би и даље садржала све карактере из скупа \(S\). Такође, приликом провере да ли одређена подниска садржи све карактере из \(S\), потребно је анализирати само оне њене позиције на којима су карактери из \(S\). Зато ћемо у фази претпроцесирања само изградити низ позиција релевантних карактера у ниски (рећи ћемо да су то релевантне позиције) и затим ћемо разматрати само подниске који почињу и завршавају се на позицијама унутар тог низа (на тај начин вршимо одсецање у претрази).
Ако се провера да ли је позиција релевантна врши линеарном претрагом ниске S, Време потребно за изградњу низа релевантних позиција је \(O(n\cdot m)\) (пошто је \(m\) веома мали број, ово је практично линеарно тј. \(O(n)\), а може се снизити и на \(O(m + n)\) ако би се скуп \(S\) представио својом карактеристичном функцијом – асоцијативним низом 26 логичких вредности).
Иако се овим не снижава сложеност најгорег случаја (на пример, када су сви карактери ниске у скупу \(S\)), у случају да постоји значајан број карактера у тексту који нису у скупу \(S\), претрага се може убрзати.
Проверу да ли се сви карактери из скупа \(S\) јављају унутар подниске имеђу две релевантне позиције \(i\) и \(j\) можемо извршити тако што одредимо скуп свих релевантних карактера на свим релевантним позицијама ниске између \(i\) и \(j\) (укључујући и њих). Сви карактери из тако направљеног скупа ће бити у скупу \(S\) (јер разматрамо само релевантне позиције), па је уместо испитивања да ли је тај скуп једнак скупу \(S\), довољно испитати само да ли има исти број елемената као \(S\) (а пошто ниска \(S\) по условима задатка нема поновљених карактера, број елемената скупа \(S\) једнак је дужини ниске \(S\)). Изградњу скупа релевантних карактера који се појављују унутар текуће ниске \(S\) можемо вршити инкрементално, тако што приликом сваког повећања \(j\), тј. приликом преласка на нову релевантну позицију \(j\) додамо карактер на тој позицији у тај скуп, што захтева само константно време (ако скуп карактера представимо низом или библиотечким скупом, јер је укупан број могућих карактера само 26).
Скуп карактера у језику C++ можемо представити преко низа 26 логичких вредности и додатног бројача који представља број карактера у скупу. Ипак, елегантнија имплементација се добија ако употреби библиотечка имплементација скупа (set или 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;
}Сложеност алгоритма који за сваку позицију \(i\) одређује најкраћу исправну подниску која почиње на позицији \(i\) уз све наведене оптимизације је \(O(n^2)\).
Захваљујући инкременталности, проверу да ли за дату дужину подниске \(k\) постоји нека подниска која садржи све дате карактере можемо урадити у линеарном времену \(O(n)\), у једном проласку кроз низ. Користићемо технику покретног прозора и приликом преласка са једне на наредну подниску, из скупа ћемо уклањати први карактер текуће подниске и додаваћемо последњи карактер нове подниске. Ово додатно можемо убрзати (додуше не асимптотски) ако је скуп карактера мали, тако што ћемо пролазити само кроз позиције оригиналне ниске на којима знамо да се јављају карактери из скупа.
Скуп карактера из \(S\) унутар текуће подниске ћемо представити помоћу пресликавања карактера у њихов број појављивања. Најједноставније је употребити библиотечку имплементацију мапе тј. речника, јер нам она пружа могућност ефикасног одређивања броја карактера из \(S\) унутар подниске (подниска је исправна тј. садржи све потребне карактере ако и само ако је број карактере из \(S\) које садржи једнак броју елемената скупа \(S\)).
Након тога, најмању дужину \(k\) можемо наћи техником бинарне претраге тако што нађемо најмању вредност \(k\) за коју важи неки услов. Битно је нагласити да проблем задовољава својство монотоности тј. да ако за неко \(k\) не постоји подниска дужине \(k\) која садржи све карактере скупа, онда таква подниска не постоји ни за једно мање \(k\) тј. да ако за неко \(k\) постоји таква подниска, онда она постоји и за свако веће \(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;
}Бинарном претрагом се претражује интервал \([1, n]\), где је \(n\) дужина ниске, па се провера да ли постоји подниска неке фиксне која садржи сва потребна слова врши највише \(\log{n}\) пута. Та провера се врши једним проласком кроз ниску. У сваком кораку врши се линеарна претрага ниске којом је одређен скуп карактера и врше се операције над мапом тј. речником у ком су кључеви карактери из скупа \(S\). Ако претпоставимо да се операције над мапом извршавају у логаритамској сложености, сложеност једне претраге је зато \(n\cdot m \cdot \log{m}\), где је \(m\) број карактера у \(S\). Пошто је \(m\) веома мали број, фактор \(m\log{m}\) можемо сматрати и константом и укупну сложеност грубо оценити са \(O(n\log{n})\). Да је \(m\) веће, сложеност би се могла поправљати тиме што би се провера припадности карактера скупу \(S\) вршила на ефикаснији начин (на пример, представљањем \(S\) помоћу бибилотечких колекција за представљање скупа или помоћу низа логичких вредности). Такође је могуће унапред одредити позиције карактера из \(S\) унутар ниске (што не утиче на асимптотску сложеност најгорег случаја, јер сви карактери у \(T\) могу припадати \(S\), али може доста смањити фактор \(n\) у свакој појединачној провери).
Рачунарски систем распоређује послове на два процесора. За сваки од процесора су познати послови који се на њему могу распоредити и за сваки од послова је познато очекивано време извршавања. У циљу добре балансираности система потребно је распоредити она два посла чије је време извршавања што сличније. Написати програм који то ради.
Са стандардног улаза се учитавају два низа који представљају очекивана времена извршавања послова на првом и на другом процесору. За сваки низ је задата прво дужина \(n\) (\(1 \leq m \leq 50000\)), а затим у другом реду \(n\) целих бројева (цели бројеви између \(1\) и \(2\cdot 10^9\) раздвојени по једним размаком).
На стандардни излаз исписати најмању вредност разлике два посла која ће бити распоређена.
5 4680 2120 7940 11530 17820 4 850 13420 5770 6300
1090
Најмања разлика се постиже када се на првом процесору покрене процес чије је време извршавања 4680, а на другом чије је време извршавања 5770.
Један могући приступ је да одредимо разлику (прецизније, апсолутну вредност разлике) у између сваког елемента првог и сваког елемента другог низа, па од тих разлика нађемо најмању.
Сложеност одговара броју парова и процењује се као \(O(m\cdot n)\), где је \(m\) број елемената првог, а \(n\) број елемената другог низа.
// 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;
}Ефикаснији приступ је да се низови најпре сортирају, а да се затим истовремено пролази кроз оба низа, рачунајући разлику текућих елемената и напредујући у оном низу у којем је вредност тренутно мања, као код класичног алгоритма обједињавања два сортирана низа. Успут се, наравно, по потреби ажурира најмања забележена разлика. Када се стигне до краја било којег низа, поступак је завршен и најмања забележена разлика је тада и укупно најмања.
Заиста, пошто су низови сортирани, када се упореде почетни елементи из оба низа, онај који је мањи од њих нема потребе упоређивати са осталим елементима низа коме он не припада, јер ће разлика моћи бити само већа (јер је тај низ сортиран). На тај начин вршимо одсецање, чиме добијамо на ефикасности. Тај елемент онда можемо избацити из даљег разматрања тако што ћемо у низу у ком се он налази прећи на следећи елемент. У специјалном случају када су почетни елементи оба низа једнаки, разлика је једнака нули, што је најмања могућа разлика, па нема потребе вршити даљу анализу.
Пример 3.A.7. На пример, нека су након сортирања вредности једнаке следећим.
1 14 28 33 45 8 21 22 41 56 68
Можемо закључити да је најмања могућа разлика једнака 4 (за бројеве 41 и 45).
Сложеношћу доминира сортирање, које се извршава у времену \(O(m\log{m} + n\log{n})\). Након сортирања, пролазак са два показивача се извршава у времену \(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;
}Напиши програм који одређује на колико начина можемо да одаберемо два елемента низа тако да им је разлика једнака датом броју \(r\).
Са стандардног улаза се уноси прво позитиван природан број \(r\), у наредном реду дужина низа \(n\) (\(1 \leq n \leq 50000\)), а након тога елементи низа.
На стандардни излаз испиши број парова елемената низа чија је разлика једнака \(r\).
2350 5 15745 18095 15745 16234 13395
4
Могуће је направити парове од првог и другог, од првог и петог, од другог и трећег и од трећег и петог елемента низа.
Наиван начин да се задатак реши је да се испитају сви уређени парови елемената низа и да се преброје они чија је разлика једнака траженој. Пошто уређених парова ученика има \(n^2\), сложеност оваквог алгоритма је \(O(n^2)\).
Задатак можемо решити техником два показивача. Низ мора бити сортиран, а оба показивача се крећу слева надесно. Једноставности ради, претпоставимо прво да у низу нема дупликата.
Пример 3.A.8. Прикажимо како би алгоритам радио на примеру одређивања броја елемената чија је разлика 8 у наредном низу.
1 3 7 8 11 14 16 30 38
Крећемо од пара 1 3. Пошто је разлика мања од тражене елемент 3 не може бити умањеник, па повећавамо умањеник на 7.
Анализирамо пар 1 7. Ситуација је опет иста, па опет повећавамо умањеник на 8. Наиме, померањем умањиоца са 1 на 3, разлика би се само смањила, па 7 заиста не може бити умањеник.
Анализирамо пар 1 8. И ту је ситуација иста, па опет повећавамо умањеник на 11 (поново закључујемо да се померањем умањиоца са 1 надесно, на 3 или 7 разлика смањује, па 8 заиста не може бити умањеник).
Анализирамо пар 1 11. Овај пут је разлика већа од тражене. Стога можемо закључити да 1 не може бити умањилац (даљим померањем умањеника надесно, разлика би се само повећала). Стога прелазимо на наредни умањилац, а то је 3. Кључна напомена је да су разлике свих умањеника испред 11 и броја 3 мање од тражене разлике 8 (јер су такве биле разике и када је умањилац био мањи)
Анализирамо пар 3 11. То је први пар који има дату разлику. Ако су елементи различити, тада се за све умањенике после 11 добија већа разлика у односу на умањилац 3, па можемо да померимо умањилац на 7. Слично, умањеник 11 не може да направи ни један даљи пар чија би разлика била једнака траженој, па можемо да померимо умањеник на 14.
Анализирамо пар 7 14. Разлика је мања од тражене, па повећавамо умањеник на 16.
Анализирамо пар 7 16 разлика је већа од тражене, па померамо умањилац на 8.
Анализирамо пар 8 16 чија је разлика једнака траженој. Након тога можемо повећати и умањилац на 11 и умањеник на 17.
Анализирамо пар 11 30 и пошто му је разлика већа од тражене, померамо умањилац на 14.
Анализирамо пар 14 30 и пошто му је разлика већа од тражене, померамо умањилац на 16.
Анализирамо пар 16 30 и пошто му је разлика већа од тражене, померамо умањилац на 30.
Анализирамо пар 30 30 коме је разлика мања од тражене, па померамо умањеник на 38.
Анализирамо пар 38 30 коме је разлика једнака траженој, па померамо и умањилац и умањеник. Пошто не постоји већи умањеник, алгоритам се завршава.
Опишимо формално претходни поступак и докажимо његову коректност. Одредимо колико парова дате разлике \(r\) постоји у интервалу \([i, n)\), ако знамо да важи инваријанта да је је \(a_{j-1} - a_i < r\). Вршимо иницијализацију \(i=0\) и \(j=1\), тако да одређујемо број парова и интервалу \([0, n)\), а инваријанта је задовољена јер је \(a_{j-1} - a_i = a_0 - a_0 = 0 < r\).
Ако је \(j = n\), тада у интервалу \([i, n)\) не постоји ни један пар дате разлике. Заиста, на основу инваријанте важи да је \(a_{n-1} - a_i < r\). Пошто је низ сортиран, и повећањем \(i\) и смањивањем \(j\) разлика се смањује. Зато парови бројева унутар интервала \([i, n)\) имају мању разлику од \(r\).
Ако је \(a_j - a_i < r\), тада знамо да у интервалу \([i, j]\) не постоји ни један пар бројева чија је разлика једнака \(r\) (јер је разлика елемената унутар интервала увек мања неко разлика крајњих елемената). Инваријанта је задовољена за пар \((i, j+1)\) па увећавамо \(j\) и настављамо поступак.
Ако је \(a_j - a_i > r\), тада ни један пар \(a_{j'} - a_i\) за \(i < j' < n\) нема разлику \(r\). На основу инваријанте знамо да је \(a_{j-1} - a_i\) мање од \(r\), па пошто је низ сортиран то важи и за све елементе \(i < j' < j\). Пошто је \(a_j - a_i > r\) и пошто је низ сортиран повећањем \(j\) се повећава разлика, па су разлике за \(j \leq j' < n\) веће од \(r\). Зато се у интервалу \([i, n)\) сви евентуални парови чија је разлика \(r\) налазе у интервалу \([i+1, n)\) и поступак настављамо тако што увећавамо \(i\) за 1. Још морамо доказати да тада инваријанта важи тј. да је \(a_{j-1} - a_{i+1} < r\), међутим то важи јер је низ сортиран и важи \(a_i < a_{i+1}\), а на основу инваријанте је важило да је \(a_{j-1} - a_i < r\).
На крају, ако је \(a_j - a_i = r\), тада смо пронашли један пар. Пошто смо претпоставили да у низу нема дупликата и да је низ сортиран, \(a_i\) не може бити члан ни једног другог пара са разликом \(r\) у интервалу \([i, n)\) - пошто је низ сортиран померањем умањеника налево разлика се смањује, а померањем надесно, она се повећава. Дакле, сви евентуални парови чија је разлика \(r\) налазе се у интервалу \([i+1, n)\). Поступак се може наставити увећавањем и индекса \(i\) и индекса \(j\) за 1. Заиста, инваријанта је задовољена јер је \(a_{j+1 - 1} - a_{i+1} = a_j - a_{i+1} < a_j - a_i = r\).
Сложеност овог приступа је \(O(n\log{n})\) захваљујући почетном сортирању, док је сложеност друге фазе, након сортирања линеарна тј. \(O(n)\). Заиста и умањеник и умањилац се крећу у истом смеру (вредност оба показивача се само увећава), па се може направити највише \(2n\) корака.
Пређимо сада на случај у ком се елементи у низу могу понављати.
Ако се елементи у низу понављају, онда у тренутку када нађемо први пар \((i, j)\) такав да је \(a_i - a_j = r\), одређујемо број појављивања \(n_i\) елемента \(a_i\) и број појављивања \(n_j\) елемента \(a_j\), број парова увећавамо за \(n_i \cdot n_j\) (јер свако појављивање вредности \(a_i\) можемо искомбиновати са сваким појављивањем вредности \(a_j\)) и након тога поступак настављамо од индекса \((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;
}Сложеношћу и даље доминира сортирање чија је сложеност \(O(n\log{n})\), док је сложеност друге фазе и даље линеарна тј. \(O(n)\).
Још један начин да се реши проблем понављања елемената је да се у првој фази низ вредности трансформише у низ парова који садрже вредности и њихов број појављивања.
// 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;
}Сортирање је сложености \(O(n\log{n})\). Пребројавање елемената се након тога извршава у сложености \(O(n)\), једним проласком кроз низ, након чега се са два показивача пролази кроз низ опет у сложености \(O(n)\). Укупна сложеност је, дакле, \(O(n\log{n})\). Имплементација користи и помоћни низ, али меморијска сложеност остаје \(O(n)\).
У датом низу позитивних природних бројева наћи све сегменте (њихов почетак и крај) чији је збир једнак датом позитивном броју (бројање позиција почиње од нуле).
У првој линији стандардног улаза налази се задати позитиван природни број \(z\) који представља дати збир \(0 < z < 10^6\), у другој број елемената низа, \(N\) (\(2 \leq N \leq 50000\)), а затим, у наредној линији \(N\) елемената низа (позитивни природни бројеви мањи од \(200\)).
У свакој линији стандардног излаза исписују се два броја (цели бројеви) одвојена празнином, који представљају индексе почетка и краја сегмента (бројано од нуле). Ако постоји више тражених сегмената њихове индексе исписати сортирано на основу левог краја.
125 10 60 40 25 50 50 100 25 35 30 35
0 2 2 4 5 6 6 9
Наивно решење грубом силом претпоставља да се израчунају збирових свих сегмената и да се провери да ли су једнаки датом броју. Чак и када збирове сегмената рачунамо инкрементално, добијамо неефикасно решење.
Постоји \(O(n^2)\) сегмената, а збир сваког сегмента на основу збира претходног сегмента добијамо у сложености \(O(1)\), па је укупна сложеност \(O(n^2)\).
Претрагу сегмената грубом силом можемо коришћењем одсецања начинити много ефикаснијом.
Пример 3.A.9. Посматрајмо пример проналажења првог сегмента у низу 1 2 3 5 15 1 2 5 који има збир 21.
Крећемо да испитујемо збирове сегмената који почињу на позицији \(0\). Све док је збир текућег сегмента строго мањи од 21, потребно је да проширујемо сегменте.
i a[i] zbir 0 1 1 1 2 3 2 3 6 3 5 11 4 15 26
У тренутку када је збир постао строго већи од тражене вредности 21, сигурни смо да ни један сегмент који почиње на позицији 0 не може имати збир 21. Наиме, пошто су сви даљи елементи стриктно позитивни, њиховим укључивањем би се добио само још већи збир. Због тога можемо да пређемо на сегменте који почињу на позицији 1. Важна (и не баш тривијална) опаска је то да сви сегменти који почињу на позицији 1 и завршавају се пре текуће позиције 4 имају збир строго мањи од 21 и стога их није потребно експлицитно испитивати. Наиме, сви сегменти који почињу на позицији 0, а завршавају се пре текуће позиције су имали збир мањи од 21, па се уклањањем елемента на позицији 0 добијају сегменти чији је збир још мањи. Дакле, први кандидат за збир 21, је сегмент који почиње на позицији 1 и завршава се на позицији 4. Његов збир лако добијамо одузимањем почетне вредности 1 са позиције 0 од збира текућег сегмента.
i a[i] zbir 1 2 2 2 3 5 3 5 10 4 15 25
Пошто и тај сегмент има збир већи од 21, такав збир ће имати и сви даљи сегменти који почињу на позицији 1, па можемо прећи на сегменте који почињу на позицији 2. Поново је први кандидат онај који се завршава на позицији 4 (јер сви који се раније завршавају сигурно имају збир мањи од 21).
i a[i] zbir 2 3 3 3 5 8 4 15 23
Поново је збир превелики, па прелазимо на сегменте који почињу на позицији 3. Први кандидат је сегмент који се завршава на позицији 4.
i a[i] zbir 3 5 5 4 15 20
Овај пут тај сегмент има збир мањи од траженог, па га је потребно проширити надесно. Додавањем наредног елемента добијамо сегмент чији је збир једнак траженом.
i a[i] zbir 3 5 5 4 15 20 5 1 21
Након овога смо сигурни да нема више сегмената траженог збира који почињу на позицији 3, па прелазимо на позицију 4 и поступак се по истом принципу наставља даље.
Дакле, одржавамо текући сегмент и његов збир. Док је тај збир мањи од траженог проширујемо сегмент надесно (док је то могуће), а када збир постане већи или једнак траженом скраћујемо сегмент са леве стране.
Докажимо и формално да је претходни поступак коректан. Обележимо са \(z_{ij} = \sum_{k=i}^j a_k\) збир елемената низа \(a\) чији индекси припадају сегменту \([i, j]\), а са \(z\) тражени збир елемената. Пошто су сви елементи низа \(a\) позитивни, збирови елемената сегмента задовољавају својство монотоности тј. важи да из \(i < i' \leq j\) следи \(z_{ij} > z_{i'j}\) и да из \(i \leq j < j' < n\) следи \(z_{ij} < z_{ij'}\).
Претпоставимо да за неки интервал \([i, j]\) знамо да за свако \(j'\) такво да је \(i \leq j' < j\) важи да је \(z_{ij'} < z\). Постоје следећи случајеви за однос \(z_{ij}\) и \(z\).
Прво, ако је \(z_{ij} < z\), тада ни за један интервал који почиње на позицији \(i\), а завршава се најкасније на позицији \(j\) не може важити да му је збир елемената \(z\), и проверу је потребно наставити од интервала \([i, j+1]\), увећавајући \(j\) за 1. Ако такав интервал не постоји (ако је \(j + 1 = n\)), онда се претрага може завршити (јер је и за свако \(i'\) такво да је \(i < i' \leq j = n-1\) важи \(z_{i'j} < z_{ij} < z\), а зато и за свако \(j'\) такво да је \(i' \leq j' < j = n-1\) важи да је \(z_{i'j'} < z_{i'j} < z\), тако да за сваки интервал \([i', j']\) такав да је \(i \leq i' \leq j' < n\) важи да је \(z_{i'j'} < z\)).
Друго, претпоставимо да је \(z_{ij} \geq z\). Ако је \(z_{ij} = z\), тада је пронађен један задовољавајући интервал и потребно је обрадити његове границе \(i\) и \(j\). То је једини сегмент који почиње на позицији \(i\) са збиром \(z\). Ако је \(z_{ij} > z\), онда таквих сегмената нема. Наиме, пошто су сви елементи низа \(a\) позитивни, за свако \(j''\) такво да је \(j < j'' < n\) важи да је \(z \leq z_{ij} < z_{ij''}\). Дакле, претрагу можемо наставити увећавајући вредност \(i\). За све вредности \(j'\) такве да је \(i+1 \leq j' < j\) важи да је \(z_{(i+1)j'} < z\). Наиме, пошто је \(a_i > 0\) важи да је \(z_{(i+1)j'} < z_{ij'} < z\). Дакле, на сегмент \([i+1, j]\) може се применити анализа случајева истог облика као на интервал \([i, j]\).
Још један начин да образложимо коректност овог поступка је да посматрамо све збирове сегмента.
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
Пошто су елементи низа строго позитивни, свака врста ове матрице је строго растућа, а свака колона је строго опадајућа. Када је текући збир мањи од траженог и сви елементи његове колоне испод њега су мањи од траженог и они не морају бити разматрани. Могуће је “прецртати” све елементе у колони испод текућег и прећи се на разматрање наредног збира у текућој врсти (ако он постоји). Када је текући збир већи од траженог, већи су и сви елементи у његовој врсти десно од њега. Могуће је њих прецртати и прећи на разматрање наредног збира у текућој колони (ако он постоји). Елементи у тој наредној врсти лево од текуће колоне су већ раније прецртани и није потребно враћати се на њих.
Приликом имплементације одржаваћемо интервал \([i, j]\) и његов збир ћемо израчунавати инкрементално - приликом повећања броја \(j\) збир ћемо увећавати за \(a_j\), а приликом повећања броја \(i\) збир ћемо умањивати за \(a_i\).
Један начин да се на основу претходне анализе направи имплементација је да се у сваком кораку петље одржавају две променљиве \(i\) и \(j\) и променљива \(zbir\). Обезбедићемо да при сваком уласку у тело петље важи да променљива \(zbir\) чува текућу вредност \(z_{ij}\) и да је за свако \(j' < j\) испуњено да је \(z_{ij'} < z\). Ако се \(i\) и \(j\) иницијализују на нулу, тада се \(zbir\) треба иницијализовати на \(a_0\), чиме се задовољава претходни услов.
У телу петље провервамо да ли је \(zbir\) мањи од траженог и ако јесте, увећавамо вредност \(j\). Ако \(j\) достигне вредност \(n\), тада можемо прекинути петљу и завршити претрагу. Ако је увећано \(j\) мање од \(n\), онда збир увећавамо за \(a_j\) и прелазимо на наредни корак петље (услов који смо наметнули да важи при уласку у петљу ће бити овим бити задовољен).
Ако вредност променљиве \(zbir\) није мања од тражене вредности \(z\) проверавамо да ли јој је једнака. Ако јесте, пријављујемо пронађени интервал \([i, j]\). Затим прелазимо на обраду наредног интервала тако што збир умањујемо за вредност \(a_i\) и \(i\) увећавамо за 1 (услов који смо наметнули да важи при уласку у петљу ће овим бити опет задовољен).
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;
}Још једна могућа имплементација садржи две угнежђене петље. У првој десни крај сегмента померамо надесно све док не стигнемо до краја или док је збир текућег сегмента мањи од траженог. У другој леви крај сегмента померамо надесно све док је збир већи или једнак од траженог (при том проверавајући да ли је збир једнак траженом и ако јесте, пријављујући пронађени интервал).
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;
}Иако садржи угнежђене петље, ово решење је линеарне сложености у односу на дужину низа тј. сложености је \(O(n)\). Наиме, променљиве \(i\) и \(j\) се у сваком кораку увећавају за један и никада се не умањују, тако да је укупан број корака ограничен вредношћу \(2n\).
Овај задатак је поновљен у циљу илустровања различитих техника решавања.
У првој линији стандардног улаза налази се текст (једноставности ради претпоставимо да је састављен само од малих слова енглеског алфабета) чија је дужина највише \(10^5\) карактера. У другој линији се налази скуп слова (опет, претпоставимо малих слова енглеског алфабета) које је дизајнер променио (слова су написана једно до другог, без размака и без понављања).
На стандардни излаз исписати један цео број који представља дужину најкраћег дела текста који садржи све карактере датог скупа. Ако такав део текста не постоjи, исписати nema.
dobardansvimakakoste arnk
10
ababababab abc
nema
Пореска инспекција жели да провери преваре тако што ће проверавати банковне рачуне на којима се налази тачно неки специфичан износ (на пример, тачно 100 хиљада динара). У том циљу потребно је имплементирати банковни систем. Систем има највише \(k\) различитих корисника. Сваки корисник на почетку има рачун са почетним стањем 0. Потребно је подржати две врсте операција:
ime x додаје \(x\) динара на рачун особе са корисничким именом ime (\(x\) може бити и негативно)provera x одређује колико постоји корисника чији рачун садржи тачно \(x\) динараНаписати програм који пордржава извршавање \(n\) оваквих операција.
Са стандардног улаза се уносе бројеви \(n\) и \(k\). Након тога се у \(n\) редова уноси по једна операција.
За сваки упит (операцију првог типа) исписати одговор, сваки у засебном реду.
6 4 marko 2300 milan 5200 dragana 4000 provera 0 milan -1200 provera 4000
1 2
Задатак се једноставно и лако може решити употребом две мапе тј. речника. Једна се користи да преслика име корисника у износ на његовом рачуну, а друга да преслика износ на рачуну у број рачуна који садрже тај износ.
// 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;
}Напиши програм који за дати низ целих бројева одређује број непразних сегмената узастопних елемената низа чији је збир једнак датом броју.
Са стандардног улаза се у првој линији уноси тражена вредност збира \(z\) (цео број \(-10000\) и \(10000\)), затим, у наредној линији димензија низа \(n\) (\(3\leq n \leq 50000\)) и затим у наредној линији елементи низа (цели бројеви између -100 и 100, раздвојени размаком).
На стандардни излаз испиши број сегмената чији је збир једнак \(z\).
11 10 1 2 3 5 1 -1 1 5 3 2
7
Објашњење: следећи сегменти имају збир 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
Директно решење грубом силом подразумевало би да се провере сви сегменти узастопних елемената, да се за сваки израчуна збир и да се провери да ли је тај збир једнак траженом. Сви сегменти се могу набројати угнежђеним петљама, где спољна петља пролази кроз леве крајеве сегмента (\(i\) узима вредности од \(0\) па до \(n-1\)), а унутрашња петља пролази кроз десне крајеве сегмената (од вредности \(i\) па до \(n-1\)).
Сложеност овог приступа је кубна у односу на димензију \(n\) тј. \(O(n^3)\).
Алгоритам грубе силе који посебно рачуна збир сваког сегмента се може унапредити ако се збирови рачунају инкрементално тј. ако се искористи чињеница да се збир сваког сегмента који се добија проширивањем претходног сегмента једним елементом може лако израчунати на основу збира претходног сегмента, тако што се збир претходног сегмента увећа за текући елемент низа.
Дакле, опет можемо набрајати све сегменте угнежђеним петљама, на почетку тела спољашње петље збир иницијализујемо на нулу, у унутрашњој петљи збир увећавамо за елемент \(a_j\) и, ако је он једнак траженом, исписујемо индексе интервала \([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;
}Овим је избегнута линеарна сложеност за израчунавање збира тренутног интервала тј. да се збир сваког наредног интервала добија у константном времену, тако да је сложеност целог алгоритма редукована на квадратну тј. \(O(n^2)\).
Задатак се, може решити и доста ефикасније од овога.
Један елегантан и често примењиван начин да се добију збирови свих сегмената низа је да се збир сегмента представи као разлика збира два префикса низа. У помоћни низ \(b\) (или у сам низ \(a\), ако је меморија критичан ресурс), инкрементално, у линеарној сложености \(O(n)\), на сваку позицију \(k\) од \(0\) до \(n\) можемо сместити збир првих \(k\) елемената низа тј. збир елемената сегмента \([0, k)\).
Након тога можемо проверити све парове префикса и видети да ли је њихова разлика једнака траженом збиру сегмената. Ако проверавамо сваки сегмент \([i, j]\) за \(0 \leq i < j < n\) и за сваки збир одређујемо на основу разлике збирова префикса (што можемо урадити у константном времену) добијамо алгоритам квадратне сложености \(O(n^2)\).
Ово није ефикасније од инкременталног решења грубом силом, али се уз коришћење погодне структуре података може унапредити.
Изражавање збира сегмента у облику разлике збира два префикса нам даје могућност да стигнемо до ефикаснијег решења. Проблем можемо формулисати и овако. За сваки збир \(b_{j+1}\) префикса \([0, j+1)\) потребно је да пронађемо да ли постоји збир \(b_{i}\) префикса \([0, i)\) за неко \(i < j\) таква да је \(b_{j+1} - b_{i} = z\), где је \(z\) тражени збир, тј. да се провери да ли се међу збировима претходних префикса налази вредност \(b_{i} = b_{j+1} - z\). Ако се та претрага врши линеарно, долазимо до имплементације веома сличне претходној, која испитује сваки пар елемената \(i < j\). Пошто међу елементима низа може бити и негативних, збирови префикса нису сортирани и не можемо применити ни бинарну претрагу. Остаје нам, међутим, могућност да у некој структури података која омогућава ефикасно претраживање чувамо све збирове префикса за индексе \(i < j\). Ако алгоритам организујемо тако да \(j\) увећавамо од \(0\) до \(n-1\), тада се на крају сваког корака у ту структуру може додати и збир текућег сегмента (\(b_{j+1}\)). Структура треба да реализује претрагу по кључу, тако да је најбоље употребити асоцијативни низ (мапу тј. речник).
Пошто се у задатку тражи само одређивање броја сегмената са датим збиром, кључеви могу бити збирови префикса, а вредност придружена сваком кључу може бити број префикса са тим збиром. Да се тражила само провера да ли постоји сегмент са датим збиром, могли смо уместо асоцијативног низа (мапе, речника) чувати само скуп раније виђених вредности збирова префикса, а да су се експлицитно тражили сви префикси, онда бисмо сваки кључ пресликавали у низ вредности \(i\) таквих да је \(b_i\) једнако том кључу.
Ако рачунамо да ће претрага бити реализована у \(O(\log{n})\) (што је најчешће случај ако се користе структуре података засноване на бинарним стаблима), тада ће укупна сложеност ове имплементације бити \(O(n\log{n})\). Напоменимо да смо добитак на ефикасности платили додатном меморијом коју смо ангажовали, међутим, у овом сценарију није потребно памтити учитан низ, тако да меморијска сложеност неће бити значајно повећана.
// 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;
}Ђаци седе у кругу обележени бројевима од \(0\) до \(n-1\) и играју се разбрајалице тако да у сваком бројању један ђак испадне. Бројање креће од ђака 0 и сваки \(m\)-ти ђак испада. Напиши програм који одређује који ђак ће остатати последњи.
У првој линији стандардног улаза налази се почетни број ђака \(n\) (\(1 \leq n \leq 10^5\)), а у другом дужина бројалице \(m\) (\(2 \leq m \leq n\)).
На стандардни излаз исписати број преосталог ђака.
8 3
6
Ђаци који седе у кругу на почетку и након сваког испадања су:
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
Структура података која допушта ефикасно избацивање елемената из средине је листа (нпр. двоструко повезана). Кружно кретање по листи можемо остварити тако што након сваког померања итератора проверимо да ли смо стигли до краја листе и ако јесмо, итератор ручно поново поставимо на почетак листе.
// 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;
}Кружну листу можемо једноставно реализовати коришћењем реда. У сваком кораку бројања једног ђака са почетка реда ћемо пребацити на крај реда. Након пребацивања \(m-1\) ученика, оног који је на почетку реда трајно избацујемо.
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;
}Дата су два низа која садрже природне бројеве. Напиши програм који одређује \(k\)-ти највећи збир који се може добити када се сабере један елемент првог и један елемент другог низа. Водити рачуна о меморијској ефикасности програма.
Са стандардног улаза се учитава број \(m\) (\(1 \leq m \leq 5000\)), а затим из наредног реда \(m\) елемената првог низа раздвојених размаком. Из наредног реда се учитава број \(n\) (\(1 \leq n \leq 5000\)), а затим из наредног реда \(n\) елемената другог низа раздвојених размаком. Елементи оба низа су природни бројеви између \(0\) и \(10^6\). На крају се учитава број \(k\) (\(0 \leq k < mn\)).
На стандардни излаз исписати збир који се налази на позицији \(k\) у низу који би се добио када би се низ свих збирова парова једног елемента првог и једног елемента другог низа сортирао нерастуће (позиције се броје од нуле).
3 1 5 3 3 6 4 2 4
7
Збирови који се могу добити, поређани од највећег ка најмањег су \(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\), па се на позицији \(4\) налази збир \(7\).
5 5 3 8 6 1 6 1 10 9 7 12 2 9
15
Решење грубом силом подразумева да се формира низ свих збирова, да се сортира нерастуће и да се прочита елемент са позиције \(k\).
Парова елемената има \(m\cdot n\), па је меморијска сложеност квадратна и износи \(O(mn)\). Временском сложеношћу доминира сортирање и она износи \(O(mn\log{(mn)})\).
Уместо сортирања, могуће је применити и мало ефикаснији алгоритам QuickSelect, који проналази елемент на позицији \(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;#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;
}Проблем се може свести на проблем обједињавања неколико сортираних низова, који се не морају истовремено чувати у меморији. Наиме, ако сортирамо оба низа опадајуће, можемо разматрати следеће низове:
\[ \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} \]
Сви они су сортирани нерастуће и могу се објединити коришћењем реда са приоритетом. У почетку у ред убацујемо први елемент сваке листе тј. све збирове облика \(a_i + b_0\). У сваком кораку избацујемо највећи збир из реда и додајемо у ред наредни елемент листе којој он припада. Да бисмо након вађења елемента из реда могли додати наредни елемент листе којој он припада, поред вредности збира \(a_i + a_j\) (на основу којих је ред уређен) у реду морамо чувати и индексе \(i\) и \(j\). Заправо довољно је чувати само индекс \(j\), јер се на основу збира \(z = a_i + b_j\), збир \(a_i + b_{j+1}\) може добити као \(z-b_j+b_{j+1}\).
У реду се у сваком тренутку налази највише \(m\) елемената. Пошто се чувају и оригинални низови (да би се сортирали), меморијска сложеност је \(O(m+n)\). Ажурирање реда врши се \(k\) пута. Пошто је сложеност иницијалних сортирања низова \(O(m\log{m} + n\log{n})\), сложеност једног ажурирања реда је \(O(\log{m})\), а важи \(k < mn\), временска сложеност је \(O(m\log{m} + n\log{n} + mn\log{m})\). Сложеношћу јасно доминира фаза обједињавања, па се временска сложеност може проценити и само са \(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;
}У заводу за статистику желе да што непристрасније процене која је просечна плата. Закључили су да израчунавање аритметичке средине може дати мало искривљену слику јер неколико људи са веома високим платама могу значајно повећати просек. Зато су одлучили да уместо аритметичке средине израчунају медијану, која се добија тако што се све плате поређају у неопадајући низ и онда се узме средишњи елемент тог низа. Ако у низу има паран број елемената, онда се за медијану узима аритметичка средина два средишња елемента. На пример, медијана низа бројева 1, 2, 4, 7, 9 је 4 (јер је он средишњи), а низа бројева 1, 2, 4, 5, 7, 9 је 4.5 (јер је то аритметичка средина бројева 4 и 5 који су средишњи елементи). Подаци о платама пристижу у завод, а софтвер мора да може да у сваком тренутку да податак о медијани до тада унетих плата.
Са стандардног улаза се уносе линије, све до краја стандардног улаза. Линија или садржи слово d и затим износ плате раздвојен размаком (цео број), што значи да се уноси податак о новој плати или садржи слово m што значи да је потребно на стандардни излаз исписати податак о медијани до тада унетих плата. Прва линија сигурно садржи d.
На стандардном излазу су исписане тражене медијане, свака у посебном реду, заокружене на једну децималу.
d 5 d 7 d 6 m d 8 m
6.0 6.5
Директан начин да се задатак реши је тај да се све учитане плате смештају у низ (или још боље вектор тј. листу, пошто не знамо унапред колико ће плата бити учитано) и да се сваки пут када се затражи израчунавање медијане позове функција која рачуна медијану низа. Та функција може бити заснована на сортирању и читању средишњег елемента (тј. средишњих елемената када је низ парне дужине), а постоје и мало ефикаснија решења од тога.
Сложеност таквог решења зависи од сложености сортирања који је \(O(n\log(n))\) када се користи бибилотечка функција сортирања, тако да је укупна сложеност \(O(n^2\cdot \log(n))\), при чему претпостављамо да ће се медијана рачунати \(O(n)\) пута за низ који има \(O(n)\) елемената (тј. да су и број додавања и број упита за медијаном одређени бројем \(n\)).
Медијана се може наћи и без сортирања целог низа, коришћењем идеје партиционисања тј. алгоритма брзе селекције (QuickSelect).
У језику C++ ово је најлакше остварити помоћу функције nth_element. Рецимо и да је у случају парне димензије функцију nth_element потребно позвати два пута, да би се одредила два средишња елемента.
Сложеност проналажења медијане алгоритмом брзе селекције је у најгорем случају \(O(n)\), што доводи до укупног решења сложености \(O(n^2)\).
Ефикасно решење се може добити ако у сваком тренутку у једној (рећи ћемо левој) колекцији чувамо све елементе који су мањи од средишњег, а у другој (рећи ћемо десној) све оне који су већи или једнаки средишњем (ако постоји паран број елемената, те две колекције треба да садрже исти број елемената, а ако постоји непаран број елемената, десна колекција може да садржи један елемент више). Ако има непаран број елемената, тада је медијана једнака најмањем елементу десне колекције, а у супротном је једнака аритметичкој средини између највећег елемента леве и најмањег елемента десне колекције. Сваки нови елемент се пореди са најмањим елементом десне колекције и ако је мањи или једнак њему убацује се у леву колекцију, а ако је већи од њега, убацује се у десну колекцију. Тада се проверава да ли се средина променила. Ако се десило да лева колекција има више елемената од десне (што не допуштамо), највећи елемент леве колекције треба да пребацимо у десну. Ако се десило да у десној колекцији има два елемента више него у левој, тада најмањи елемент десне колекције пребацујемо у леву. Дакле, лева колекција треба да буде таква да лако можемо да пронађемо и избацимо њен највећи елемент, а десна да буде таква да лако можемо да пронађемо и избацимо њен најмањи елемент, при чему обе колекције морају да подрже ефикасно убацивање произвољних елемената. Јасно је да те колекције треба да буду хипови (у језику C++ можемо употребити priority_queue) у којима се најмања тј. највећа вредност може очитати у константном времену, уклонити у логаритамском, исто колико је потребно и да се уметне нови елемент.
Пример 3.A.10. Прикажимо рад овог алгоритма на једном примеру.
На почетку су оба хипа празна.
Претпоставимо да се на улазу појављује елемент 5. Њега убацујемо у десни хип (јер он може да садржи један елемент више). Стање је сада следеће:
\(\mathit{levi}: []\quad \mathit{desni}: [5]\)
Медијана је елемент на врху десног хипа тј. 5.
Претпоставимо са се на улазу сада појављује елемент 6. Пошто је он већи од елемента 5 који је на врху десног хипа, елемент 5 пребацујемо у леви, а елемент 6 убацујемо у десни хип. Стање је сада следеће:
\(\mathit{levi}: [5]\quad \mathit{desni}: [6]\)
Медијана је просек елемената на врху оба хипа тј. 5,5.
Претпоставимо да се сада на улазу појављује елемент 3. Пошто је он мањи од елемента 5 на врху левог хипа елемент 5 пребацујемо у десни хип, а елемент 3 убацујемо у леви. Стање је сада следеће:
\(\mathit{levi}: [3]\quad \mathit{desni}: [5, 6]\)
Медијана је елемент на врху десног хипа тј. 5.
Претпоставимо да се сада на улазу појављује елемент 1. Пошто је он мањи од елемента 5 на врху десног хипа, додајемо га у левих хип.
Стање је сада следеће:
\(\mathit{levi}: [1, 3]\quad \mathit{desni}: [5, 6]\)
Медијана је просек елемената на врху оба хипа тј. 4.
Претпоставимо да се сада на улазу појављује елемент 8. Пошто је он већи од елемента 5 на врху десног хипа, додајемо га у десни хип.
Стање је сада следеће:
\(\mathit{levi}: [1, 3]\quad \mathit{desni}: [5, 6, 8]\)
Медијана је елеменат на врху десног хипа, тј. 5.
Идеја да се уместо у једне подаци чувају у две структуре података често може довести до ефикасног решења.
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;
}