POBOLJŠANJE SLOŽENOSTI ALGORITMA- PRIMERI

Ova stranica nudi primere zadataka za poboljšanje složenosti algoritama. Uključuje različite probleme poput optimizacije vaterpolskih treninga, brojenja specifičnih podstringova, pronalaženja nedostajućih brojeva i izračunavanja zbirnih vrednosti u aritmetičkim trouglovima. Svaki primer pruža izazov u analizi složenosti i efikasnosti rešenja.

1. N-ti dan treninga

Na planeti super-heroja, vaterpolisti učestvuju na pripremama za takmičenje u trajanju od n dana. Prvog dana priprema vaterpolista prepliva a metara, a svakog sledećeg dana za d metara više nego prethodnog dana. Napisati program kojim se za svakog vaterpolistu u klubu određuje koliko metara prepliva poslednjeg dana priprema.

Ulaz: Prvi red standardnog ulaza sadrži broj dana priprema n (n ≤ 105). Svaki naredni red standardnog
ulaza predstavlja podatke za jednog vaterpolistu (njih najviše 105). Unose se tri dva broja razdvojena raz-
makom: broj metara koji vaterpolista prepliva prvog dana priprema a (a ≤ 3000), i broj metara koje svaki
dan više pliva u odnosu na prethodnii dan d (d ≤ 1000).Izlaz:

Na standardnom izlazu za svakog vaterpolistu prikazati koliko metara prepliva poslednjeg dana priprema.

Primer:

Ulaz:
10
500 100
400 20

Izlaz:

1400
580
Pročitaj objašnjenje zadatka na strani: Zamena iteracija formulom

---

2. BROJ PODSTRINGOVA KOJI POČINJU I ZAVRŠAVAJU SA 1

Dat je binarni string (niska karaktera koja se sastoji od karaktera 0 i 1). Napisati program kojim se određuje broj segmenata (podstring uzastopnih elemenata), dužine najmanje 2, koji počinju i završavaju sa 1.

Ulaz:

Prva i jedina linija standardnog ulaza sadrži binarni string (sastavljen od 0 i 1).

Izlaz:

Na standardnom izlazu prikazati u jednoj liniji traženi broj segmenata.

Primer:

Ulaz:
010001001

Izlaz:

3
​Pročitaj objašnjenje zadatka na strani: Zamena iteracija formulom

---

3. НЕДОСТАЈУЋИ БРОЈ

U nizu brojeva od 0 do n tačno jedan broj je izostavljen. Napiši program koji, bez pamćenja elemenata niza, učitava brojeve sa ulaza i efikasno određuje koji broj nedostaje.

Ulaz:

Sa standardnog ulaza se učitava broj n (1 ≤ n ≤ 10⁹), a zatim i opisani niz brojeva (brojevi su navedeni u jednom redu, razdvojeni sa po jednim razmakom).

Izlaz:

Na standardni izlaz ispisati element koji nedostaje.

Primer:

Ulaz:
5
0 4 2 5 1

Izlaz:

3

---

4. ARITMETIČKI TROUGAO

Koliki je zbir brojeva u datom redu, sledećeg trougla:

Ulaz:

Redni broj k (1 ≤ k ≤ 5 · 10⁵), reda trougla čiji zbir treba izračunati (brojanje redova počinje od 1)

Izlaz:

Zbir vrednosti u zadatom redu trougla.

Primer:

Ulaz:
3

Izlaz:

35