SVET PROGRAMIRANJA

PRIPREMA ZA DRŽAVNO TAKMIČENJE IZ INFORMATIKE

Ova stranica je vodič za pripremanje rešavanja zadatka koja se pojavljuju na državnim takmičenjima iz informatike, za osnovne škole. Takođe su pokazani jednostavni primeri koji su sastavni deo većih zadataka.
Ako se prethodno niste pripremili za okržno takmičenje pogledajte stranu Priprema za okružna takmičenja

Državno takmičenje iz 2021

Zadatke sa rešenjima i test primerima možete preuzeti sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

1. Prašuma

Napomena: Zadatak je za 5. i 6. razred i preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

U prašumi je nađena čudesna tablica sa 3 reda i 3 kolone ispunjena ciframa. Pored tablice je nađen tekst zagonetke. Zagonetka kaže: Formirajte prvi trocifreni broj na osnovu cifara sa glavne dijagonale tablice, počev od vrha i idući ka dnu tablice. Zatim formirajte još jedan trocifreni broj koji se sastoji od cifara u sporednoj dijagonali, takođe počevši od vrha do dna. Rešenje zagonetke je proizvod ova dva trocifrena broja. Napišite program koji učitava cifre napisane na tablici i ispisuje proizvod dva trocifrena broja koji se formiraju na opisani način.
Pojašnjenje: Glavnu dijagonalu tablice obrazuju redom: prva cifra prvog reda, srednja cifra drugog reda i poslednja cifra trećeg reda. Sporednu dijagonalu obrazuju redom: poslednja cifra prvog reda, srednja cifra drugog reda i prva
cifra trećeg reda.
Ulaz
U svakom od tri reda standardnog ulaza date su tri cifre, zapisane bez razmaka.
Izlaz
Na standardnom izlazu, program mora da ispiše jedan ceo broj - proizvod dva
trocifrena broja koji se dobija na gore opisan način.
Primer 1
Ulaz
123
456
789
Izlaz
56763
Pojašnjenje primera: Broj formiran od cifri na glavnoj dijagonali je 159. Broj formiran od cifri na sporednoj dijagonali je 357. Proizvod ta dva broja je 56763


Analiza prvog zadatka

Da bi ste uradili ovaj zadatak jedno od mogućih načina rešavanja je upotrebom matrica i korišćenje ugnježdenih petlji. S obzirom da se ove oblasti pojavljuju na državnom takmičenju preporuka je poznavanje ovih oblasti.
Više o matricama pogledajte na strani: Dvodimenzionalni nizovi - matrice
Više o ugnježdenim petljama pročitajte na strani: Ugnježdene petlje u C/C++
Pre rešavanja zadatka sa državnog takmičenja, preporuka je da se prvo urade sledeći primeri: primer 1 i primer 2

Primer 1:

Učitati 9 brojeva u matricu 3*3. Ispisati vrednosti u glavnoj i sporednoj dijagonali. 
Primer
Ulaz:
1 2 3
4 5 6
7 8 9
Izlaz 
Glavna dijagonala: 1 5 9
Sporedna dijagonala 3 5 7

Rešiti zadatak po sledećem algoritmu:

  • Koristiti dvodimenzioni niz(matricu) za smeštanje podataka u 3 reda i 3 kolone
  • Učitati matricu. Koristiti ugnježdene petlje for. Spoljašnja treba da menja redove, a unutrašnja kolone
  • Koristiti ugnježdene petlje for sa istim kontrolnim izrazima za ispis elemenata matrice
  • Koristiti if naredbu za proveru uslova za glavnu dijagonalu. Uočiti da su za te elemente red i kolona jednaki
  • Koristiti if naredbu za proveru uslova za sporednu dijagonalu. Uočiti da su za te elemente red i kolona jednaki, ako bi kolone menjali od poslednje ka prvoj

#include < iostream >
using namespace std;
int main()
{
int A[3][3];
int X=0,Y=0;
//Menja redove
for(int i=0; i<3; i++)
{
//menja kolone
for(int j=0; j<3; j++)
{
cin >> A[i][j];
}
}
int d=1000,d1=1000;
for(int i=0; i < 3; i++)
{
//menja kolone
for(int j=0; j < 3; j++)
{
int c=A[i][j];// cifra izvađena iz matrice u i-tom redu i j-toj koloni. U ciklusima 1,5,9
if(i==j)
{
d=d/10;////100,10,1 u ciklusima redom
X=X+c*d;//vrednosti 100,150,159 u ciklusima redom
}
if(2-i==j)
{
d1=d1/10;//100,10,1 u ciklusima redom
Y=Y+c*d1;//vrednosti 300,350,357 u ciklusima redom
}
}
cout << endl;
}
cout << (X*Y) << endl; // rezultat
return 0;
}

Sastaviti broj od poznatih cifara

Primer 2:

Uneti 4 cela broja koji predstavljaju cifre četvorocifrenog broja. Sastaviti novi broj čije su cifre u obrnutom redosledu.
Primer:
Ulaz:
4
5
6
7
​Izlaz: 7654

Poslednja uneta cifra je cifra 1000 pa nju treba pomnožiti sa 1000, pretposlednju cifru sa 100, treću od nazad sa 10 itd. Dobijen broj je zbir pomenutih proizvoda

#include < iostream >
using namespace std;
int main()
{
int a,b,c,d,broj;
cin >> a >> b >> c >> d;
broj=1000*d + 100*c + 10*b + a;
cout << broj< return 0;
}

2. Zbir kvadrata neparnih cifara

Napomena: Zadatak je je za 5. i 6. razred i  preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Lenka želi da izračuna zbirove kvadrata neparnih cifara nekoliko brojeva. Pomozi Lenki i napiši program koji sa standardnog ulaza učitava jedan prirodan broj manji od milijardu i na standardni izlaz ispisuje zbir kvadrata njegovih neparnih cifara (ako takvih cifara nema, računamo da je zbir nula). Kvadrat neke cifre je jednak proizvodu te cifre sa samom sobom. Na primer, kvadrat cifre 3 je
3, jer 3×3=9
Primer 1
Ulaz
1234560
Izlaz
35
Primer 2
Ulaz
11
Izlaz
2
Primer 3
Ulaz
888
Izlaz
0

Analiza drugog zadatka

Da bi se izdvojile cifre iz broja potrebno je koristiti operatore % i /, tj. deljenje sa nekim od stepena sa osnovom 10 ili ostatka deljenja sa ovim brojevima. Sličan primer je obrađen u zadatku 4 sa web strane Podaci i tipovi podataka-dodatni primeri
Takođe je potrebno znanje iz  petlji i to kako sabrati brojeve koristeći petlju. Sličan primer je objašnjen na web strani Priprema za kontrolni zadatak iz petlji (Zadatak 3)

Rešiti zadatak po sledećem algoritmu:

  • Učitati ceo broj
  • Koristeći petlju(while) vršiti izdvajanje poslednje cifre sa desne strane iz ostatka broja
  • Ostatak broja je taj broj na pre početka petlje, a unutar petlje se transformiše tako što se deljenjem sa 10 uklanja jedna cifra
  • Postupak se ponavlja dok je ostatak broja veći od nule
  • Dodavati kvadrat izdvojene cifre u trenutni zbir, povećavajući ga kroz petlju postupno
  • Ne zaboraviti da se zbir inicijalizuje na vrednost nula pre početka petlje

#include < iostream >
using namespace std;
int main()
{
int broj,x;
int zb=0;//zbir, koji je u početku jedna nuli
cin >> broj;
x=broj;
while( x > 0 ){
int c=x % 10;//cifra na desnom kraju
x=x/10;//uklanja cifru na desnom kraju
if((c % 2) != 0){//da li je neparna
zb += c*c;//formira zbir kvadrata
}
}
cout << zb << endl;
return 0;
}

3. Čarobni niz

Napomena: Zadatak je za 5. i 6. razred i preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Laza je odlučio da napravi čarobni niz brojeva na sledeći način: Laza je počeo da pravi niz od nekog zadatog broja i svaki naredni član niza se dobija tako što se prethodnom broju doda broj svih njegovih delilaca. Na primer, ako je neki član niza jednak 6, onda je sledeći član niza jednak 6 + 4 tj. 10, jer postoje tačno 4 delioca broja 6 (to su redom brojevi 1, 2, 3, 6).
Napišite program koji učitava sa standardnog ulaza u prvom redu prvi član niza (0<a1≤10000) i u drugom redu prirodan broj N (0<N≤100), a štampa na standardni izlaz N-ti član Lazinog niza.
Primer 1
Ulaz
2
4
Izlaz
9
Pojašnjenje: a1=2, a2=4, a3=7, a4=9
Primer 2
Ulaz
3882
93
Izlaz
4878

Analiza trećeg zadatka

Zadak se može odraditi tako što se u posebnu metodu izdvoji postupak određivanje broja delilaca za unet broj. 
Za rešavanje zadatka potrebno je poznavanje:
  1. Petlje u programskom jeziku C/C++
  2. metode(opciono)

Zadak se može odraditi tako što se u posebnu metodu izdvoji postupak određivanje broja delilaca za unet broj. U glavnoj metodi bi se onda posle unošenja prvog člana niza formirala petlja od k ponavljanja, gde je k broj elemenata niza i taj broj se takođe unosi. U svakom ciklusu petlje bi se određivao broj delioca tekućeg člana niza pozivanjem dodatne metode (može se uraditi i bez upotrebe metoda pisanjem celog postupka određivanja broja delilaca unutar petlje). Dobijeni broj delilaca bi se iskoristio za izračunavanje sledećeg elementa u nizu.

#include < iostream >
using namespace std;

/*Metoda koja za unet broj n, određuje kolko ima delilaca*/
int brojDelioca(int n)
{
int br=0;//broj delilaca
for(int i=1;i<=n;i++)
{
if(n%i == 0)//ispituje deljivost sa trenutnom vrednošću promenljive "i"
{
br++;//ako je deljiv sa "i" povećava broj delilaca za 1
cout << i << " ";
}
}
cout << endl;
return br;
}
int main()
{
int a1,brDel=0,n;
cin >> a1 >> n;
int x=a1;//tekuci element niza
for(int i=1; i {
brDel=brojDelioca(x);
x=x+brDel;
cout << x << endl;
brDel=0;
}
cout << x << endl;
return 0;
}

4. Mesto K-tog pojavljivanja broja

Napomena: Zadatak  je za 5. i 6. razred i preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Pogledajmo sledeće redove:
1
121
​12321
1234321
123454321
............................
Red čiji je redni broj M (M=1, 2, 3, ...) se formira zapisivanjem redom prirodnih brojeva od 1 do M, a zatim zapisivanjem brojeva u obratnom smeru od M-1 do 1. Sada formiramo beskonačni red uzimajući prvi od gore navedenih redova i dodajući mu
drugi red, zatim dodajemo treći red i tako dalje.
Početak formirane beskonačne serije brojeva izgleda ovako: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 ...
Članovi ove serije su numerisani počev od jedan. Napišite program koji pronalazi na kom mestu se dati broj n javlja po k-ti put.
Ulaz
U jedinom redu standardnog ulaza data su dva cela broja n i k, odvojena jednim
znakom razmaka (0<n≤1000000, 0<k≤1000000).
Izlaz
Na standardnom izlazu, program mora da ispiše ceo broj - pozicija k-te pojave
broja n u nizu.
Primer 1
Ulaz
1 1
Izlaz
1
Primer 2
Ulaz
2 2
Izlaz
6
Primer 3
Ulaz
3 3
Izlaz
14

Analiza četvrtog zadatka 

Za rešavanje zadatka potrebno je prethodno poznavanje sledećih oblasti:
Grananje u programu
Petlje
Uočimo sledeće pravilo. Analizirajmo broj, podniz gde je taj broj u sredini podniza, dužinu podniza i poziciju poslednjeg elementa na kraju tekućeg podniza.
Broj Novi član se dodaje nizu Dužina podniza Pozicija na kraju
1 1 1 1
2 1 2 1 3 4
3 1 2 3 2 1 5 9
4 1 2 3 4 3 2 1 7 7
5 1 2 3 4 5 4 3 2 1 9 9
6 1 2 3 4 5 6 5 4 3 2 1 11 20

Uneti broj "n" i broj potrebnih pojavljivanja "k". Zatim kroz petlju uraditi sledeće:

  • Povećavati vrednost broja(1. kolona u tabeli)
  • Dok broj ne dostigne vrednost n pomerati samo dužinu i poziciju( 3. i 4. kolona). Do tada sigurno nema još ni jednog pojavljivanja broja n.
  • U redu (ciklusu) u kojem je brojač dostigao vrednost n, dostignuto je prvo pojavljivanje koje se u podnizu nalazi tačno na sredini.
  • U narednim redovima ukoliko je više od dva pojavljivanja do dostizanja k-tog pojavljivanja, pored promena pozicije i dužine po utvrđenom pravilu, treba povećavati broj pojavljivanja za 2
  • U narednim redovima ukoliko je manje ili jednako od dva pojavljivanja do dostizanja k-tog pojavljivanja, imamo 2 slučaja
  • Prvi slučaj da je ostalo samo još 1 pojavljivanje, onda je tražena pozicija za n mesta udaljena od poslednje zapamćene(4. kolona)
  • Drugi slučaj da je ostalo samo još 2 pojavljivanje, onda je tražena pozicija za (duzinaPodniza + 1 -n) mesta udaljena od poslednje zapamćene(4. kolona), a to se može zaključiti posmatranjem druge kolone
#include < iostream >
using namespace std;

int main()
{
int n,k,poz,pom=0,broj=0,poj=0;
cin>>n>>k;//n- broj, k- broj pojavljivanja broja n
poz=0;
do
{
broj++;
// dok broj ne dodje do n nema pojavljivanja
/*pom je u stvari duzina podniza. Npr za broj 3, podniz
je 12321, pa je duzina 5*/
if(broj {
if(broj==1)
{
pom+=1;//sledece pomeranje
}
else
{
pom+=2;
}
poz=poz+pom;//pozicija na kraju niza
}
else if(broj==n) //Pocinje da broji
{
poj=1;//Prvo pojavljivanje
if(poj==k) //slucaj za n=1
{
poz=poz+n;
break;
}
pom+=2;//Dužina podniza u tekucem ciklusu
poz=poz+pom;//Nova pozicija
}
else
{
if(poj {
poj+=2;
pom+=2;//dužina podniza je za 2 veća od prethodne
poz=poz+pom;//pozicija poslednje cifre se pomera za dužinu podniza
}
else if(poj == k-2)//ostaju još dva pojavljivanja
{
pom+=2;
poz=poz+pom;//pozicija koja bi bila na kraju
poz=poz+1-n;//drugo pojavljivanje od poslednjeg je udaljeno za n-1
break;
}
else//ostaje još jedno pojavljivanje
{
poz=poz+n;
break;
}
}
}
while(poj < k);
cout << poz << endl;
return 0;
}

5. Neparan broj delilaca

Napomena: Zadatak  je za 7. i 8. razred i preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/
​Napišite program koji pronalazi koliko celih brojeva koji se nalaze između dve zadate vrednosti a i b (uključujući a i b) ima neparan broj delilaca.


Ulaz

U jedinom redu standardnog ulaza date su dva cela broja a i b , odvojena jednim znakom razmaka (0 < a ≤ b <1015).

Izlaz

Na standardnom izlazu, program mora da ispiše ceo broj - broj celih brojeva između a i b (uključujući a i b) koji imaju neparan broj delilaca.

Primer 1
Ulaz
3 12
Izlaz
2
Pojašnjenje primera: Delioci brojeva od 3 do 12 su sledeći:
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1,2,3,4,6,12
Vidimo da ukupno dva broja (4 i 9) imaju neparan broj delilaca.

I način: metoda grube sile

Uneti a i b

Napraviti metodu koja vraća broj delilaca za poslat ceo broj kao parametar

Menjati delioce "d" kroz petlju od 1 do maksimalno vrednosti jednake celom broju "a" poslatom kao parametar

U toj petlji proveravati deljivost broja "a" i delioca "d"

Ako je deljivo povećati brojac za 1

Funkcija vraća vrednost brojača(ceo broj)

U glavnoj funkciji formirati petlju koja menja tekući broj za proveru od vrednosti a do vrednosti b

U vesti brojač koji treba da se od početne vrednosti jednake "0" povećava svaki put kada funkcija koja broji delioce tekućeg broja vrati vrednost koja je neparna

Ispisati ovu vrednost.

II način: Optimizovan

Umesto metode koja vraća broj delilaca nekog broja, napraviti metodu koja vraća logičku promenljivu i koja je true ako je broj potpun kvadrat, jer samo potpun kvadrat ima neparan broj delioca.

III način: potpuno optimizovan

II način popraviti unutar glavne metode: Ne proveravati sve moguće vrednosti od a do b, nego pronaći minimalan i maksimalan broj u tom intervalu koji su potpuni kvadrati, pa onda proveravati brojeve od tog minimuma do tog maksimuma.

6. Bašta sljezove boje

Napomena: Zadatak  je za 7. i 8. razred i preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​​Sećate se "Bašte sljezove boje", divne knjige Branka Ćopića i avantura malog Baje, samardžije Petraka, Bajinog djeda,... Mali Baja ima nekoliko kartica i na svakoj kartici je upisan ceo broj između 1 i 10. Baja i stari Petrak su krenuli u pohod na Mjesec. Za to vreme djed Rade koji baš ne vidi dobro je poređao u kartice u niz.
Kada se Baja vratio sa neuspešnog pohoda na Mjesec, započeo je deljenje kartica. U svakom deljenju je želeo da posloži dobijene kartice od najmanje do najveće (npr. ako ima kartica koje se ponavljaju. te kartice se nalaze jedna uz drugu). Pomozite Baji tako što ćete napisati program koji izračunava koliko puta je Baja pogrešio i nije složio karte kako je želeo.


Ulaz

Iz prvog reda standardnog ulaza čitajte ceo broj N - ( 1 < N < 100) - broj deljenja koje je Baja igrao, zatim broj k (2 < k < 10) - broj karata u svakom deljenju, a zatim za svako deljenje po k karata navedenih onako kako ih je Baja složio. Svaki broj je naveden u zasebnom redu.

Izlaz

U jednom redu standardnog izlaza, Vaš program treba da prikaže broj deljenja u kojima Baja nije dobro složio kartice.

​Primer 1
Ulaz
4
3
1
2
3
4
3
4
1
5
5
8
8
8
Izlaz
1
Učitani su podaci za 4 deljenja. Dobro je posloženo prvo, treće, četvrto deljenje.
Nije dobro posloženo drugo deljenje sa karticama 4,3,4.

I način: Upotrebom ugnježdene petlje


Uneti n i k

Napraviti dve for petlje, jedna da bude ugnježdena u drugoj. Spoljašnja simulira promenu deljenja, N puta.

Unutrašnja uzima tekući broj koji je u tom ciklusu i učitan i poredi sa prethodnim u okviru istog deljenja, tj. u prethodnom ciklusu ugnježdene petlje. U svakom novom ciklusu tekući broj postaje prethodnik za novi ciklus.

Ako se dobije da u nekom ciklusu tekući i prethodni broj nisu u neopadajućem poretku, konstatuje se da je tekuće deljenje "neispravno" i brojač neispravnih deljenja se poveća za 1. Postupak se pomoću spoljašnje petlje ponavlja i za ostala "deljenja", tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.

II način: Upotrebom vektora

Uneti brojeve na karticama u vektor za svako deljenje. Deljenja se menjaju pomoću petlje.

Napraviti kopiju vektora i sortirati(samo kopiju) po neopadajućem redosledu.

Uporediti kopiju vektora sa originalom. Ako su jednaki, to znači da je i originalni vektor bio u samom početku ispravno sortiran. Dakle, ako nisu jednaki reč je o "lošem" deljenju i brojač loših deljenja se povećava za 1.

Postupak ponoviti i za ostala deljenja, tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.

7. Dinosaurus Dino

Napomena: Zadatak  je za 7. i 8. razred i preuzet je sa sajta društva matematičara srbije: dms.rs/informatika-osnovne-skole/
Dinosaurus Dino uživa na turniru koji je organizovao poznati Internet pregledač.
Sećate se igre Chrome donosaurus, tj. Igre sakupljanje kaktusa. Svaki učesnik u igri ima pravo da sakuplja redom uzastopne kaktusa, poređanih duž prave linije. Državna komisija treba da odredi prag za prolazak takmičara sa prvog nivoa igre na sledeći nivo gledajući isključivo broj skupljenih kaktusa. U ovoj igri učestvuje veliki broj takmičara. Dino održava tabelu sa poenima i takmičari ga stalno pitaju koji bi broj takmičara prošao dalje kada bi donja granica prolaza bila toliko i toliko poena (dalje se plasiraju svi učesnici čiji je broj poena veći ili jednak donjoj granici). Dino je odlučio da napiše program koji daje odgovor na ta pitanja. Sa standardnog ulaza učitava se broj takmičara n (1 ≤ n ≤ 50000), a zatim i poeni takmičara (prirodni brojevi), zadati u sortiranom redosledu od najvećeg
do najmanjeg i razdvojeni razmacima. Nakon toga se učitava broj m (1 ≤ m ≤ 50000) koji predstavlja broj pitanja na koja Dino treba da odgovori, a zatim i m brojeva razdvojenih razmacima za koje je potrebno dati odgovor koliko bi se takmičara plasiralo kada bi se taj broj uzeo za donju granicu. Na standardni izlaz ispisati tražene brojeve takmičara koji su se plasirali, u posebnom redu za svaku donju granicu..
Primer:
Ulaz
5
79 63 63 46 13
4
85 40 60 5
Izlaz
0
4
3
5

Pojašnjenje
ako je prag 85 poena, niko se nije plasirao
ako je prag 50 poena, plasirali su se takmičari sa osvojenih 79, 63, 63 i 46 poena
ako je prag 60 poena, plasirali su se takmičari sa osvojenih 79, 63 i 63 poena
ako je prag 5 poena, svi su se takmičari plasirali

Upotrebom vektora


Uneti n, a zatim niz ili vektor od n elemenata koji predstavljaju poene takmičara u sortiranom redosledu od najvećeg ka najmanjem.

Učitati m, kao broj pitanja, a zatim kreirati drugi vektor sa m elemenata za prag poena po 1 pitanju na koje treba dati odgovor o broju takmičara koji bi prošli u slučaju da je granica taj prag.

Za svako pitanje pozvati metodu, koja:

Vrši linearnu pretragu, tažeći u nizu sa poenima takmičara prvu koja je manja od praga, pri tom brojeći broj ciklusa. kada se vrednost pronađe, prekida se ciklus, i konstatuje da je pronađen

Po izlasku iz ciklusa razlikujemo 2 slučaja:

1) Ako je pronađen, onda se ispisuje broj ostvrenih ciklusa, jer to je i ujedno broj takmičara koji su prešli prag, tj. imaju veći broj poena.

2) Ako nije pronađen, ispisati: "0".

Državno takmičenje iz 2019

9. Visoki učenici

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Poznate su visine svih učenika jedne škole. Napiši program koji određuje najvišeg dečaka i najvišu devojčicu u toj školi, određuje ko je od njih viši i ispisuje razliku njihovih visina.
Ulaz
Sa standardnog ulaza se unosi broj učenika (5 ≤ 𝑛 ≤ 100), a zatim u svakom od 𝑛 narednih redova podaci za po jednog učenika. Za svakog učenika se unosi visina (ceo broj između 120 i 200) i oznaka pola (m za muški pol i z za ženski), razdvojeni
jednim razmakom. Pretpostaviti da postoji bar jedan dečak i bar jedna devojčica.
Izlaz
Ako je najviša devojčica viša od najvišeg dečaka, na standardni izlaz ispisati z, razmak i zatim za koliko je viša. Ako je najviši dečak viši od najviše devojčice, na standardni izlaz ispisati m, razmak i zatim za koliko je viši. Ako su iste visine, ispisati samo "=".
Primer
Ulaz
5
152 z
174 m
165 z
172 m
170 z
Izlaz
m 4

Uneti broj "n" i napraviti petlju koja ima n ponavljanja. Zatim kroz petlju uraditi sledeće:

  • Uneti podatke iz jednog reda unosa, visinu i pol. Za pol koristiti char promenljivu
  • Ispitati da li je pol muški ili ženski. Odrediti posebno maksimum visine za muški, a posebno za ženski pol.

Uporediti maksimume visina koji su određeni prethodno i ispisati traženu poruku

#include < iostream >
using namespace std;

int main()
{
int n,m=0,z=0;
cin >> n;
for(int i=0; i {
int v;
char p;
cin >> v;
cin >> p;
if(p=='m')//ispituje se da li je pol muski
{
/*Određuje se maksimalna visina za muskarce*/
if(v > m)
{
m=v;
}
}
else if(p == 'z')//ako je pol jednak ženskom
{
/*Određuje se maksimalna visina za žene*/
if(v > z)
{
z=v;
}
}
}
/*poredi najvecu musku i najvecu zensku visinu*/
if(m>z)
{
cout << "m " << (m-z) << endl;
}
else if(m == z)
{
cout << "=" << endl;
}
else
{
cout << "z " << (z-m) << endl;
}
return 0;
}

10. Knjiga

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Nizom 𝑎 date su dužine 𝑛 poglavlja jedne knjige. Elementom 𝑎0 je dat broj stranica za prvo poglavlje, elementom 𝑎1 za drugo i tako redom. Potrebno je knjigu podeliti na dva dela, tako da se ukupni brojevi strana u ta dva dela najmanje razlikuju. Podela
se vrši iza nekog od poglavlja. Ako postoje dve moguće podele sa istom najmanjom razlikom, podela se vrši nakon ranijeg od dva poglavlja (tako da prvi deo bude kraći). Napiši program koji određuje nakon kog poglavlja treba izvršiti podelu.

Ulaz
U prvoj liniji standardnog ulaza nalazi se prirodan broj 𝑛 (1 < 𝑛 ≤ 50000). U sledećih 𝑛 linija nalaze se po jedan prirodan broj (između 1 i 1000), brojevi predstavljaju brojeve stranica svakog poglavlja.

Izlaz
Na standarnom izlazu prikazati u jednoj liniji redni broj poglavlja (poglavlja se broje od nule) posle kog treba izvršiti podelu knjige.
Primer
Ulaz
5
100
120
50
150
70
Izlaz
1
Kada se podela izvrši posle poglavlja broj 1 (to je drugo poglavlje), tada prvi deo knjige sadrži 220, a drugi 270 strana, što daje najmanju moguću razliku od 50 strana.
Ako bi se podela izvršila nakon poglavlja broj 2 (to je treće poglavlje), prvi deo bi sadržao 270 strana, a drugi 220, što bi takođe bila razlika 50, međutim, po uslovima zadatka u tom slučaju podela se vrši tako da prvi deo knjige bude kraći,
pa je rešenje 1 (podela se vrši posle poglavlja broj 1).

Analiza zadatka

Ako bi poglavlja označili indeksima od 0 do n, onda bi mogli da uočimo 4 niza. Prvi je broj knjiga po svakom poglavlju. To je inače niz koji se unosi. Drugi niz je broj strana koji se dobija sabiranjem broja strana svih poglavlja, do posmatranog, sa leve strane. Treći niz predstavlja zbir strana svih preostalih poglavlja, od tekućeg poglavlja pa do kraja knjige, tj. desno od tekućeg poglavlja. Četvrti niz dobijemo ako od 3. oduzmemo elemente 2. niza.Posmatrajmo to u sledećoj tabeli:
0 1 2 3 4
100 120 50 150 70
100 220 270 420 490
390 270 220 70 0
290 50 -50 -350 -490
Potrebno je naći dakle, najmanju razliku broja knjiga desno i levo od kraja tekućeg poglavlja, što praktično znači najmanji broj po apsolutnoj vrednosti u 4. nizu. Treba takođe uočiti da najmanja vrednost može biti samo prva levo od prelaza od pozitivnih ka negativnim vrednostima, ili prva desno. kasnije se te vrednosti povećavaju po absolutnoj vrednosti. Dakle to je vrednost u koloni sa indeksom 1 i 2. Pošto su one jednake po apsolutnoj vrednosti uzima se vrednost levo.

Rešiti zadatak po sledećem algoritmu:

  • Učitati broj poglavlja
  • Koristeći petlju(for) učitati niz broja strana po poglavlju, u primeru datom u tabeli, to su brojevi u prvom redu.
  • Formirati niz formiran od zbira učitanih elemenata prethodnog niza sa leve strane
  • Formirati niz formiran od zbira učitanih elemenata prethodnog niza sa desne strane. Indeks kolone menjati od poslednje ka početnoj. To su brojevi u 3. redu.
  • Kreirati 4. niz, kao razlika elemenata 3. i 2. reda
  • U istom ciklusu tražiti minimalnu vrednost razlike
  • Kada se dođe do elementa koji ima negativnu razliku prekinuti ciklus

#include < iostream >
using namespace std;
int main()
{
int n,z=0,minR;
cin >> n;
int a[n],l[n],r[n];
for(int i = 0; i < n; i++)
{
cin >> a[i];
z=z+a[i];
l[i]=z;
}
minR=z;//Najveća moguća razlika je jednaka zbiru svih elemenata
z=0;
for(int i=n-1; i>=0; i--)
{
r[i]=z;
z=z+a[i];
}
int raz;
int ind=0;
for(int i=0; i < n; i++)
{
raz=r[i]-l[i];//razlika između levog i desnog dela knjige u odnosu na kraj tekućeg poglavlja

//svaka sledeca razlika ce biti veca
if(raz < 0)
{
minR=(abs(raz) < minR) ? abs(raz):minR;
ind=(abs(raz) break;
}
//ako se naiđe na manju razliku, ona se pamti kao minimalna
if(raz < minR)
{
minR=raz;
}
}
cout << ind << endl;
return 0;
}

11. Rastuće cifre

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Napiši program koji među unetim brojevima pronalazi one kojima su cifre strogo rastuće, gledajući od cifre najveće težine (prve cifre sleva).


Ulaz Sa standardnog ulaza se učitava broj □ (1 ≤ □ ≤ 5000), a zatim i □ prirodnih brojeva većih ili jednakih od 10 i manjih ili jednakih od 109 , svaki u posebnom redu.

Izlaz
Na standardni izlaz ispisati tražene brojeve sa rastućim ciframa, svaki u posebnom redu.

Primer
Ulaz
3
123
222
321
Izlaz
123
​

Rešiti zadatak po sledećem algoritmu:

  • Uneti ceo broj
  • Odrediti koliko ima cifara. To se može uraditi ili while petljom ili korišćenjem funkcije log10 iz zaglavlja cmath. Videti detaljnije objašnjenje na strani Priprema za okružna takmičenja
  • Otvoriti petlju, najbolje do-while
  • Unutar petlje:
    1. Izdvajati cifru sa leve strane
    2. Skratiti broj za tu cifru deljenjem sa stepenom broja 10 čiji je izložilac za 1 manji od broja cifara ostatka broja. Npr. Ako je broj 12345, treba izdvojiti cifru 1, pa podeliti broj sa 104, tako da broj u sledećem ciklusu bude 2345
    3. Proveriti da li je tekuca cifra u rastućem poretku sa prethodnom cifrom
    4. Tekuća cifra biće prethodna u sledećem ciklusu
    5. Ako je prvi ciklus zapamptiti tekuću cifru kao prethodnu za sledeći ciklus i odmah preći u naredni ciklus
    6. Ako prethodna i tekuća cifra nisu u rastućem poretku konstatovati da poredak nije rastući postavljanjem logičke promenljive na false i prekinuti cikluse
  • Ako je logička promenljiva koja ispituje da li je redosled rastući ostala na true ispisati broj
  • Za promenu broja koji se ispituje koristiti petlju tako da druga petlja koja razdvaja cifre bude ugnježdena

#include < iostream >
#include< cmath >
using namespace std;
int main()
{
int n,brCif=0;
cin >> n;
int broj[n];
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> broj[i];
}
//analiza
for(int i=0; i < n; i++)
{
brCif=(int)log10(broj[i])+1;//Određuje broj cifara
//ispituje da li je rastuci poredak
bool rastuci=true;//pretpostavi se da je rastući redosled
int d=(int)pow(10,brCif-1);//pocetni delilac
int p,j=0;//prethodna cifra, kontrolna promenljiva za do-while ciklus(pomeranje po ciframa)
int a=broj[i];//broj kome ce se skidati cifre levo, u pocetku jednak unetom broju
do
{
int c=a/d; //cifra sa leve strane
a=a % d; //skida cifru sa leve strane tekucem broju a. Npr Od 123, broj postaje 23
d /= 10; //d=d/10
if(j==0)//prvi ciklus
{
p=c;
j++;
continue;//prelazak u sledeći ciklus
}
//proverava rastuci poredak
if(c <= p)
{
rastuci=false;
break;
}
p=c;//tekuca cifra postaje prehodna za sledeci ciklus
j++;//povecava broj ciklusa za 1
} while(d>=1);
if(rastuci)
{
cout << broj[i] << endl;
}
}
return 0;
}

12. Razlika visina

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​U jednoj školi biraju se glumci za školsku predstavu u kojoj likovi koje tumače imaju veliku razliku u visini. Napiši program koji određuje na koliko načina možemo da odaberemo dva glumca iz odeljenja tako da im je razlika visina jednaka datom broju 𝑟.
Ulaz
Sa standardnog ulaza se unosi prvo pozitivan prirodan broj 𝑟 (1 ≤ 𝑟 ≤ 1000), u
narednom redu broj učenika 𝑛 (1 ≤ 𝑛 ≤ 50000), a nakon toga u narednih 𝑛 redova
visina svakog učenika (broj između 1 i 100000).
Izlaz
Na standardni izlaz ispiši broj parova koje je moguće formirati.
Primer 1
Ulaz
10
5
150
160
165
170
175
Izlaz
3
Moguće je napraviti parove od prvog i drugog deteta (150, 160), od drugog i četvrtog deteta (160, 170) i trećeg i petog deteta (165, 175).

Primer 2
Ulaz
23
5
157
180
157
162
134
Izlaz
4
Moguće je napraviti parove od prvog i drugog deteta (157, 180), od petog i prvog (134, 157), od drugog i trećeg (157, 180) i od petog i trećeg deteta (134, 157).
Napomena
U 20 od 25 test­primera sva deca će biti različite visine.

Analiza zadatka

Ako se visine učitaju kao niz, trebalo bi ga prvo sortirati. Da bi se napravile sve kombinacije parova i razlika visina tih parova uporediti sa zadatom treba s jedne strane menjati prvi element niza , odnosno visinu prvog deteta u okviru para  a sa druge strane za fiksiranu vrednost prve visine menjati drugu vrednost u paru. Za ovo se mogu koristiti dve petlje u kojoj je jedna ugnježdena u drugoj. Obe petlje mogu da menjaju vrednosti linearno, od početka do kraja ili, jedna linearno, dok druga po principu Binarne pretrage, što bi bilo efikasnije.

Rešiti zadatak po sledećem algoritmu:

  • Uneti dva cela broja, traženu razliku i broj dece.
  • Učitati niz visina dece
  • Otvoriti dve petlju, jednu ugnježdenu u drugoj
  • Sortirati niz po rastućem redosledu.
  • U petlji formirati razliku visina i uporediti sa zadatom.
  • Ako je razlika jednaka zadatoj povećati traženi broj parova za 1
  • Iterativno kroz unutrašnju petlju menjati drugu visinu unutar parova visina sve dok razlika visina ili ne bude pronađena ili dok se ne dođe do veće razlike od zadate i tad prekinuti unutrašnju petlju, jer bi svaka sledeća razlika bila još veća
  • Po izlasku iz petlje štampati traženi broj parova

#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
int r,n,b=0;
cin >> r >> n;
int v[n]; //niz visina
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> v[i];
}
/*Sortiranje niza visina*/
sort(v,v+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
for(int j=i+1; j < n; j++)
{
int raz=v[j]-v[i];//razlika visina
if(raz==r)//Ako je razlika visina jednaka zadatoj
{
b++;//Povećava broj nađenih parova za 1
}
else if(raz > r )/*Ako je razlika veća od zadate prekidaju se promene druge
visine u paru, jer svaka sledeća razlika je sve veća*/
{
break;
}
}
}
cout << b << endl;
return 0;
}

Efikasnije rešenje sa binarnom pretragom

Rešiti zadatak po sledećem algoritmu:

  • Uneti dva cela broja, traženu razliku i broj dece.
  • Učitati niz visina dece
  • Otvoriti dve petlju, jednu ugnježdenu u drugoj
  • Sortirati niz po rastućem redosledu.
  • U petlji formirati razliku visina i uporediti sa zadatom.
  • Ako je razlika jednaka zadatoj povećati traženi broj parova za 1
  • Unutrašnja petlja menja drugu visinu tražeći onu čija je razlika sa prvom visinom jednaka zadatoj. Pretraživanje vršiti koristeći algoritam binarne pretrage. Dakle menjati krajnje levu i krajnje desnu poziciju posmatranog podniza.
    Ovaj podniz je u početku jednak celom nizu, što znači da su krajnja leva i krajnja desna pozicija u početku krjnje pozicije celog niza.
    Unutar ciklusa se najpre određuje srednja pozicija.Zatim se pronalazi razlika elementa niza na toj, srednjoj poziciji i visine prvog deteta unutar tekućeg para. Ako je ta razlika baš ona zadata, povećava se broj pronađenih parova za 1.
    Treba proveriti da li ima jos vrednosti sa jednakom razlikom, npr. ako postoji vise dece sa istim visinama.
    Ako ne, onda dalje proveriti da li je trazena razlika u levoj ili desnoj polovini tekuceg podniza i u skladu sa tim pomeriti krajnje desnu ili krajnje levu poziciju podniza u sledecem ciklusu.
  • Po izlasku iz petlje štampati traženi broj parova

#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
int dif,n,b=0;
cin >> dif >> n;//dif-trazena razlika,n-broj dece
int v[n]; //niz visina
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> v[i];
}
/*Sortiranje niza visina*/
sort(v,v+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
int l=i+1,r=n-1;//niz za pretragu je od pozicije i+1 pa do n-1, l-left,r-right
while(l <= r)//ciklus traje sve dok je leva pozicija manja ili jednaka desnoj
{
int mid=(l+r)/2;;//srednja pozicija intervala[l,r]
int raz=v[mid]-v[i];//razlika visina
//Ako je razlika jednaka dif pronadjen je novi par cija je razlika visina jednaka zadatoj
if(raz==dif)
{
b++;//broj parova se uvecava za 1
int k=mid+1;
while(v[k]==v[mid])
{
b++;
k++;
}
k=mid-1;
while(v[k]==v[mid])
{
b++;
k--;
}
break;
}
else if(dif {
r=mid-1; //desna granica za novu pretragu je prva pozicija levo u odnosu na srednju vrednost
}
else if(dif > raz)//Ako je ocekivana razlika veca od stvarne, ocekivana vrednost je u desnoj polovini
{
l=mid+1;//leva granica za novu pretragu je prva pozicija desno u odnosu na srednju vrednost
}
}
}
cout << b << endl;
return 0;
}

Državno takmičenje 2018

13. Kupovina

Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

    Poznate su sve cene predmeta koji se prodaju u jednoj prodavnici. Kupac ima na raspolaganju određeni iznos dinara i želi da kupi što skuplje predmete. Redom uzima predmete počev od najskupljeg, dok ima novca. Ako nema novca za najskuplji, uzima najskuplji za koji ima novca.
Napomena: ova strategija ne garantuje da će predmeti koje kupi biti ukupno najveće moguće vrednosti (npr. ako ima 5 dinara i ako su cene predmeta 4, 3 i 2 dinara, on će kupiti predmet samo predmet od 4 dinara, a mogao bi da kupi predmete od 3 i 2 dinara).
Napiši program koji određuje koliko novca kupcu preostaje nakon kupovine na opisani način. U prvoj liniji standardnog ulaza nalazi se iznos novca (ceo broj) koji ima kupac, u drugoj broj predmeta, N (prirodni broj manji od 50000), a zatim se u narednoj liniji unose redom cene predmeta, razdvojene razmacima. Na standarni izlaz ispisati preostali iznos novca, nakon kupovine na opisani način
​Primeri
Ulaz 
1250 
5 
1010 357 725 1125 115 
Izlaz 
10  

Ulaz
10000
6
3010 3005 5725 1265 2075 385
Izlaz
0

Rešenje:

Priprema za državna takmičenja-2018. Zadatak
Slika 1: Priprema za državna takmičenja-2018. Zadatak "Kupovina"-algoritam

Algoritam zadatka je prikazan na slici:
Niz a sadrži cene predmeta. Niz bi trebalo sortirati po opadajućem redosledu, kao što se može videti u donjem delu slike. 
Ostatak je u početku jednak novcu sa kojim raspolaže kupac.
Unutar petlje prvo se pomeraju elementi niza sve dok se ne naiđe na prvu vrednost koja je manja od trenutnog ostatka, jer se u suprotnom predmet ne mođe "kupiti".
Zatim se ostatak preračunava, tako što se cena tog predmeta, oduzme od trenutnog ostatka(U primeru: novi ostatak je 125).
Postupak se kroz petlju ponavlja, tako da sledeći element u nizu koji treba oduzeti je u datom primeru 115, a kada se ta vrednost oduzme od prethodnog ostatka(115) dobiće se vrednost ostatka=10.

14. Binarni nizovi

Napisati program kojim se prikazuju svi binarni nizovi (nizovi koji sadrže samo nule i jedinice) dužine n koji ne sadrže dve uzastopne jedinice. Nizove prikazati u leksikografskom poretku (tako da su binarni brojevi formirani od tih nizova poređani rastuće). Prva linija
standardnog ulaza sadrži prirodan broj n (n ≤ 10). Na standardnom izlazu prikazati tražene binarne nizove u leksikografskom poretku, svaki niz u posebnoj liniji.
Primer
Ulaz 
3
Izlaz
000
001
010
100
101

Rešenje:

Picture
Slika 2: Priprema za državna takmičenja-2018. Zadatak "Binarni Nizovi"-algoritam
Zadatak se može rešiti upotrebom rekurzivne funkcije koja formira binarne nizove.
Funkcija prima kao parametre sam niz(referencu ili pokazivač na niz), dimenziju niza i redni broj rekurzije "i". Npr. ako je početna rekurzija i=0, sledeća će da bude i=1 itd. U svakoj novoj rekurziji se kreiraju najviše dve nove i ubacuje se novi po redu element, a to su brojevi 0 ili 1. Nula se svakako dodaje, a za dodavanje 1 mora se proveriti uslov da li je element na prethodnoj poziciji niza   već bila jedinica(po uslovu zadatka). Ako jeste, onda se ne poziva dalje ista funkcija rekurzivno. Na slici 2. je to predstavljeno  kvadratom sa crnom ispunom.
Ako nije prethodno bila jedinica, kao i u slučaju dodavanja nule na tekuću poziciju niza, biće pozvana ista funkcija, rekurzivno, sa promenjenim trećim parametrom, tj. poslaće se vrednost "i+1".
U datom primeru, u poslednjem rekurzivnom pozivu, za i=4, treba ispisati formirani niz, kao što je i prikazano na slici.
#include < stdio.h >

void prikaziS(int * ps,int n)
{
for(int i=0; i < n; i++)
{
int b=*(ps+i);/*Element sa i-te pozicije u nizu*/
if(b)
{
printf("1");
}
else
{
printf("0");
}
printf(" ");
}
printf("\n");
}

/*Rekurzivna funkcija koja formira binarne nizove
* Parametri: ps-pokazivac na niz, n-broj elemenata niza, i-indikator rekurzivnog poziva
*/
 void binarniNizovi_(int * ps,int n,int i)
{
/*Ispituje da li je dosao do poslednje cifre*/
if(i==n)
{
prikaziS(ps,n);//Poziv funkcije koja treba da ispise binarni niz
return;
}
/*sledecaa cifra, false, tj. nula*/
*(ps+i)=0;/*s[i] pristupa elementu vektora na poziciji i i zadaje u pocetku false*/

binarniNizovi_(ps,n,i+1);/*Novi poziv rakurzivne funkcije*/
/*Ako je prva cifra mora poceti sa 1 i ako je prethodna bila 1 ova mora biti nula jer ne sme
da sadrzi dve uzastopne jedinice*/
if(i==0 || *(ps+i-1)==0)
{
*(ps+i) = 1;
/*Rekurzivan poziv finkcije binarniNizovi_ da odredi sledecu cifru */
binarniNizovi_(ps,n,i+1);
}
}

/*Funkcija koja pocinje kreiranje binarnih nizova*/
void binarniNizovi(int n)
{
int s[n];
binarniNizovi_(s,n,0);
}
int main()
{
int n;
scanf("%d",&n);
binarniNizovi(n);
return 0;
}

15. Akcije

Vrednost akcija jedne kompanije varirala je iz dana u dan tokom jednog dužeg vremenskog perioda. Napiši program koji određuje koliko ima nizova uzastopnih dana u kojima je ukupan zbir promena vrednosti akcija jednak datom broju z. Sa standardnog ulaza se u prvoj liniji unosi taj broj z (ceo broj -10000 i 10000), zatim, u narednoj liniji broj dana n u kojima se pratila promena vrednosti
akcija (3 ≤ n ≤ 50000) i zatim u narednoj liniji promene za svaki od dana u odnosu na prethodni dan (celi brojevi između -100 i 100) razdvojeni razmacima. Na standardni izlaz ispiši broj perioda u kojima je ukupna promena jednaka z (tj. broja nepraznih segmenata niza promena čiji je zbir jednak z).
​
Primer
Ulaz
11
10
1 2 3 5 1 -1 1 5 3 2
Izlaz
7
Objašnjenje:
sledeći segmenti imaju zbir 11
1 2 3 5
1 2 3 5 1 -1
2 3 5 1
2 3 5 1 -1 1
5 1 -1 1 5
1 -1 1 5 3 2
1 5 3 2

Državno takmičenje iz 2016 godine

16. Deljivi

U svakom zadatku vremensko ograničenje je 1 sekunda, a memorijsko ograničenje je 64 MB.
​
Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/
Zadatak je za 2. kategoriju(7 i 8 razred)

Data su dva cela broja a, b (0<a<b<1 000 000 000 000 000) i ceo broj c (1<c<1 000 000 000 000 000). Napisati program (konzolnu aplikaciju) DELJIVI koja će ispisati koliko celih brojeva između a i b (uključujući i a i b) je deljivo datim brojem c .
ULAZ: U prvom redu standardnog ulaza dat je prirodan broj a, u drugom redu standardnog ulaza dat je prirodan broj b, u trećem redu standardnog ulaza dat je prirodan broj c.
IZLAZ: U jedinom redu standardnog izlaza ispisati traženi broj sadržalaca.

Primer 1:
Ulaz:
8
40
5
Izlaz:
7

Primer 2:
Ulaz:
8
40
8
Izlaz:
5

Primer 3:
Ulaz:
8
1234567890
8
Izlaz:
154320986​
Rešenje:

Najednostavnije, ali ne i dovoljno efikasno rešenje(Ne zadovoljava sve test primere zbog vremenskog ograničenja) je metod, da se kroz  petlju menjaju brojevi od "a" do "b" i da se svaki od njih proveri, da li je, ili ne deljiv sa deliocem "c".
#include < stdio.h >

int main()
{
unsigned long long int a,b,c,br=0;
scanf("%llu%llu%llu",&a,&b,&c);

/*Menjaju se brojevi čija se deljivost ispituje kroz for petlju*/
for(unsigned long long int i=a;i <= b;i++){
/*Ako je tekući ispitivani broj"i" deljiv sa "c", brojač se povećava za 1*/
if(i%c == 0){
br++;
}
}
printf("%llu\n",br);
return 0;
}
Nešto efikasnije rešenje bi se dobilo, ako kada se naiđe na prvi broj koji je deljiv sa "c", sledeći broj za ispitivanje ne bude odmah za 1 , nego za "c" veći. Npr. u prvom primeru se ispituju brojevi počev od 8 pa do 40. Prvi broj u tom intervalu koji je deljiv sa "5" je broj 10. Sledeći broj za ispitivanje treba da bude za "5 veći". Na ovaj način bi prošli skoro svi test primeri, osim ako je vrednost delioca "c" suviše "mala".
U nastavku je pokazana ova varijanta rešenja. Takođe je pokazano kako da se vrednosti čitaju iz datoteka, umesto sa standardnog ulaza. Datoteke su označene npr: "deljivi.01.in", "deljivi.02.in" itd. Test primeri su kopirani u podfolderu "deljivi" unutar korenog direktorijuma aplikacije. Dodatak koda je oznčen crvenom bojom.
#include < stdio.h >

 #define DATOTEKA "deljivi/deljivi.01.in"
 int main()
{
FILE*ulaz;
ulaz=fopen(DATOTEKA,"r");
if(!ulaz)
{
printf("Datoteka %s nije uspesno otvorena za citanje",DATOTEKA);
}
 unsigned long long int a,b,c,br=0;
//scanf("%llu%llu%llu",&a,&b,&c);
fscanf(ulaz,"%llu%llu%llu",&a,&b,&c);
 /*Logička promenljiva koja indikuje da li je ispitivanje stiglo do prvog deljivog broja sa "c"*/
int prvi=0;
/*Definiše promenljivu "i" kao veliki celobrojni neoznačen podatak i inicijalizuje prvo na vrednost delioca "c"*/
unsigned long long int i=c;
/*Ako je delilac "c" manji od prvog broja čija će se deljivost ispitati, onda prvi broj treba da bude jednak "a"*/
if(i < a){
i=a;
}
/*Menjaju se brojevi čija se deljivost ispituje kroz while petlju*/
while(i <= b){
/*Ako još nije naišao na prvi deljiv sa "c" i ako broj još nije deljiv sa "c"*/
if(!prvi && i%c != 0){
i++;
}
/*Ako još nije naišao na prvi deljiv sa "c" i ako je broj sada deljiv sa "c"*/
if(!prvi && i%c==0){
prvi=1;/*Naišao je na prvi deljiv sa "c" */
br++;
i=i+c;
/*Pomera se za "c" vrednosti jer do te vrednosti brojevi sigurno neće biti deljivi sa c*/
}
else if(prvi){
i=i+c;
br++;
}
}
printf("%llu\n",br);
fclose(ulaz);
 return 0;
}
Najefikasnije rešenje bi se dobilo, ako se while petlja zameni formulom, koja izračunava koliko brojeva deljivih sa "c" ima između prvog i poslednjeg broja deljivog sa "c", u datom intervalu brojeva [a,b]. Prvi može da se odredi, ako se na broj "a", doda razlika delioca i ostatka deljenja broja "a" sa brojem "c", tj:
prvi=a+c-a%c;//10=8+(5-(8%5))=8+(5-3)
Poslednji se može dobiti na sledeći način:
poslednji=b-(b%c);//poslenji = 40-(40%5)=40-0=40
Broj deljivih brojeva sa "5", posmatrajući primer 1, bi se dobio kad dužinu intervala (40-10)=30, podelimo sa deliocem tj. sa 5 u datom primeru, što daje 6 i na to treba dodati još 1 jer treba uračunati i taj početni broj. Zaključujemo da će formula biti:
br=1+(poslednji-prvi)/c;////br=1+(40-10)/5=1+30/5=1+6=7
Ovo važi u slučajevima da je prvi manji od poslednjeg, a u suprotnom je traženi broj jednak nuli. Kod je prikazan u nastavku:
#include < stdio.h >

 #define DATOTEKA "deljivi/deljivi.01.in"
 int main()
{
FILE*ulaz;
ulaz=fopen(DATOTEKA,"r");
if(!ulaz)
{
printf("Datoteka %s nije uspesno otvorena za citanje",DATOTEKA);
}
 unsigned long long int a,b,c,br=0,,prvi,poslednji;
//scanf("%llu%llu%llu",&a,&b,&c);
fscanf(ulaz,"%llu%llu%llu",&a,&b,&c);
 prvi=a + c - a%c;//10=8+(5-(8%5))=8+(5-3)
if(prvi%c == 0){
prvi=a;
}
poslednji=b-(b%c);//poslenji = 40-(40%5)=40-0=40
if(prvi < poslednji)
{
br = 1+(poslednji-prvi)/c;//br=1+(40-10)/5=1+30/5=1+6=7
}
printf("%llu\n",br);
fclose(ulaz);
 return 0;
}

Državno takmičenje 2024

Napomena: Zadaci su preuzeti sa petlje, na web lokaciji: takprog.petlja.org/
​Da bi ste proverili rešenja, ulogujte se na petlji i kliknite na link za određen razred.

17. Teške torbe

Dva mala putnika imaju ukupno četiri teške torbe. Svaki od putnika može da ponese najviše dve torbe, po jednu u svakoj ruci.  Sve torbe su zajedničke i bilo koji putnik može da nosi bilo koju torbu. U slučaju da su im torbe preteške,  naši putnici žele da koriste što manje tuđe pomoći. Poznata je težina svake torbe, kao i najveći teret koji može da ponese svaki od putnika. Potrebno je odrediti najmanju ukupnu težinu torbi koje oni ne mogu da ponesu. 

Ulaz
U prvom redu standardnog ulaza su četiri prirodna broja razdvojena po jednim razmakom, težine torbi.
 U drugom redu su dva prirodna broja razdvojena jednim razmakom, težine koje mogu da ponesu mali putnici.
  Svi brojevi su manji od 1000.
 
Izlaz
Na standardni izlaz ispisati jedan neoznačen ceo broj, najmanju ukupnu težinu torbi za koje je putnicima potrebna pomoć.
 
Primer 1
Ulaz
1 2 3 4
5 6
Izlaz
0
Objašnjenje
Jedan putnik može da ponese torbe težina 1 i 4, a drugi torbe težina 2 i 3, tako da im nije potrebna pomoć.
 
Primer 2
Ulaz
2 3 4 5
5 6
Izlaz
3
Objašnjenje
Jedan putnik može da ponese torbu težine 5, a drugi torbe težina 2 i 4, pa im je potrebna pomoć za torbu težine 3.
 
Primer 3
Ulaz
12 20 15 17
17 14
Izlaz
35
 
99 56 34 22
3 4
211
 
7 5 4 2
7 9

Uneti niz težina torbi

Uneti težine koje mogu da ponesu putnici

Napraviti rekurzivnu funkciju, koja u jednoj iteraciji ispituje ostatak težina za dve varijante, jedna ako bi prvi putnik poneo najveću torbu(prvi element sortiranog niza po opadajućem redosledu), a druga, ako bi drugi putnik poneo tu istu torbu.

Analiza prvog bi bila, da se preračuna ostatak težina koju još mogu da ponesu putnici, ako mogu, i ostatak za izlaz, odnosno koliko je od ukupne težine preostalo. Yatim se ponovo poziva rekurzivna funkcija

Slična analiza bi bila i u drugoj varijanti, samo što se sada ispituje da li drugi putnik može da ponese najveću težinu i zatim se poziva rekurzivna funkcija koja dalje ispituje ostale elemente niza težina torbi i vraća ostatak

Rekurzivna funkcija treba da vrati manju od dve ispitivane varijante

Sledeći poziv rekurzivne funkcije se razlikuje što se uzima u razmatranje sledeći član niza težina po redu i opet se analizira za dve varijante, u prvoj da torbu ponese prvi, a u drugoj, da torbu ponese drugi putnik. Od dva potencijalna ostatka ukupne težine funkcija vraća manju vrednost

Ovaj postupak se ponavlja sve do dubine 4 jer toliko ima elemenata niza težina. Kada se dođe do poslednje iteracije, rekurzija se "odmotava" i vraća poslednje dobijeni ostatak težina koji putnici nisu mogli da ponesu.

Kroz rekurzivne pozive po nivoima, treba voditi računa i o broju ponetih torbi za svakog putnika, jer se po uslovu zadatka dozvoljava da svaki putnik ponese najviše dve torbe.

18. Kvantna zavrzlama

Napomena: Zadatak za 7. razred

Tekst zadatka:
Đole je kvantni fizičar koji je osmislio eksperiment u okviru svojih doktorskih studija. Đole pokušava da određenu česticu dovede u stabilan položaj na sobnoj temperaturi. Da bi proverio da li je uspeo, on meri brzinu te čestice tokom vremena. Da bi se smatralo da je čestica u stabilnom stanju, njena brzina mora da tokom nekih k uzastopnih trenutaka osciluje, tj. da se tokom tih k  trenutaka brzina naizmenično povećava i smanjuje. Đole je sjajan fizičar, ali nije tako dobar programer i on je zamolio vas da na osnovu niza merenja odredite da li je eksperiment uspeo. 

Ulaz
U prvom redu standardnog ulaza se nalaze dva prirodna broja n i k (2≤k≤n≤106). U drugom redu se nalazi n pozitivnih realanig brojeva koji su razdvojeni razmacima. Ovi brojevi predstavljaju brzine čestice u svakom od n trenutaka koliko traje eksperiment.
 
Izlaz
U prvom redu standardnog ulaza ispisati da ili ne (malim latiničnim slovima) u zavisnosti od toga da li je eksperiment uspeo. U drugom redu ispisati najduži podniz trenutaka u kome je brzina čestice oscilovala.
 
Primer 1
Ulaz
12 7
2.7 3.7 6.9 7.8 4.3 17.11 2.6 5.8 5.9 4.1 7.9 6.2
Izlaz
ne
6
Objašnjenje
U nizu brzina koji se učitava ne postoji podniz od 6 uzastopnih elemenata u kome važi da brzina osciluje. Najduži podniz ima 6 elemenata: 6.9, 7.8, 4.3, 17.11, 2.6, 5.8
 
Primer 2
Ulaz
10 4
6.8 5.3 4.1 9.17 3.7 2.1 1.0 9.9 17.64 2.1
Izlaz
da
4
Objašnjenje
Podniz uzastopnih trenutaka 5.3, 4.1, 9.17, 3.7 ispunjava traženi uslov.
 
Primer 3
Ulaz
7 4
2.2 7.5 3.5 3.5 5.7 9.9 10.0
Izlaz
ne
3
Objašnjenje
U nizu brzina koji se učitava ne postoji podniz od 4 uzastopna elementa u kome važi da brzina osciluje. Obratite pažnju da podniz 2.2, 7.5, 3.5, 3.5 ne ispunjava uslov jer su poslednja dva elementa jednaka.
Popularna prodavnica patika, Patikarnica, odlučila je da svojim kupcima ponudi novu uslugu. Na ulazu u Patikarnicu biće postavljen ekran osetljiv na dodir koji će kupcima predlagati najskuplje modele patika koje se uklapaju u budžet koji su planirali da izdvoje za nove patike. Patikarnica je kupila svu neophodnu opremu da bi korisnicima pružila novu uslugu, ali je zamolila nas da napišemo program koji će na osnovu dostupnih patika u prodavnici i novca koji je kupac spreman da izdvoji, prikazati spisak najskupljih modela patika koje kupac može da priušti.

19. Patikarnica

Napomena: Zadatak za 7. razred
​
Tekst zadatka:
Patikarnica na stanju ima n različitih modela patika opisanih svojim imenom i cenom. Tokom dana u Patikarnicu ulazi k kupaca. Svaki kupac na ulazu unosi količinu novca x i koju želi da izdvoji za nove patike i sistem mu prikazuje spisak najskupljih patika koje može da priušti.  

Ulaz
U prvom redu učitava se broj n, (1≤n≤105), različitih modela patika u ponudi Patikarnice, zatim se u n narednih redova učitava naziv modela patika (niska maksimalne dužine 200 karaktera) i njegova cena (prirodan broj manji od 50000). Nakon toga, učitava se broj k, (1≤k≤106), kupaca koji su ušli u prodavnicu, a zatim u k sledećih redova budžeti x i (1≤i≤k) pojedinačnih kupaca (prirodni brojevi manji od 50000).
 
Izlaz
Na standardni izlaz za svakog od k kupaca i njihove budžete x i ispisati leksikografski sortiran spisak najskupljih patika koje mogu da priušte. U slučaju da ne postoje patike koje kupac može da priušti ispisati nisku nema.
 
Primer 1
Ulaz
10
NikeAirMaxIVO 16799
AsicsMetaspeedSky+ 29999
NikeVaporFly3 32899
AsicsSkzElite 17199
NikeAirMax90 20699
NikeJordanMaxAura5 17199
NikeStreakFly 13999
Adidas4DFWD3 25999
AdidasUltraBoostLight 16799
AdidasXPLRBoost 17199
2
18000
12000

Izlaz
AdidasXPLRBoost 17199
AsicsSkzElite 17199
NikeJordanMaxAura5 17199
nema

Objašnjenje
Prvi kupac je kao svoj budžet uneo iznos od 18000 dinara i najskuplje patike koje može da priušti su AdidasXPLRBoost, AsicsSkzElite i NikeJordanMaxAura5 po ceni od 17199 dinara.
 
Drugi kupac je kao svoj budžet uneo iznos od 12000 dinara i u ponudi Patikarnice nema patika koje kupac može da priušti, pa se kao rezultat upita štampa reč nema.
​

Uneti broj patika, a zatim uneti podatke o patikama i smestiti ih ili u vector čiji su podaci parovi: ključ-vrednost ili u mapu

Ključevi treba da budu string podaci koji predstavljaju naziv patika, a vrednost celobrojni podaci koji predstavljaju cene patika.

Sortirati vektor u opadajućem redosledu po vrednosti, a podaci sa istim vrednostima da budu sortirani leksikografski.

Učitati broj kupaca k, a zatim kroz petlju učitavati budžet za svakog kupca i smestiti u niz.

Izvršiti pretragu, najbolje binarnu, dok se ne pronađe najmanji par iz vektora parova(patika-cena) čija je vrednost jednaka ili manja od budžeta tekućeg radnika.

Ispitati da li ima još jednakih vrednosti sa pronađenom kroz pretragu i ako ima pomeriti poziciju na onu u vektoru čija je pozicija najmanja

Smestiti sve te vrednosti u novi vektor, za najskuplje patike za tekućeg radnika.

Ako nije pronađena ni jedna takva vrednost, ispisati "nema" za tog radnika.

Ako jeste, ispisati sve te vrednosti, za određenog radnika.

Na kraju svakog ciklusa isprazniti vektor sa najskupljim patikama.

20. Rotator slova

Napomena: Zadatak za 7. razred

​Kada se pritisne taster na tastaturi, prvo slovo svake reči u tekstu se premesti na poslednje mesto te reči. Koliko je puta potrebno pritisnuti taster da bi se rečenica vratila u početno stanje? 
Ulaz
Sa standardnog ulaza se učitava jedna linija teksta koja je sastavljena od malih slova engleske abecede i razmaka i ima najviše 106 karaktera. Svi primeri su takvi da se rečenica vraća u prvobitno stanje nakon najviše 1018 pritisaka tastera.
 
Izlaz
Na standardni izlaz ispisati najmanji broj pritisaka tastera (veći od 0) potrebnih da se rečenica vrati u prvobitno stanje.
 
Primer 1
Ulaz
mala sirena zivi na dnu mora
Izlaz
12
Objašnjenje
Pritiscima tastera dobijaju se naredne rečenice
 
mala sirena zivi na dnu mora
alam irenas iviz an nud oram
lama renasi vizi na udn ramo
amal enasir iziv an dnu amor
mala nasire zivi na nud mora
alam asiren iviz an udn oram
lama sirena vizi na dnu ramo
amal irenas iziv an nud amor
mala renasi zivi na udn mora
alam enasir iviz an dnu oram
lama nasire vizi na nud ramo
amal asiren iziv an udn amor
mala sirena zivi na dnu mora
Primer 2
Ulaz
sestaci sedmaci i osmaci vole informatiku
Izlaz
924
Primer 3
Ulaz
dada tata i mama
Izlaz
2
Napomena: U 50% test-primera reči nisu periodične. U 60% test-primera sve reči su kraće od 100 karaktera.
Rešenje:

Uneti tekst u string promenljivu

Podeliti tekst na reči

Napraviti niz brojeva čije vrednosti predstavljaju dužine reči

Ispitati svaku reč, da li postoji podstring određene dužine koji se periodično ponavlja u reči, ceo broj puta

Ako postoji za dužinu reči u niz ubaciti dužinu podstringa. Npr. ako je reč abcabc, reč je dužine 4. Međutim, podstring abc se unutar reči ponavlja 2 puta, pa onda za dužinu treba uzeti 2.

Za taj niz dalje treba naći najmanji zajednički sadržalac, upotrebom Euklidovog algoritma

Ta vrednost, je traženo rešenje. Brojevi u nizu predstavlja broj pritiska tastera za svaku reč pojedinačno, da bi se ona ponovo dovela na istu reč postepenim premeštanjem slova. NZS tih brojeva je onaj broj pritiska tastera koje će sve reči vratiti na početno stanje.

Državno takmičenje 2023

Napomena: Zadaci su preuzeti sa petlje, na web lokaciji: takprog.petlja.org/
​Da bi ste proverili rešenja, ulogujte se na petlji i kliknite na link za određen razred.

21. Parno - neparni nizovi

Napomena: Zadatak za 7. razred

​Niz je ppnn (parno-parno-neparno-neparan) ako se na parnim pozicijama u nizu (0, 2, 4, ...)nalaze isključivo parni, a na neparnim pozicijama u nizu (1, 3, 5, ...) isključivo neparni brojevi.
Napiši program koji za nekoliko učitanih nizova proverava da li su ppnn nizovi.

Ulaz
Sa standardnog ulaza se učitavaju brojevi n(5≤n≤100) i k(5≤k≤100) a zatim iz n narednih redova n
 nizova od po k elemenata čija je vrednost između 0 i 1000.

Izlaz
Za svaki od učitanih nizova na standardni izlaz ispisati da ako zadovoljava ppnn uslov, a u suprotnom ne.

Primer
Ulaz
3 5
1 2 3 4 5
2 3 4 5 6
4 7 0 9 2
Izlaz
ne
da
da
Objašnjenje
U prvom nizu se na poziciji 0 koja je parna nalazi broj 1, koji je neparan.

U drugom nizu se na parnim pozicijama nalaze brojevi 2, 4 i 6, koji su parni, a na neparnim pozicijama brojevi 3 i 5, koji su neparni.

U trećem nizu se na parnim pozicijama nalaze brojevi 4, 0 i 2, koji su parni, a na neparnim pozicijama brojevi 7 i 9, koji su neparni.

22. Prevod

Napomena: Zadatak za 7. razred

Napiši program koji implementira srpsko-engleski rečnik.
Prvo se učitava spisak reči i njihovih prevoda, a zatim korinsnik od sistema traži da mu se prevedu neke reči (bilo sa srpskog na engleski, bilo sa engleskog na srpski).

Ulaz
Sa standardnog ulaza se unosi broj n(1≤n≤50000) parova reči na srpskom i engleskom jeziku.  Sve reči na srpskom su međusobno različite i sve reči na engleskom su međusobno različite. Nakon toga se unosi m(1≤m≤50000) upita. Svaki upit sadrži željeni jezi (ili sr ili en) i zatim reč na suprotnom jeziku koju treba prevesti.

Izlaz
Na standardni izlaz ispisati sve prevode. Ako za neku reč nije unet prevod, ispisati ?.

Primer
Ulaz
3
cat macka
dog pas
mouse mis
4
en pas
sr mouse
sr lion
en mis
Izlaz
dog
mis
?
mouse
Algoritmi
Matrice
Java
Linkovi
​Politika Privatnosti
Kontakt

© 2025 by Slobodan svetprogramiranja.com

Sva prava zadržana
SVET PROGRAMIRANJA