KVALIFIKACIJE ZA OKRUŽNA TAKMIČENJA IZ INFORMATIKE ZA 8. RAZRED I SREDNJE ŠKOLE

ZADATAK 03 2022/2023.

Spisak proizvoda

1. krug kvalifikacija 6. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje

Postavka zadatka

Ljilja je svaki dan škole kupovala za užinu jabuku, kiflu ili lizalicu. Ako je poznato kolika je cena svakog proizvoda i ako je poznat spisak proizvoda koje je ona kupila tokom nekoliko dana, odrediti koliko je ukupno novca potrošila.

Oznake proizvoda

j — jabuka
k — kifla
l — lizalica

Svaki znak u niskoj predstavlja jedan kupljeni proizvod.

Ulaz

Sa standardnog ulaza učitavaju se cena jabuke, kifle i lizalice (tri prirodna broja između 10 i 100, svaki u posebnom redu). Nakon toga se učitava niska sastavljena od znakova j, k i l, dužine najviše 30 karaktera, koja određuje redom proizvode koje je Ljilja kupila.

Izlaz

Na standardni izlaz ispisati ukupnu količinu utrošenog novca.

Primer 1

Ulaz

32
30
45
jjkllkl

Izlaz

Primer 2

Ulaz

10
20
30
jkl

Izlaz

Razumevanje i rešavanje zadatka

U ovom zadatku vežbamo rad sa niskom (stringom), prolazak kroz njene znakove pomoću petlje i korišćenje grananja da bismo odredili cenu svakog kupljenog proizvoda.

Zato je dovoljno da prolazimo kroz spisak proizvoda jedan po jedan znak. Kada naiđemo na j, ukupnoj sumi dodajemo cenu jabuke. Kada naiđemo na k, dodajemo cenu kifle, a za l dodajemo cenu lizalice.

Ključna ideja: ne moramo da obrađujemo svaki proizvod posebno. Petljom prolazimo kroz nisku i na osnovu njenog trenutnog znaka prepoznajemo šta je kupljeno.

Primer obračuna

Za spisak:

jjkllkl

potrebno je sabrati:

cena jabuke + cena jabuke + cena kifle
+ cena lizalice + cena lizalice
+ cena kifle + cena lizalice

Za cene 32, 30 i 45 dobijamo:

32 + 32 + 30 + 45 + 45 + 30 + 45 = 259

Pošto spisak ima najviše 30 znakova, jednostavan prolazak kroz celu nisku je sasvim dovoljan.

Uputstvo — ideja rešenja

1. Učitavanje cena

Najpre učitavamo tri cene:

j — cena jabuke
k — cena kifle
l — cena lizalice

Zatim učitavamo nisku proizvodi koja sadrži samo znakove j, k i l.

2. Početna suma

Pre kupovine je potrošeno nula dinara, pa promenljivu za ukupnu cenu postavljamo na:

uk = 0

3. Prolazak kroz nisku

Potrebno je pregledati svaki znak u niskoj. To možemo uraditi petljom for.

Ako koristimo string, znak na poziciji i dobijamo pomoću:

proizvodi[i]

Taj izraz predstavlja jedan znak iz niske.

4. Provera kupljenog proizvoda

Za svaki znak proveravamo tri mogućnosti:

ako je znak j, dodajemo cenu jabuke;
ako je znak k, dodajemo cenu kifle;
ako je znak l, dodajemo cenu lizalice.

5. Zašto koristimo `'j'`, a ne `"j"`?

Izraz proizvodi[i] predstavlja jedan znak, pa ga poredimo sa:

proizvodi[i] == 'j'

Apostrofi ' ' koriste se za jedan znak tipa char, dok se navodnici " " koriste za string.

6. Koliko traje algoritam?

Ako je broj kupljenih proizvoda n, kroz nisku prolazimo samo jednom. Zato je vremenska složenost:

O(n)

Pošto je n ≤ 30, algoritam je veoma brz.

Plan rešenja

Učitaj cene jabuke, kifle i lizalice.
Učitaj nisku sa spiskom proizvoda.
Postavi ukupnu cenu na nulu.
Prođi kroz svaki znak niske.
Za j, k ili l dodaj odgovarajuću cenu.
Ispiši ukupnu cenu.

Rešenje 1 — jednostavnija varijanta

Ovo je preporučena varijanta za učenike. Pošto je proizvodi[i] već jedan znak, nema potrebe da izdvajamo znak pomoću funkcije substr().

C++

#include <iostream>
#include <string>
using namespace std;

int main()
{
    // Cene proizvoda:
    // j - cena jabuke
    // k - cena kifle
    // l - cena lizalice
    int j, k, l;

    // Ukupno potrošen novac.
    int uk = 0;

    // Niska koja sadrži spisak kupljenih proizvoda.
    string proizvodi;

    // Učitavanje cena.
    cin >> j >> k >> l;

    // Učitavanje spiska proizvoda.
    cin >> proizvodi;

    // Prolazimo kroz sve znakove niske.
    for (int i = 0; i < proizvodi.length(); i++)
    {
        // Proveravamo koji proizvod predstavlja trenutni znak.
        if (proizvodi[i] == 'j')
        {
            // Ako je 'j', kupila je jabuku.
            uk += j;
        }
        else if (proizvodi[i] == 'k')
        {
            // Ako je 'k', kupila je kiflu.
            uk += k;
        }
        else if (proizvodi[i] == 'l')
        {
            // Ako je 'l', kupila je lizalicu.
            uk += l;
        }
    }

    // Ispisujemo ukupno potrošen novac.
    cout << uk << endl;

    return 0;
}

Objašnjenje koda

Ključni deo programa je petlja:

for (int i = 0; i < proizvodi.length(); i++)

Njome prolazimo kroz sve pozicije u niskoj. Na svakoj poziciji proveravamo znak:

proizvodi[i]

Na primer, za nisku jkl program redom obrađuje:

proizvodi[0] → 'j'
proizvodi[1] → 'k'
proizvodi[2] → 'l'

Za ulaz:

10
20
30
jkl

program računa:

10 + 20 + 30 = 60

Na kraju se ispisuje:

Rešenje 2 — varijanta sa `substr()`

Ovo je ispravna varijanta rešenja u stilu prvobitnog programa. Ovde se trenutni znak najpre izdvaja iz stringa pomoću funkcije substr(), a zatim se poredi sa "j", "k" i "l".

C++

#include <iostream>
#include <string>
using namespace std;

int main()
{
    // Cene jabuke, kifle i lizalice.
    int j, k, l;

    // Dužina spiska proizvoda i ukupno potrošen novac.
    int duz, uk = 0;

    // Niska sa spiskom proizvoda.
    string proizvodi;

    // String u kome ćemo privremeno čuvati jedan znak.
    string charac;

    // Učitavanje cena.
    cin >> j >> k >> l;

    // Učitavanje spiska proizvoda.
    cin >> proizvodi;

    // Određujemo koliko znakova ima spisak.
    duz = proizvodi.length();

    // Prolazimo kroz sve znakove spiska.
    for (int i = 0; i < duz; i++)
    {
        // Izdvajamo jedan znak kao string dužine 1.
        charac = proizvodi.substr(i, 1);

        // Ako je znak "j", dodajemo cenu jabuke.
        if (charac == "j")
        {
            uk = uk + j;
        }
        // Ako je znak "k", dodajemo cenu kifle.
        else if (charac == "k")
        {
            uk = uk + k;
        }
        // Ako je znak "l", dodajemo cenu lizalice.
        else if (charac == "l")
        {
            uk = uk + l;
        }
    }

    // Ispis ukupno potrošenog novca.
    cout << uk << endl;

    return 0;
}

Objašnjenje druge varijante

Izraz:

proizvodi.substr(i, 1)

znači: počev od pozicije i, izdvoji jedan znak. Dobijeni znak se smešta u promenljivu charac tipa string.

Zato se ovde koriste navodnici:

charac == "j"
charac == "k"
charac == "l"

Za razliku od prve varijante, ovde charac nije tipa char, već string.

Poređenje dve varijante

Prva varijanta:
proizvodi[i] == 'j'

Druga varijanta:
charac = proizvodi.substr(i, 1);
charac == "j"

Obe varijante daju isti rezultat. Prva je kraća i jednostavnija, pa je pogodnija za učenike koji tek uče rad sa stringovima. Druga varijanta je takođe potpuno ispravna i korisna za upoznavanje funkcije substr().

Vremenska složenost

U obe varijante prolazimo kroz sve proizvode najviše jednom, tako da je vremenska složenost O(n), gde je n broj kupljenih proizvoda.

Pošto je najveća dozvoljena dužina spiska samo 30 znakova, obe varijante rade veoma brzo.

ZADATAK 04 2022/2023.

Majstor

1. krug kvalifikacija 6. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje

Postavka zadatka

Nakon izvođenja radova majstoru Peri je vraćeno n kutija sa šrafovima. Kutije su korišćene i mogu sadržati različite brojeve šrafova.

Majstor Pera hoće da koristi dve kutije sa najmanjim brojem šrafova. Pomozite majstoru Peri da izračuna koliko ukupno šrafova ima u tako izabrane dve kutije.

Ulaz

U prvoj liniji standardnog ulaza unosi se ukupan broj kutija n (2 ≤ n ≤ 30). Zatim se u narednih n linija unose brojevi šrafova u kutijama ki (1 ≤ ki ≤ 100), redom.

Izlaz

Na standardni izlaz ispisati ceo broj koji predstavlja zbir šrafova u dve kutije sa najmanje šrafova.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Primer 3

Ulaz

Izlaz

Uputstvo za rešavanje

Zadatak se može rešiti primenom petlji i grananja u programu, ali i pomoću vektora.

Za pristup sa vektorom potrebno je poznavanje oblasti: Dinamički niz — vector.

U vektor treba učitati broj šrafova iz svake kutije, a zatim ga sortirati po rastućem redosledu pomoću funkcije sort iz zaglavlja <algorithm>. Prve dve vrednosti tada predstavljaju najmanje brojeve šrafova.

Otvori rešenje

ZADATAK 05 2022/2023.

Zrak

1. krug kvalifikacija 6. i 7. razred

Izvor zadatka: Originalni link iz postojeće stranice — Petlja

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Ugnježdene petlje u C/C++

Opciono: Dinamički niz — vector

Postavka zadatka

Poznato je da radio-talasima smetaju prepreke koje im se nađu na putu. Potrebno je istražiti da li radiotalasi mogu da prođu kroz pravougaonu oblast u kojoj je zasađeno drveće.

Radio-talas se ispušta iz gornjeg levog ugla te oblasti i to u pravcu koji je određen vertikalnim i horizontalnim pomerajem. To su brojevi koji određuju razliku između koordinata narednog i tekućeg polja koje je zrak dostigao.

Na primer, ako su pomeraji redom 2 i 1, to znači da se zrak u svakom koraku pomeri dve vrste naniže i jednu kolonu nadesno, pa redom prelazi polja čije su koordinate (v, k) jednake (0, 0), (2, 1), (4, 2) itd.

Napiši program koji određuje koliko stabala će se naći na putu radio-talasa.

Ulaz

Prva linija standardnog ulaza sadrži dimenzije matrice bv i bk (3 ≤ bv, bk ≤ 100), razdvojene razmakom. Nakon toga se nalazi opis matrice, pri čemu su polja koja sadrže stabla označena sa 1, a polja koja ne sadrže stabla sa 0. Na kraju se nalazi linija u kojoj su dati pomeraji (prirodni brojevi razdvojeni razmakom).

Izlaz

Na standardni izlaz ispisati broj stabala koje radio-signal poseti.

Primer 1

Ulaz

8 8
0 1 1 0 0 1 0 1
0 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0
1 1 0 1 0 1 0 1
0 1 1 0 1 1 1 0
0 0 0 0 0 1 0 1
1 0 1 1 0 1 1 0
0 1 1 0 1 1 1 0
2 1

Izlaz

Objašnjenje

Na slici su polja kroz koja prolazi zrak označena simbolima - ako na njima nema stabla i X ako se na njima nalazi stablo.

Za pomeraje 2 i 1 zrak posećuje položaje (0, 0), (2, 1), (4, 2) i (6, 3). Dva od tih polja sadrže stabla.

- 1 1 0 0 1 0 1
0 0 1 0 1 0 1 0
1 - 1 0 1 0 1 0
1 1 0 1 0 1 0 1
0 1 X 0 1 1 1 0
0 0 0 0 0 1 0 1
1 0 1 X 0 1 1 0
0 1 1 0 1 1 1 0

Primer 2

Ulaz

8 8
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 2

Izlaz

Uputstvo za rešavanje

Za učitavanje matrice koristiti ugnježdene petlje.

Početi od pozicije (0, 0). Koristeći petlju i proveru da li se nalazimo unutar matrice, prelaziti na nove pozicije prema unetim vrednostima pomeraja po redu i koloni.

Ako je na posećenoj poziciji vrednost u matrici jednaka 1, povećati brojač za 1. Po izlasku iz petlje brojač predstavlja broj posećenih polja na kojima se nalazi stablo.

Otvori rešenje

ZADATAK 06 2022/2023.

Broj dana odmerenog treninga

1. krug kvalifikacija 7. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje

Postavka zadatka

Prilikom pripreme za predstojeća takmičenja, sportista svakog dana meri rezultat koji je postigao. Pošto želi da ravnomerno podiže formu, želi da svaki dan rezultat bude sve bolji (veći broj predstavlja bolji rezultat).

Za neki dan treninga ćemo reći da je dobar ako je rezultat postignut tog dana strogo bolji nego prethodnog, a strogo lošiji nego narednog. Da bi bio dobar, za prvi dan je dovoljno da je strogo lošiji od narednog, a za poslednji dan da je strogo bolji od prethodnog.

Napiši program koji izračunava broj dobrih dana.

Ulaz

Sa standardnog ulaza učitava se broj dana n (3 ≤ n ≤ 100) tokom kojih je sportista trenirao, a u drugom redu rezultati koje je sportista postizao tokom svakog od tih n dana.

Izlaz

Na standardni izlaz ispisati broj dobrih dana.

Primer 1

Ulaz

6
100 120 130 110 140 150

Izlaz

Primer 2

Ulaz

6
10 20 30 40 50 60

Izlaz

ZADATAK 07 2022/2023.

Kuvar

1. krug kvalifikacija 8. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++

Postavka zadatka

Kuvaru je za jednu porciju potrebno m grama mesa za glavno jelo, a za salatu ili k grama kupusa ili c grama cvekle.

Na raspolaganju su M grama mesa, K grama kupusa i C grama cvekle (a svih ostalih sastojaka ima mnogo više).

Napisati program koji učitava potrebne količine za jednu porciju m, k, c, a zatim i raspoložive količine M, K, C, i ispisuje za koliko celih porcija (glavno jelo i salata) kuvar ima dovoljno sastojaka.

Ulaz

Na standardnom ulazu su redom brojevi m, k, c, M, K, C, svaki u posebnom redu. Svi brojevi su celi, pozitivni i manji od 50000.

Izlaz

Na standardni izlaz ispisati samo jedan ceo nenegativan broj, a to je broj celih porcija koje mogu da se pripreme.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Napomena

U originalnom tekstu, oznake za raspoložive količine nisu bile potpuno navedene u rečenici. Ovde su zapisane kao M, K i C, prema redosledu brojeva u ulazu.

Otvori rešenje

ZADATAK 08 2022/2023.

Stubići od kockica

1. krug kvalifikacija 8. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu

Postavka zadatka

Dva druga se igraju kockicama. Od prethodne igre ostala su im dva stuba čije su visine A i B. Sada, za novu građevinu, imaju dve ideje.

Po prvoj ideji potrebni su im stubovi visina A1 i B1, a po drugoj stubovi visina A2 i B2.

Da bi promenio visinu nekog stuba za 1, jednom drugaru potrebno je Tx vremena, a drugom Ty vremena. Za koliko najmanje vremena drugari mogu da preprave (produže ili skrate) postojeće stubove i naprave od njih stubove koji se uklapaju u jednu od ideja, ako svaki od njih prepravlja po jedan stub?

Vreme se meri od trenutka kada drugari istovremeno počnu sa prepravkama do trenutka kada su obojica završila.

Ulaz

U četiri reda standardnog ulaza nalaze se po dva prirodna broja razdvojena razmakom:

u prvom redu su A i B;
u drugom redu su A1 i B1;
u trećem redu su A2 i B2;
u četvrtom redu su Tx i Ty.

Veličine A, B, A1, B1, A2 i B2 pripadaju intervalu [1, 1000000], a Tx i Ty intervalu [1, 100].

Izlaz

Na standardni izlaz ispisati jedan prirodan broj — traženo najmanje vreme.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

ZADATAK 09 2022/2023.

Slovarica

1. krug kvalifikacija 7. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Stringovi u C/C++ jeziku

Postavka zadatka

Ana uči da sastavlja reči od slova. Danas želi da od slova koja ima na raspolaganju sastavi što više primeraka reči koju je smislila.

Napisati program koji određuje koliko puta data reč može da se sastavi od slova date kolekcije.

Ulaz

U prvom redu standardnog ulaza nalazi se niska karaktera koja predstavlja kolekciju, a u drugom niska koja predstavlja reč. Obe niske sastoje se isključivo od malih slova engleske abecede, a njihova dužina je najviše 50000 karaktera.

Izlaz

Na standardni izlaz ispisati jedan ceo broj — broj mogućih sastavljanja date reči.

Primer 1

Ulaz

matematikaiprogramiranje
meta

Izlaz

Primer 2

Ulaz

nekavelikakolekcijaslova
kea

Izlaz

Primer 3

Ulaz

babanedanijevisesedapajenekogleda
deda

Provera nedostajućeg podatka

U dostavljenom HTML-u nije naveden izlaz za ovaj primer. Potrebno je proveriti originalni zadatak pre objavljivanja kompletnog primera.

Uputstvo i rešenje

Otvori rešenje

ZADATAK 10 2022/2023.

Pas Ćuki

1. krug kvalifikacija 7. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Stringovi u C/C++ jeziku

Opciono: Dinamički niz — vector

Postavka zadatka

Pas Ćuki je najpametniji pas na svetu. Pored toga što ume da napravi razne akrobatske trikove, on je i izvrstan programer, pa je izmislio novi programski jezik koji je nazvao Ć++.

Svaka linija programskog koda u jeziku Ć++ sastoji se od tačno m celih brojeva razdvojenih razmacima. Pošto je Ć++ veoma napredan jezik, potrebno ga je prevesti tako da bude razumljiv današnjim računarima.

U procesu prevođenja je u jednom trenutku potrebno da se svaka linija koda transformiše tako da sadrži m istih celih brojeva. Linija se transformiše tako što se svaki broj povećava ili smanjuje za 1 dok se ne dođe do željenog broja, a cena transformacije jednog broja u drugi jednaka je broju povećavanja ili smanjivanja.

Primer transformacije

Recimo da želimo da transformišemo liniju 1 4 9 u 3 3 3.

Broj 1 treba povećati dva puta da bi se dobio broj 3, pa je cena transformacije 2.
Broj 4 treba smanjiti jednom, pa je cena 1.
Broj 9 treba smanjiti šest puta, pa je cena 6.

Ukupna cena transformacije linije je 2 + 1 + 6 = 9.

Kako bi se uštedeli resursi pri prevođenju, potrebno je transformisati kod tako da ukupna cena transformacije bude što manja. Za jednu učitanu liniju potrebno je odrediti u koji će se broj transformisati da bi cena transformacije bila najmanja moguća.

Ako je liniju moguće transformisati u više različitih brojeva tako da cena ostane ista, bira se najveći takav broj.

Ulaz

U prvom redu standardnog ulaza nalazi se prirodan broj m (1 ≤ m ≤ 10⁵) koji označava koliko brojeva se nalazi u liniji koja se učitava.

U narednom redu nalazi se niz od m celih brojeva (između −1000 i 1000) razdvojenih razmacima, koji predstavljaju jednu liniju u Ć++-u.

Dodatna ograničenja

U test primerima vrednim 49 poena dodatno važi m ≤ 100.

Izlaz

U prvom redu standardnog izlaza ispisati jedan broj koji označava u koji će se broj transformisati brojevi u datoj liniji. U drugom redu standardnog izlaza ispisati najmanju cenu transformacije date linije programskog koda.

Primer 1

Ulaz

6
1 8 6 -4 0 7

Izlaz

6
24

Objašnjenje

Najmanja cena transformacije postiže se ako se svi brojevi transformišu u broj 6.

Cena transformacije linije je:

|1 - 6| + |8 - 6| + |6 - 6|
+ |-4 - 6| + |0 - 6| + |7 - 6| = 24

Ista cena dobila bi se i kada bi se linija transformisala u broj 1. Pošto je 6 veći broj, prema uslovu zadatka biramo 6.

Primer 2

Ulaz

7
-5 -4 -3 -2 -1 0 1

Izlaz

-2
12

Uputstvo za rešavanje

ZADATAK 11 2022/2023.

Datum sa najvećom zaradom

1. krug kvalifikacija 8. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Stringovi u C/C++ jeziku

Opciono: Dinamički niz — vector Rečnik podataka — mape u C++

Postavka zadatka

Poznati su svi fiskalni računi koje je izdala jedna knjižara. Sa svakog računa može se pročitati datum kada je račun izdat i iznos koji je naplaćen.

Napiši program koji određuje najveći ukupan iznos koji je knjižara naplatila u jednom danu, odnosno maksimalni dnevni pazar, kao i datum kada je taj iznos bio najveći.

Ako postoji više takvih datuma, ispisati ih sve, uređene hronološki od najstarijeg do najnovijeg.

Ulaz

Sa standardnog ulaza učitava se broj izdatih računa n (1 ≤ n ≤ 10⁵), a zatim podaci o svakom računu u obliku:

dd-mm-gggg iznos

Iznos je realan broj zaokružen na dve decimale.

Izlaz

Na standardni izlaz ispisati maksimalni iznos, kao realan broj zaokružen na dve decimale, a zatim u narednim redovima datume kada je taj maksimalni iznos naplaćen.

Ako ima više datuma, oni treba da budu ispisani redom od najstarijeg do najnovijeg.

Primer

Ulaz

5
03-07-2021 340.00
05-04-2021 285.50
03-07-2021 100.50
04-07-2021 270.00
05-04-2021 155.00

Izlaz

440.50
05-04-2021
03-07-2021

Objašnjenje primera

Za datum 03-07-2021 ukupan pazar iznosi 340,00 + 100,50 = 440,50.

Za datum 05-04-2021 ukupan pazar iznosi 285,50 + 155,00 = 440,50.

To je najveći dnevni pazar. Pošto su oba datuma ostvarila isti iznos, ispisuju se oba, hronološki: prvo 05-04-2021, a zatim 03-07-2021.

Ideja za rešavanje

Potrebno je sabrati iznose svih računa koji imaju isti datum. Zatim među ukupnim dnevnim iznosima pronaći najveći i izdvojiti sve datume koji imaju baš taj iznos.

Za grupisanje se može koristiti mapa (map), u kojoj je datum ključ, a vrednost zbir iznosa za taj dan.

Posebno treba voditi računa o hronološkom redosledu: tekstualni datumi oblika dd-mm-gggg ne mogu se pravilno hronološki poređati običnim leksikografskim sortiranjem.

Dodatno uputstvo

Otvori rešenje

Uputstvo — koraci rešavanja

1. Učitavanje podataka

Učitati broj računa n. Za svaki račun učitati datum i odgovarajući iznos.

2. Sabiranje pazara po datumima

Za svaki učitani račun pronaći datum u mapi i dodati njegov iznos ukupnom pazaru za taj datum. Ako se datum pojavljuje prvi put, formira se nova stavka.

Pošto su iznosi zadati na dve decimale, za potpuno pouzdano poređenje iznosa može se raditi sa celim brojevima koji predstavljaju pare, umesto sa približnim decimalnim vrednostima.

3. Pronalaženje maksimalnog dnevnog pazara

Kada se obrade svi računi, proći kroz ukupne iznose po datumima i pronaći najveću vrednost.

4. Izdvajanje svih datuma

Ponovo pregledati ukupne iznose i izdvojiti svaki datum čiji je pazar jednak pronađenom maksimumu. Nije dovoljno sačuvati samo prvi datum, jer može postojati više dana sa istim maksimalnim iznosom.

5. Hronološko sortiranje

Datume je potrebno poređati po godini, zatim po mesecu i na kraju po danu. Na primer, 05-04-2021 treba da bude pre 03-07-2021.

6. Ispis rezultata

Najpre ispisati maksimalni dnevni pazar na dve decimale, a zatim svaki datum koji je ostvario taj pazar, u hronološkom redosledu.

Česta greška

Ne treba upoređivati pojedinačne račune da bi se našao najveći iznos. Zadatak traži najveći ukupan dnevni pazar, pa prvo moraju da se saberu svi računi istog datuma.

ZADATAK 12 2022/2023.

Zbirovi nakon podele

1. krug kvalifikacija Nizovi i parnost

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Nizovi u C/C++

Opciono: Maksimalna suma podniza

Postavka zadatka

Dat je niz celih brojeva dužine n. Niz je potrebno preseći na dva dela.

Nakon sečenja određuje se koliko postoji parova brojeva takvih da je jedan broj iz levog, a drugi iz desnog dela i da je njihov zbir paran broj.

Odrediti maksimalan broj takvih parova koji je moguće dobiti sečenjem niza.

Ulaz

Sa standardnog ulaza unosi se ceo broj n (2 ≤ n ≤ 50000). Zatim se u narednom redu unose elementi niza a[i] (0 ≤ a[i] ≤ 100), razdvojeni razmakom.

Izlaz

Na standardni izlaz ispisati jedan ceo broj koji predstavlja traženu maksimalnu vrednost.

Primer 1

Ulaz

8
1 7 3 4 6 5 8 0

Izlaz

Objašnjenje

Najveći broj parova dobija se podelom niza na delove:

Levi deo:  1 7 3 4 6
Desni deo: 5 8 0

Parovi čiji je zbir paran su:

(1,5), (7,5), (3,5),
(4,8), (4,0), (6,8), (6,0)

Ukupno postoji 7 parova.

Primer 2

Ulaz

7
1 9 3 11 12 4 8

Izlaz

Objašnjenje

Jedna optimalna podela je:

Levi deo:  1 9
Desni deo: 3 11 12 4 8

Svi brojevi u levom delu su neparni. U desnom delu postoje dva neparna broja, 3 i 11, pa svaki od njih može da formira paran zbir sa oba broja iz levog dela.

Dobijamo 2 × 2 = 4 para.

Ideja za rešavanje

Zbir dva broja je paran ako su oba parna ili su oba neparna. Zato nije potrebno proveravati svaki mogući par brojeva. Dovoljno je brojati parne i neparne elemente sa leve i desne strane preseka.

Za konkretnu podelu broj odgovarajućih parova jednak je:

parni_levo * parni_desno
+ neparni_levo * neparni_desno

Presek se pomera kroz niz, a brojači parnih i neparnih elemenata ažuriraju se prilikom prelaska svakog elementa sa desne na levu stranu.

Dodatno uputstvo

Otvori rešenje

Uputstvo — koraci rešavanja

1. Uoči pravilo parnosti

Zbir je paran u dve situacije:

kada se sabiraju dva parna broja;
kada se sabiraju dva neparna broja.

Zbir parnog i neparnog broja uvek je neparan, pa takve parove ne treba brojati.

2. Prebroj parne i neparne elemente

Na početku se svi elementi nalaze desno od zamišljenog preseka. Prebroj koliko desna strana sadrži parnih, a koliko neparnih brojeva.

Levi deo je u početku prazan. Zatim se presek pomera udesno, element po element.

3. Ažuriraj brojače pri pomeranju preseka

Kada element pređe sa desne na levu stranu, smanji odgovarajući brojač desne strane i povećaj odgovarajući brojač leve strane, u zavisnosti od toga da li je element paran ili neparan.

4. Izračunaj broj parova za svaku podelu

Za svaki dozvoljeni presek izračunaj:

broj_parova =
    parni_levo * parni_desno
    + neparni_levo * neparni_desno

Zapamti najveću dobijenu vrednost. Podela mora imati bar jedan element i sa leve i sa desne strane, pa poslednji element niza ne treba prebaciti u levu stranu i zatim proveravati prazan desni deo.

5. Složenost algoritma

Niz je dovoljno preći konstantan broj puta. Svaki pomeraj preseka zahteva samo nekoliko ažuriranja brojača i jedno izračunavanje, tako da je vremenska složenost O(n).

Česta greška

Nije dovoljno brojati samo parne brojeve ili samo neparne brojeve u celom nizu. Broj parova zavisi od toga koliko parnih i neparnih elemenata ostaje sa svake strane konkretnog preseka.

ZADATAK 13 2022/2023.

Mešalica

3. krug kvalifikacija Permutacije

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Nizovi u C/C++

Opciono: Algoritam brzog stepenovanja

Postavka zadatka

Na raspolaganju nam je mešalica koja može da meša redosled elemenata niza. Mešalica elemente uvek meša na isti način.

Neka je dat niz koji se dobija mešanjem niza 0 1 2 ... n-1. Napiši program koji određuje niz koji se dobija mešanjem niza 0 1 2 ... n-1 ukupno m puta.

Ulaz

Sa standardnog ulaza unose se prirodni brojevi n (1 ≤ n ≤ 50000) i m (0 ≤ m ≤ 10¹⁸), razdvojeni razmakom.

U narednom redu unosi se n različitih brojeva između 0 i n−1, razdvojenih razmakom, koji predstavljaju elemente niza 0 1 2 ... n-1 nakon jednog mešanja.

Izlaz

Na standardni izlaz ispisati n različitih brojeva između 0 i n−1, razdvojenih razmakom, koji predstavljaju elemente početnog niza nakon m mešanja.

Primer 1

Ulaz

4 2
0 2 3 1

Izlaz

0 3 1 2

Objašnjenje

Početni niz je:

0 1 2 3

Prvim mešanjem dobija se:

0 2 3 1

Drugim mešanjem dobija se:

0 3 1 2

Primer 2

Ulaz

5 3
1 2 0 4 3

Izlaz

0 1 2 4 3

Objašnjenje

Početni niz je:

0 1 2 3 4

Posle prvog mešanja:

1 2 0 4 3

Posle drugog mešanja:

2 0 1 3 4

Posle trećeg mešanja:

0 1 2 4 3

Primer 3

Ulaz

4 3
1 0 3 2

Izlaz

1 0 3 2

Objašnjenje

Početni niz je:

0 1 2 3

Prvim mešanjem dobija se:

1 0 3 2

Drugim mešanjem dobija se početni niz:

0 1 2 3

Trećim mešanjem dobija se:

1 0 3 2

Ideja za rešavanje

Kada bismo ponavljali mešanje jedno po jedno, za veoma veliko m algoritam bi bio prespor. Potrebno je iskoristiti činjenicu da mešalica uvek primenjuje istu permutaciju.

Jedna mogućnost je da se permutacija razloži na cikluse. U svakom ciklusu elementi se posle određenog broja mešanja vraćaju na svoje početne pozicije.

Za ciklus dužine k dovoljno je izračunati m % k. Tako se izbegava ponavljanje svih m mešanja i dobija efikasno rešenje i kada je m veoma veliko.

Dodatno uputstvo i video

Otvori rešenje

Uputstvo — kako izbeći ponavljanje mešanja

1. Zašto gruba sila nije dovoljno efikasna?

Jednostavan algoritam ponavlja mešanje tačno m puta. On može biti prihvatljiv za male vrednosti m, ali ne i za vrednosti do 10¹⁸.

2. Posmatraj permutaciju kao cikluse

Svaki element permutacije nakon ponovljenih transformacija prolazi kroz ciklus i na kraju se vraća na početnu poziciju.

Ako je dužina ciklusa k, nakon k koraka element se vraća na odgovarajuću poziciju. Zato broj koraka možemo smanjiti na ostatak pri deljenju broja m sa k.

3. Odredi rezultat za svaki ciklus

Pronađi elemente svakog ciklusa, izračunaj m % k i za svaki element odredi odgovarajuću završnu poziciju nakon tog broja pomeranja.

Potrebno je pažljivo pratiti smer permutacije: da li niz na novoj poziciji preuzima vrednost sa pozicije koju navodi permutacija, ili se element premešta na poziciju koju permutacija označava. Postupak mora biti usklađen sa načinom na koji je permutacija definisana u zadatku.

4. Složenost

Svaki element treba obraditi samo konstantan broj puta. Zbog toga se ciklusima može rešiti zadatak u vremenu O(n), nezavisno od veličine m, uz odgovarajuću reprezentaciju permutacije.

Dodatni materijal

Za opšti princip brzog stepenovanja pogledaj i članak: Algoritam brzog stepenovanja .

Video objašnjenje

ZADATAK 14 2022/2023.

Katanac

2. krug kvalifikacija 7. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje

Postavka zadatka

Katanac za bicikl ima šifru koja se sastoji od četiri cifre. Svaka cifra se postavlja tako što se prsten na kome je ispisano svih deset cifara može vrteti u krug.

Napiši program koji za unetu ispravnu šifru i trenutno namešten kod na katancu određuje najmanji broj okretanja prstenova potrebnih da bi se katanac otključao.

Ulaz

Sa standardnog ulaza učitava se četvorocifrena ispravna šifra, a zatim četvorocifreni broj koji predstavlja početnu poziciju prstenova na katancu. Oba broja mogu počinjati nulama.

Izlaz

Na standardni izlaz ispisati najmanji ukupan broj okretanja prstenova.

Primer 1

Ulaz

1234
7249

Izlaz

Objašnjenje

Prsten sa cifrom 7 okreće se četiri puta unapred da bi se dobila cifra 1.
Prsten sa cifrom 2 ne mora da se okreće.
Prsten sa cifrom 4 okreće se jednom unazad da bi se dobila cifra 3.
Prsten sa cifrom 9 okreće se pet puta da bi se dobila cifra 4, bilo unapred bilo unazad.

Ukupno je potrebno 4 + 0 + 1 + 5 = 10 okretanja.

Primer 2

Ulaz

4812
0319

Izlaz

Ideja za rešavanje

Posmatraj svaku od četiri cifre zasebno. Prsten može da se okreće u dva smera, pa treba izabrati kraći put od trenutne cifre do odgovarajuće cifre šifre.

Ako je razlika dve cifre d, gde je d apsolutna razlika njihovih vrednosti, potrebno je:

min(d, 10 - d)

Zatim se saberu minimalna okretanja za sve četiri pozicije. Važno je sačuvati početne nule, zato šifre treba čitati kao stringove, a ne kao obične cele brojeve.

Dodatno uputstvo

ZADATAK 15 2022/2023.

Tačan izraz

2. krug kvalifikacija 8. razred

Izvor zadatka: Originalna zbirka zadataka na Petlji

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Stringovi Nizovi

Postavka zadatka

U izrazu a_b_c=d umesto donjih crta treba ubaciti dve računske operacije tako da izraz bude tačan.

Računske operacije koje se mogu koristiti su sabiranje (+), oduzimanje (-), množenje (*) i celobrojno deljenje (/). Važe standardni prioriteti računskih operacija.

Ulaz

U svakom od četiri reda standardnog ulaza unosi se po jedan ceo broj: redom a, b, c i d. Svi brojevi su u opsegu [1, 1000].

Izlaz

Na standardni izlaz ispisati sva moguća rešenja, u proizvoljnom redosledu, svako u posebnom redu. Jedno rešenje sastoji se od dva znaka razdvojena razmakom, koji predstavljaju računske operacije koje tim redom treba ubaciti.

Ukoliko nije moguće postići tačan izraz, ispisati nemoguce.

Primer 1

Ulaz

Izlaz

* -
+ /
- /

Objašnjenje

Rešenje * - je tačno jer važi:

2 * 3 - 4 = 2

Rešenje + / je takođe tačno:

2 + 3 / 4 = 2

Ovde je 3 / 4 celobrojno deljenje, pa je njegov rezultat 0. Deljenje ima veći prioritet od sabiranja.

Isto tako, važi:

2 - 3 / 4 = 2

Primer 2

Ulaz

Izlaz

* /

Primer 3

Ulaz

Izlaz

nemoguce

Primer 4

Ulaz

Izlaz

nemoguce

Ideja za rešavanje

Za svako od dva prazna mesta postoje četiri mogućnosti: +, -, * i /. Ukupno zato postoji samo 4 × 4 = 16 kombinacija.

Umesto da pokušavamo da matematički izvedemo operacije, možemo da isprobamo svih 16 parova i proverimo da li izraz daje vrednost d.

Važno je da se izraz izračuna uz standardni prioritet operacija: množenje i deljenje imaju prednost u odnosu na sabiranje i oduzimanje. Operator / predstavlja celobrojno deljenje.

Dodatno uputstvo

Otvori rešenje

ZADATAK 17 2022/2023.

Šljive

2. krug kvalifikacija 6. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje

Postavka zadatka

Janko i Nataša su jeli šljive. Iz činije su uzimali istovremeno: Janko po dve, a Nataša po tri šljive, sve dok je to bilo moguće, odnosno dok nije ostalo manje od pet šljiva. Preostale šljive, ako ih je bilo, pojeo je kasnije Marko.

Napisati program koji učitava početni broj šljiva, a zatim ispisuje koliko je šljiva pojeo svako od njih, kao i broj osoba koje su pojele bar jednu šljivu.

Važno: Janko i Nataša uzimaju šljive sve dok u činiji ima najmanje pet šljiva. U svakom takvom krugu Janko pojede dve, a Nataša tri. Tek kada ostane manje od pet šljiva, preostali deo pojede Marko.

Ulaz

Na standardnom ulazu nalazi se jedan ceo nenegativan broj manji od 51, koji predstavlja početni broj šljiva.

Izlaz

Na standardni izlaz ispisati četiri cela broja, svaki u posebnom redu. Prva tri broja predstavljaju broj šljiva koje su pojeli Janko, Nataša i Marko, tim redom. Četvrti broj predstavlja broj osoba koje su pojele bar jednu šljivu.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Razumevanje i rešavanje zadatka

U ovom zadatku vežbamo korišćenje petlje while, promenljivih i uslova. Potrebno je pratiti koliko šljiva je ostalo i koliko su ih pojeli Janko i Nataša.

U jednom krugu Janko pojede dve šljive, a Nataša tri. Zajedno, dakle, pojedu pet šljiva. Zato petlja treba da se izvršava dok je broj preostalih šljiva veći ili jednak pet.

Ključna ideja: U svakom prolasku kroz petlju Jankov broj povećavamo za 2, Natašin za 3, a broj šljiva koje su ostale u činiji smanjujemo za 5. Kada se petlja završi, ono što je ostalo pripada Marku.

Primer obračuna

Ako na početku imamo 14 šljiva, Janko i Nataša mogu da uzmu po dve, odnosno tri šljive, ukupno dva puta:

14 - 5 = 9
9 - 5 = 4

Janko je pojeo 4 šljive, Nataša 6, a Marko preostale 4 šljive. Pošto su sve tri osobe pojele bar jednu šljivu, poslednji rezultat je 3.

Uputstvo — ideja rešenja

1. Učitavanje broja šljiva

Najpre učitavamo početni broj šljiva i postavljamo brojače za Janka i Natašu na nulu.

int n;
cin >> n;

int janko = 0;
int natasa = 0;

2. Ponavljanje uzimanja šljiva

Petlja se izvršava dok je ostalo najmanje pet šljiva. U svakom krugu Janko uzima dve, Nataša tri, a ukupan broj preostalih šljiva smanjuje se za pet.

while (n >= 5) {
    janko += 2;
    natasa += 3;
    n -= 5;
}

3. Šljive koje je pojeo Marko

Kada se petlja završi, promenljiva n sadrži broj šljiva koji je ostao. Taj broj pripada Marku.

int marko = n;

4. Brojanje osoba koje su jele šljive

Za svaku osobu proveravamo da li je pojela bar jednu šljivu. Ako jeste, povećavamo brojač osoba za jedan.

int brojOsoba = 0;

if (janko > 0) brojOsoba++;
if (natasa > 0) brojOsoba++;
if (marko > 0) brojOsoba++;

5. Ispis rezultata

Rezultati se ispisuju u četiri reda: broj šljiva koje je pojeo Janko, zatim Nataša, Marko, pa broj osoba koje su pojele bar jednu šljivu.

Plan rešenja

Učitaj početni broj šljiva.
Postavi broj šljiva koje su pojeli Janko i Nataša na nulu.
Dok ima najmanje pet šljiva, dodaj 2 Janku i 3 Nataši.
Preostali broj šljiva dodeli Marku.
Prebroj osobe koje su pojele bar jednu šljivu.
Ispiši sva četiri rezultata.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int janko = 0;
    int natasa = 0;

    while (n >= 5) {
        janko += 2;
        natasa += 3;
        n -= 5;
    }

    int marko = n;
    int brojOsoba = 0;

    if (janko > 0) brojOsoba++;
    if (natasa > 0) brojOsoba++;
    if (marko > 0) brojOsoba++;

    cout << janko << '\n';
    cout << natasa << '\n';
    cout << marko << '\n';
    cout << brojOsoba << '\n';

    return 0;
}

Provera graničnog slučaja: Ako je početni broj šljiva manji od pet, petlja se ne izvršava. Janko i Nataša tada ne pojedu nijednu šljivu, a sve šljive pojede Marko. Ako je početni broj šljiva nula, broj osoba koje su jele šljive takođe je nula.

ZADATAK 18 2022/2023.

Flaše

2. krug kvalifikacija 6. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Petlje

Postavka zadatka

Ranko pretače različite vrste tečnosti iz \(n\) punih kanistera različitih zapremina u flaše zapremine \(v\) litara. Za svaki kanister treba odrediti koliko se flaša može potpuno napuniti tečnošću iz tog kanistera i koliko tečnosti će ostati nakon punjenja.

Tečnosti iz različitih kanistera ne smeju se međusobno mešati.

Važno: Svaki kanister se obrađuje zasebno. Ne prenosi se ostatak iz jednog kanistera u drugi, čak ni kada je u pitanju ista vrsta tečnosti.

Ulaz

U prvom redu standardnog ulaza nalaze se dva cela broja: \(n\), broj kanistera, i \(v\), zapremina jedne flaše u litrima. U narednih \(n\) redova nalazi se po jedan ceo broj koji predstavlja zapreminu odgovarajućeg kanistera u litrima. Svi brojevi su celi i između 1 i 10000.

Izlaz

U \(n\) redova ispisati po dva cela broja. Prvi broj predstavlja broj potpuno napunjenih flaša iz odgovarajućeg kanistera, a drugi broj broj litara koji ostaje nakon punjenja flaša.

Primer

Ulaz

Izlaz

Objašnjenje

Prvi kanister sadrži 24 litra. Pošto jedna flaša prima 6 litara, mogu se napuniti četiri flaše i ne ostaje tečnosti. Drugi kanister sadrži 13 litara, pa se mogu napuniti dve flaše i ostaje jedan litar. Ostali kanisteri obrađuju se na isti način.

Razumevanje i rešavanje zadatka

Ovaj zadatak vežba celobrojno deljenje i računanje ostatka pri deljenju. Nisu nam potrebne složene petlje za punjenje svake flaše pojedinačno — količnik i ostatak mogu se izračunati direktno.

Ako kanister sadrži \(k\) litara tečnosti, a jedna flaša ima zapreminu \(v\) litara, broj potpuno napunjenih flaša dobija se celobrojnim deljenjem \(k / v\), dok se preostala količina dobija operatorom \(k \% v\).

Ključna ideja: Operator / daje celobrojni količnik, a operator % daje ostatak pri deljenju. Za svaki kanister dovoljno je izračunati te dve vrednosti i ispisati ih.

Primer računanja

Ako kanister sadrži 17 litara, a zapremina flaše je 6 litara, računamo:

17 / 6 = 2
17 % 6 = 5

Mogu se potpuno napuniti dve flaše, a pet litara tečnosti ostaje u kanisteru.

Uputstvo — ideja rešenja

1. Učitavanje broja kanistera i zapremine flaše

Najpre učitavamo broj kanistera i zapreminu jedne flaše.

int n, v;
cin >> n >> v;

2. Obrada svakog kanistera

Petljom prolazimo kroz svih \(n\) kanistera. U svakom prolasku učitavamo zapreminu trenutnog kanistera.

for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
}

3. Izračunavanje broja punih flaša

Celobrojno deljenje zapremine kanistera zapreminom flaše daje broj potpuno napunjenih flaša.

int brojFlasa = k / v;

4. Izračunavanje ostatka

Operator % vraća ostatak pri deljenju, odnosno broj litara koji ne može da napuni još jednu flašu.

int ostatak = k % v;

5. Ispis rezultata

Za svaki kanister ispisujemo broj punih flaša i ostatak, razdvojene razmakom. Svaki par se ispisuje u posebnom redu.

cout << brojFlasa << ' ' << ostatak << '\n';

Plan rešenja

Učitaj broj kanistera i zapreminu flaše.
Za svaki kanister učitaj njegovu zapreminu.
Izračunaj broj potpuno napunjenih flaša pomoću operatora `/`.
Izračunaj preostalu količinu pomoću operatora `%`.
Ispiši oba rezultata.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n, v;
    cin >> n >> v;

    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;

        int brojFlasa = k / v;
        int ostatak = k % v;

        cout << brojFlasa << ' ' << ostatak << '\n';
    }

    return 0;
}

Zašto je dovoljan jedan prolazak? Svaki kanister je nezavisan, a broj flaša i ostatak mogu se izračunati direktno. Zato svaki kanister obrađujemo jednom, a ukupno vreme izvršavanja raste linearno sa brojem kanistera, odnosno \(O(n)\).

ZADATAK 19 2022/2023.

Fudbalska grupa – tabela

2. krug kvalifikacija 6. razred Nizovi Uslovi

Izvor zadatka: DMS – informatika osnovnih škola

Potrebno predznanje: Podaci u C++ Operatori u C++ Nizovi

Postavka zadatka

Na svetskom prvenstvu u fudbalu svaka grupa sastoji se od četiri ekipe koje igraju svaka sa svakom. U narednu fazu takmičenja plasiraju se dve najbolje plasirane ekipe.

Za svaku pobedu ekipa dobija 3 poena, a za nerešen rezultat svaka ekipa dobija po 1 poen. Napisati program koji na osnovu rezultata šest utakmica određuje broj poena svake ekipe i gol-razliku, odnosno razliku između broja datih i primljenih golova.

Važno: Pobeda donosi 3 poena, nerešen rezultat 1 poen svakoj ekipi, a poraz ne donosi poene. Gol-razlika može biti pozitivna, negativna ili jednaka nuli.

Ulaz

Rezultati utakmica unose se redom: AB, CD, AC, BD, AD, BC. Svaki rezultat sastoji se od dva broja razdvojena razmakom. Prvi broj predstavlja broj golova prve navedene ekipe, a drugi broj golova druge ekipe.

Izlaz

Ispisati broj poena i gol-razliku za ekipe A, B, C i D, tim redom. Za svaku ekipu ispisati po jedan red.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Razumevanje i rešavanje zadatka

Potrebno je pratiti poene i gol-razliku za svaku od četiri ekipe. To možemo da uradimo pomoću dva niza: poeni i golRazlika. Svakom elementu niza odgovara jedna ekipa.

Gol-razlika se uvećava za broj postignutih golova i umanjuje za broj primljenih golova. Poeni se određuju poređenjem rezultata dve ekipe u svakoj utakmici.

Ključna ideja: Za rezultat a b, prva ekipa dobija gol-razliku a - b, a druga b - a. Zatim pobedniku dodajemo 3 poena ili, ako je rezultat nerešen, dodajemo po 1 poen obema ekipama.

Primer računanja gol-razlike

Ako ekipa postigne 2 gola, a primi 5, njena gol-razlika za tu utakmicu iznosi:

2 - 5 = -3

Na kraju se sabiraju gol-razlike iz svih utakmica u kojima je ekipa učestvovala.

Uputstvo — ideja rešenja

1. Čuvanje podataka za ekipe

Ekipama A, B, C i D dodeljujemo indekse 0, 1, 2 i 3. Na početku su broj poena i gol-razlika za svaku ekipu jednaki nuli.

int poeni[4] = {0, 0, 0, 0};
int golRazlika[4] = {0, 0, 0, 0};

2. Određivanje ekipa koje igraju

Utakmice se unose redom AB, CD, AC, BD, AD i BC. Dva niza pamte indekse prve i druge ekipe u svakoj utakmici.

int prvaEkipa[6]  = {0, 2, 0, 1, 0, 1};
int drugaEkipa[6] = {1, 3, 2, 3, 3, 2};

3. Ažuriranje gol-razlike

Ako je učitani rezultat a b, prvoj ekipi dodajemo a - b, a drugoj b - a.

golRazlika[x] += a - b;
golRazlika[y] += b - a;

4. Dodeljivanje poena

Poređenjem broja golova određujemo pobednika. Pobednička ekipa dobija 3 poena, dok u slučaju nerešenog rezultata obe ekipe dobijaju po 1 poen.

if (a > b) {
    poeni[x] += 3;
} else if (a < b) {
    poeni[y] += 3;
} else {
    poeni[x]++;
    poeni[y]++;
}

5. Ispis rezultata

Kada se obrade sve utakmice, ispisujemo poene i gol-razliku za svaku ekipu, redom od A do D.

Plan rešenja:

Inicijalizuj nizove za poene i gol-razliku.
Zapamti redosled ekipa u šest utakmica.
Učitaj rezultat svake utakmice.
Ažuriraj gol-razliku i poene obe ekipe.
Ispiši rezultate za sve četiri ekipe.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int poeni[4] = {0, 0, 0, 0};
    int golRazlika[4] = {0, 0, 0, 0};

    // Redom: AB, CD, AC, BD, AD, BC.
    int prvaEkipa[6]  = {0, 2, 0, 1, 0, 1};
    int drugaEkipa[6] = {1, 3, 2, 3, 3, 2};

    for (int i = 0; i < 6; i++) {
        int a, b;
        cin >> a >> b;

        int x = prvaEkipa[i];
        int y = drugaEkipa[i];

        golRazlika[x] += a - b;
        golRazlika[y] += b - a;

        if (a > b) {
            poeni[x] += 3;
        } else if (a < b) {
            poeni[y] += 3;
        } else {
            poeni[x]++;
            poeni[y]++;
        }
    }

    for (int i = 0; i < 4; i++) {
        cout << poeni[i] << ' '
             << golRazlika[i] << '\n';
    }

    return 0;
}

Zašto koristimo dva niza indeksa? Redosled utakmica je unapred određen. Nizovi prvaEkipa i drugaEkipa omogućavaju da u svakoj iteraciji znamo kojim ekipama pripada učitani rezultat, bez ponavljanja posebnog koda za svaku utakmicu.

ZADATAK 20 2022/2023.

Najviše odličnih

2. krug kvalifikacija 6. razred Nizovi Prebrojavanje

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Nizovi

Postavka zadatka

Napisati program koji za dati razred i uspeh svakog od \(n\) učenika ispisuje broj razreda u kome ima najviše odličnih učenika.

Učenik ima odličan uspeh ako je njegov uspeh veći ili jednak 4,5.

Važno: Ako više razreda ima isti najveći broj odličnih učenika, ispisuje se broj najvećeg razreda.

Ulaz

U prvom redu nalazi se ceo broj \(n\), gde je \(1 \leq n \leq 100\). U svakom od narednih \(n\) redova nalaze se prirodan i realan broj razdvojeni razmakom. Prirodan broj je iz intervala [1, 8] i predstavlja razred, a realan broj je iz intervala [1.0, 5.0] i predstavlja uspeh učenika. Uspeh veći ili jednak 4,5 smatra se odličnim.

Izlaz

Ispisati broj razreda koji ima najviše odličnih učenika. Ako više razreda ima isti najveći broj odličnih učenika, ispisati broj najvećeg takvog razreda.

Primer

Ulaz

Izlaz

Objašnjenje

U 4. razredu ima dva odlična učenika, u 5. razredu jedan, a u 6. razredu dva. Pošto 4. i 6. razred imaju isti najveći broj odličnih učenika, ispisuje se veći broj razreda: 6.

Razumevanje i rešavanje zadatka

Potrebno je prebrojati odlične učenike u svakom razredu. Za to koristimo niz odlicni, u kome odlicni[r] predstavlja broj odličnih učenika u razredu r.

Kada učitamo podatke o učeniku, proveravamo da li je njegov uspeh najmanje 4,5. Ako jeste, povećavamo brojač njegovog razreda. Nakon obrade svih učenika tražimo razred sa najvećim brojem odličnih učenika.

Ključna ideja: Razrede obilazimo od 8 ka 1. Odgovor menjamo samo kada pronađemo strogo veći broj odličnih učenika. Tako u slučaju izjednačenja ostaje izabran veći razred.

Primer prebrojavanja

Ako је učenik iz 6. razreda ostvario uspeh 4,5, on se računa kao odličan jer je njegov uspeh veći ili jednak 4,5.

if (uspeh >= 4.5) {
    odlicni[razred]++;
}

Uputstvo — ideja rešenja

1. Priprema niza brojača

Koristimo niz sa po jednim brojačem za svaki razred. Pošto su razredi označeni brojevima od 1 do 8, niz ima devet elemenata, a indeks 0 ne koristimo.

int odlicni[9] = {0};

2. Učitavanje podataka o učenicima

Za svakog učenika učitavamo razred i uspeh. Uspeh čuvamo u promenljivoj tipa double, jer može biti realan broj.

int razred;
double uspeh;

cin >> razred >> uspeh;

3. Prebrojavanje odličnih učenika

Ako je uspeh najmanje 4,5, uvećavamo brojač odgovarajućeg razreda.

if (uspeh >= 4.5) {
    odlicni[razred]++;
}

4. Pronalaženje razreda sa najviše odličnih

Razrede pregledamo od 8 ka 1. Promenljiva najvise čuva najveći broj odličnih učenika pronađen do tog trenutka, a odgovor broj odgovarajućeg razreda.

int najvise = -1;
int odgovor = 8;

for (int razred = 8; razred >= 1; razred--) {
    if (odlicni[razred] > najvise) {
        najvise = odlicni[razred];
        odgovor = razred;
    }
}

5. Ispis rezultata

Nakon prebrojavanja i pronalaženja maksimuma ispisujemo broj izabranog razreda.

cout << odgovor << '\n';

Plan rešenja:

Postavi sve brojače odličnih učenika na nulu.
Učitaj razred i uspeh svakog učenika.
Prebroj učenike čiji je uspeh najmanje 4,5.
Od 8. do 1. razreda pronađi najveći broj odličnih.
Ispiši broj razreda sa najviše odličnih učenika.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int odlicni[9] = {0};

    for (int i = 0; i < n; i++) {
        int razred;
        double uspeh;

        cin >> razred >> uspeh;

        if (uspeh >= 4.5) {
            odlicni[razred]++;
        }
    }

    int najvise = -1;
    int odgovor = 8;

    for (int razred = 8; razred >= 1; razred--) {
        if (odlicni[razred] > najvise) {
            najvise = odlicni[razred];
            odgovor = razred;
        }
    }

    cout << odgovor << '\n';

    return 0;
}

Zašto razrede obilazimo od 8 ka 1? Kada dva ili više razreda imaju isti najveći broj odličnih učenika, veći razred će biti prvi pronađen. Pošto odgovor menjamo samo kada pronađemo strogo veći broj odličnih, izabrani veći razred ostaje zapamćen.

ZADATAK 21 Nizovi · Petlje

Doline

Nizovi Uzastopni elementi Uslovi

Potrebno predznanje: Nizovi Petlje Grananje u programu

Postavka zadatka

Dat je niz nadmorskih visina nekog terena. Dolina je deo terena sastavljen od jedne ili više uzastopnih jednakih visina, takav da su visina neposredno pre tog dela i visina neposredno posle njega strogo veće od visine dna doline.

Napisati program koji određuje koliko dolina postoji na datom terenu.

Važno: Više uzastopnih jednakih visina koje predstavljaju dno jedne doline računaju se kao jedna dolina. Dno mora imati susede sa obe strane, a obe susedne visine moraju biti strogo veće.

Ulaz

Sa standardnog ulaza unosi se broj delova terena \(n\), gde je \(1 \leq n \leq 150\). U narednom redu unosi se \(n\) celih brojeva razdvojenih razmakom, koji predstavljaju nadmorske visine terena. Sve visine su iz intervala [0, 100].

Izlaz

Ispisati jedan ceo broj koji predstavlja broj dolina.

Primer 1

Ulaz

8
5 3 3 7 4 4 4 8

Izlaz

Objašnjenje

U nizu postoje dve doline. Prvu čine visine 5 3 3 7, a drugu visine 7 4 4 4 8. Njihova dna su na visinama 3 i 4.

Primer 2

Ulaz

5
4 3 1 2 4

Izlaz

Objašnjenje

Jedina dolina je 3 1 2, čije je dno na visini 1.

Primer 3

Ulaz

11
2 2 3 4 4 2 2 2 5 4 5

Izlaz

Objašnjenje

Doline su 5 2 2 2 5 i 5 4 5. U oba slučaja dno je niže od susednih visina.

Razumevanje i rešavanje zadatka

Niz obilazimo sleva nadesno i posmatramo grupe uzastopnih jednakih visina. Svaka grupa predstavlja jedno moguće dno doline. Da bismo utvrdili da li je grupa zaista dolina, proveravamo visinu neposredno levo i neposredno desno od nje.

Ako grupa ima susede sa obe strane i obe susedne visine strogo su veće od visine grupe, broj dolina uvećavamo za jedan. Zatim nastavljamo obilazak od prvog elementa posle te grupe.

Ključna ideja: Najpre pronađi početak i kraj bloka jednakih visina. Zatim proveri da li su visine neposredno uz blok veće od visine dna. Na taj način jedan blok jednakih visina broji se samo jednom.

Primer prepoznavanja doline

U nizu 5 3 3 3 7, sva tri elementa visine 3 čine dno jedne doline. Visina levo od bloka je 5, a desno 7, pa su oba suseda viša od dna.

5 > 3
7 > 3

Uputstvo — ideja rešenja

1. Učitavanje niza

Učitavamo broj elemenata i sve nadmorske visine. Indeksi niza počinju od nule.

int n;
cin >> n;

int a[150];

for (int i = 0; i < n; i++) {
    cin >> a[i];
}

2. Pronalaženje grupe jednakih visina

Indeks i označava početak grupe. Indeks j pomeramo udesno sve dok nailazimo na visine jednake vrednosti a[i].

int j = i;

while (j + 1 < n && a[j + 1] == a[i]) {
    j++;
}

3. Provera da li je grupa dolina

Grupa mora imati element levo i desno od sebe. Pored toga, oba susedna elementa moraju biti strogo veća od visine dna.

if (i > 0 && j < n - 1
    && a[i - 1] > a[i]
    && a[j + 1] > a[i]) {
    brojDolina++;
}

4. Nastavak obilaska

Nakon obrade grupe, prelazimo na prvi element posle nje. Tako istu grupu nećemo obrađivati više puta.

i = j + 1;

5. Ispis broja dolina

Kada obradimo sve grupe, ispisujemo ukupan broj dolina.

cout << brojDolina << '\n';

Plan rešenja:

Učitaj sve nadmorske visine u niz.
Pronađi uzastopne grupe jednakih visina.
Proveri da li svaka grupa ima oba suseda i da li su viši od nje.
Uvećaj broj dolina za svaku grupu koja ispunjava uslove.
Pređi na sledeću grupu i na kraju ispiši rezultat.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int a[150];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int brojDolina = 0;
    int i = 0;

    while (i < n) {
        int j = i;

        // Pronađi kraj grupe jednakih uzastopnih visina.
        while (j + 1 < n && a[j + 1] == a[i]) {
            j++;
        }

        // Grupa je dolina samo ako ima susede sa obe strane
        // i ako su obe susedne visine strogo veće od dna.
        if (i > 0 && j < n - 1
            && a[i - 1] > a[i]
            && a[j + 1] > a[i]) {
            brojDolina++;
        }

        // Nastavi od sledeće grupe.
        i = j + 1;
    }

    cout << brojDolina << '\n';

    return 0;
}

Zašto tražimo ceo blok jednakih visina? U nizu 5 3 3 3 7 sva tri uzastopna elementa visine 3 čine jedno dno doline. Zato najpre nalazimo početak i kraj tog bloka, a tek onda proveravamo njegovu levu i desnu visinu. Svaki takav blok može doprineti rezultatu najviše jednom dolinom.

ZADATAK 22 2022/2023.

Dopuna mejlova

1. krug kvalifikacija 7. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje u programu Petlje Stringovi

Postavka zadatka

Aplikacije za slanje mejlova čuvaju ranije korišćene mejl adrese i pomažu korisnicima tako što na osnovu njih automatski dopunjavaju započeti unos nove adrese.

Napisati program koji efikasno implementira ovu funkcionalnost: za svaki započeti unos određuje koliko sačuvanih mejl adresa počinje unetim tekstom.

Ulaz

Sa standardnog ulaza učitava se broj mejl adresa \(n\), gde je \(1 \leq n \leq 10^5\). U narednih \(n\) redova nalazi se po jedna mejl adresa. Nakon toga učitava se broj upita \(m\), gde je \(1 \leq m \leq 10^5\), a zatim i \(m\) upita. Svaki upit predstavlja započetu mejl adresu.

Izlaz

Za svaki upit ispisati broj sačuvanih mejl adresa koje počinju tim upitom. Svaki rezultat ispisati u posebnom redu.

Primer

Ulaz

9
pera@gmail.com
lidija.djokic@yahoo.com
andrija@yahoo.com
laza@gmail.com
ana.petrovic@mail.ru
lazica@hotmail.com
milica@gmail.com
larisa@zoho.com
anaconda@python.org
3
laz
milica@
a

Izlaz

2
1
3

Objašnjenje

Upit laz odgovara adresama laza@gmail.com i lazica@hotmail.com. Upit milica@ odgovara jednoj adresi, a slovom a počinju tri adrese.

Razumevanje i rešavanje zadatka

Kada ima mnogo adresa i upita, nije efikasno za svaki upit ponovo prolaziti kroz sve sačuvane mejlove. Umesto toga možemo koristiti prefiksno stablo, poznato kao trie.

Prilikom dodavanja adrese prolazimo kroz njene karaktere i povećavamo brojač svakog posećenog čvora. Kada stigne upit, pratimo odgovarajuće grane stabla. Brojač poslednjeg čvora predstavlja broj adresa koje počinju unetim tekstom.

Ključna ideja: Svaki čvor pamti koliko sačuvanih adresa prolazi kroz njega. Ako neki karakter upita nema odgovarajuću granu, nijedna adresa ne počinje tim upitom, pa je odgovor nula.

Primer rada sa prefiksom

Adrese laza@gmail.com i lazica@hotmail.com obe počinju tekstom laz. Brojač čvora koji predstavlja prefiks laz zato ima vrednost 2.

Uputstvo — ideja rešenja

1. Predstavljanje čvora

Svaki čvor sadrži mapu koja povezuje karakter sa sledećim čvorom i brojač koji čuva broj adresa koje prolaze kroz njega.

struct Cvor {
    unordered_map<char, int> sledeci;
    int broj = 0;
};

2. Dodavanje mejl adrese

Počinje se od korena stabla. Za svaki karakter adrese proverava se da li odgovarajuća grana već postoji. Ako ne postoji, pravi se novi čvor. Brojač čvora u koji smo stigli uvećava se za jedan.

3. Obrada upita

Za svaki upit ponovo počinjemo od korena. Pratimo grane koje odgovaraju karakterima upita. Ako neka grana nedostaje, rezultat je nula. Ako prođemo kroz ceo upit, rezultat je brojač poslednjeg posećenog čvora.

4. Efikasnost

Izgradnja stabla zavisi od ukupnog broja karaktera u svim mejl adresama. Obrada svakog upita zavisi od dužine tog upita, a ne od ukupnog broja sačuvanih adresa.

Plan rešenja:

Napravi koren prefiksnog stabla.
Ubaci sve mejl adrese i ažuriraj brojače čvorova.
Za svaki upit prati odgovarajuće grane.
Ispiši brojač pronađenog čvora ili nulu ako grana nedostaje.

C++ rešenje

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

struct Cvor {
    unordered_map<char, int> sledeci;
    int broj = 0;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Cvor> trie(1);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string adresa;
        cin >> adresa;

        int cvor = 0;

        for (char znak : adresa) {
            auto it = trie[cvor].sledeci.find(znak);

            if (it == trie[cvor].sledeci.end()) {
                int novi = (int)trie.size();
                trie[cvor].sledeci[znak] = novi;
                trie.emplace_back();
                cvor = novi;
            } else {
                cvor = it->second;
            }

            trie[cvor].broj++;
        }
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        string upit;
        cin >> upit;

        int cvor = 0;
        bool postoji = true;

        for (char znak : upit) {
            auto it = trie[cvor].sledeci.find(znak);

            if (it == trie[cvor].sledeci.end()) {
                postoji = false;
                break;
            }

            cvor = it->second;
        }

        if (postoji) {
            cout << trie[cvor].broj << '\n';
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}

Zašto je ovo efikasno? Nakon izgradnje stabla, za odgovor na upit dovoljno je proći kroz njegove karaktere. Ne moramo ponovo da proveravamo sve sačuvane mejl adrese.

ZADATAK 23 2022/2023.

Note

1. krug kvalifikacija 8. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje Petlje Stringovi Nizovi

Postavka zadatka

Tonovi se u muzici ređaju po oktavama. U jednoj oktavi imamo sedam osnovnih tonova: C, D, E, F, G, A i H, kao i pet povišenih tonova koji se nalaze između pojedinih osnovnih tonova.

Dogovaramo se da sve međutonove zapisujemo kao povišene, pomoću oznake #. Redosled tonova je:

C, C#, D, D#, E, F, F#, G, G#, A, A#, H

Posle tona H ponovo dolazi C. Transponovanje melodije znači pomeranje svakog tona za određeni broj mesta unapred ili unazad u ovom cikličnom redosledu.

Napisati program koji transponuje unetu melodiju za zadati broj tonova.

Ulaz

U prvom redu nalazi se niska dužine najviše 1000 karaktera koja predstavlja melodiju. Tonovi su zapisani jedan za drugim, bez razmaka. Nakon toga unosi se ceo broj između -11 i 11 koji predstavlja broj mesta za transponovanje. Pozitivan broj označava pomeranje unapred, a negativan unazad.

Izlaz

Ispisati transponovanu melodiju, bez razmaka između tonova.

Primer 1

Ulaz

GDGHDCAF#D
5

Izlaz

CGCEGFDHG

Objašnjenje

Pomeranjem tona G za pet mesta dobija se C, jer se nakon H vraćamo na C. Na isti način D prelazi u G, a F# u H.

Primer 2

Ulaz

C#F#AG
-3

Izlaz

A#D#F#E

Razumevanje i rešavanje zadatka

Potrebno je svakom tonu dodeliti indeks u nizu od 12 tonova. Kada pronađemo indeks tona, dodamo mu broj mesta za transponovanje i dobijemo indeks novog tona.

Pošto se tonovi ponavljaju ciklično, indeks mora ostati u opsegu od 0 do 11. To postižemo ostatkom pri deljenju sa 12. Posebno treba voditi računa o negativnom pomeranju, jer u C++ ostatak negativnog broja može biti negativan.

Ključna ideja: Tonovi se čuvaju u nizu redosledom kojim se pojavljuju. Svaki ton prvo prepoznajemo u ulaznoj melodiji, a zatim njegov indeks pomeramo ciklično. Ton sa oznakom # predstavlja jedan ton, pa se njegovi karakteri obrađuju zajedno.

Primer pomeranja

Ako je indeks tona G jednak 7, a pomeraj je 5, novi indeks je:

(7 + 5) % 12 = 0

Indeks 0 odgovara tonu C, pa G transponovan pet mesta unapred postaje C.

Uputstvo — ideja rešenja

1. Čuvanje tonova

U niz smeštamo svih 12 tonova redosledom kojim se pojavljuju u oktavi.

string tonovi[12] = {
    "C", "C#", "D", "D#", "E", "F",
    "F#", "G", "G#", "A", "A#", "H"
};

2. Prepoznavanje tona u melodiji

Čitamo melodiju sleva nadesno. Svaki ton počinje jednim karakterom. Ako je sledeći karakter znak #, dodajemo ga istom tonu i pomeramo indeks preko oba karaktera.

3. Pronalaženje indeksa

Poređenjem pročitanog tona sa elementima niza pronalazimo njegov indeks.

int pozicija = 0;

while (pozicija < 12 && tonovi[pozicija] != ton) {
    pozicija++;
}

4. Transponovanje

Na indeks dodajemo pomeraj. Ako je rezultat negativan, dodajemo 12 kako bismo ga vratili u dozvoljeni opseg.

int novaPozicija = (pozicija + pomeraj) % 12;

if (novaPozicija < 0) {
    novaPozicija += 12;
}

5. Ispis

Ispisujemo ton koji se nalazi na novom indeksu, a zatim nastavljamo sa sledećim tonom melodije.

Plan rešenja:

Učitaj melodiju i pomeraj.
Sačuvaj niz svih 12 tonova.
Pročitaj svaki ton, uključujući znak # ako postoji.
Pronađi indeks i izračunaj novi indeks uz ciklično pomeranje.
Ispiši novi ton i nastavi kroz melodiju.

C++ rešenje

#include <iostream>
#include <string>
using namespace std;

int main() {
    string melodija;
    int pomeraj;

    cin >> melodija;
    cin >> pomeraj;

    string tonovi[12] = {
        "C", "C#", "D", "D#", "E", "F",
        "F#", "G", "G#", "A", "A#", "H"
    };

    for (int i = 0; i < (int)melodija.size(); i++) {
        string ton;
        ton += melodija[i];

        // Ako je sledeći karakter #, deo je istog tona.
        if (i + 1 < (int)melodija.size()
            && melodija[i + 1] == '#') {
            ton += '#';
            i++;
        }

        int pozicija = 0;

        while (pozicija < 12 && tonovi[pozicija] != ton) {
            pozicija++;
        }

        int novaPozicija = (pozicija + pomeraj) % 12;

        if (novaPozicija < 0) {
            novaPozicija += 12;
        }

        cout << tonovi[novaPozicija];
    }

    cout << '\n';
    return 0;
}

Važno: Ne možemo svaki karakter tretirati kao poseban ton jer je, na primer, C# jedan ton. Takođe, pri negativnom pomeranju treba ispraviti negativan rezultat operatora % u C++.

Otvori originalno rešenje

ZADATAK 24 2022/2023.

Greška u tekstu

2. krug kvalifikacija 7. i 8. razred

Izvor zadatka: takprog.petlja.org — originalna zbirka zadataka

Potrebno predznanje: Podaci u C++ Operatori u C++ Grananje Petlje Stringovi Nizovi

Postavka zadatka

Poruka od četiri velika slova poslata je tri puta. Svaki put je, zbog smetnji tokom prenosa, tačno jedan karakter poruke pogrešno prenesen kao neko drugo veliko slovo.

Napisati program koji na osnovu tri primljene poruke rekonstruiše originalnu poruku. Rekonstruisana poruka ima četiri karaktera. Na pozicijama na kojima se originalno slovo može sa sigurnošću odrediti ispisuje se to slovo, a na ostalim pozicijama zvezdica (*).

Ulaz

U svakom od tri reda standardnog ulaza nalazi se po četiri velika slova engleske abecede.

Izlaz

U jednom redu ispisati četiri karaktera rekonstruisane poruke. Ako se originalni karakter na određenoj poziciji ne može jednoznačno odrediti, na toj poziciji ispisati zvezdicu.

Primer 1

Ulaz

AXCD
ABYD
ABCZ

Izlaz

ABCD

Primer 2

Ulaz

AXCD
AYCD
AZCD

Izlaz

A*CD

Razumevanje i rešavanje zadatka

Originalna poruka ima samo četiri slova, pa možemo da isprobamo sve moguće poruke sastavljene od velikih slova engleske abecede. Takvih poruka ima \(26^4 = 456976\).

Kandidat prihvatamo samo ako se od svake od tri primljene poruke razlikuje na tačno jednoj poziciji. Nakon što pronađemo sve kandidate koji ispunjavaju taj uslov, upoređujemo njihova slova po pozicijama.

Ključna ideja: Ako je slovo na određenoj poziciji isto u svim prihvaćenim kandidatima, to slovo možemo pouzdano da ispišemo. Ako se kandidati na toj poziciji razlikuju, ispisujemo zvezdicu.

Primer zaključivanja

U primeru 2, sve tri poruke počinju slovom A, a završavaju se sa CD. Drugo slovo je različito: X, Y i Z. Zato su prva, treća i četvrta pozicija poznate, dok se na drugoj ispisuje zvezdica.

Uputstvo — ideja rešenja

1. Učitavanje poruka

Učitavamo tri primljene poruke. Svaka je predstavljena niskom od četiri velika slova.

string poruke[3];

for (int i = 0; i < 3; i++) {
    cin >> poruke[i];
}

2. Generisanje mogućih poruka

Svaki od četiri karaktera može biti bilo koje veliko slovo od A do Z. Četiri ugnježdene petlje omogućavaju da isprobamo sve moguće kombinacije.

3. Provera kandidata

Za svakog kandidata upoređujemo njegove karaktere sa karakterima svake primljene poruke. Kandidat je ispravan samo ako se od svake poruke razlikuje na tačno jednoj poziciji.

int razlike = 0;

for (int j = 0; j < 4; j++) {
    if (kandidat[j] != poruke[i][j]) {
        razlike++;
    }
}

if (razlike != 1) {
    ispravan = false;
}

4. Poređenje prihvaćenih kandidata

Prvog prihvaćenog kandidata čuvamo kao početnu poruku. Za svaki naredni kandidat proveravamo da li se slova na istim pozicijama poklapaju. Ako se neko slovo razlikuje, na toj poziciji označavamo da odgovor nije jednoznačan.

5. Sastavljanje odgovora

Na kraju za svaku poziciju ispisujemo zajedničko slovo ako je isto u svim kandidatima, a u suprotnom zvezdicu.

Plan rešenja:

Učitaj tri primljene poruke.
Generiši sve poruke od četiri slova.
Prihvati samo kandidate koji imaju tačno jednu razliku u odnosu na svaku poruku.
Uporedi sve prihvaćene kandidate po pozicijama.
Ispiši zajedničko slovo ili zvezdicu za svaku poziciju.

C++ rešenje

#include <iostream>
#include <string>
using namespace std;

int main() {
    string poruke[3];

    for (int i = 0; i < 3; i++) {
        cin >> poruke[i];
    }

    string zajednicko;
    bool isto[4] = {true, true, true, true};
    bool pronadjen = false;

    for (char a = 'A'; a <= 'Z'; a++) {
        for (char b = 'A'; b <= 'Z'; b++) {
            for (char c = 'A'; c <= 'Z'; c++) {
                for (char d = 'A'; d <= 'Z'; d++) {
                    string kandidat;
                    kandidat += a;
                    kandidat += b;
                    kandidat += c;
                    kandidat += d;

                    bool ispravan = true;

                    for (int i = 0; i < 3; i++) {
                        int razlike = 0;

                        for (int j = 0; j < 4; j++) {
                            if (kandidat[j] != poruke[i][j]) {
                                razlike++;
                            }
                        }

                        if (razlike != 1) {
                            ispravan = false;
                            break;
                        }
                    }

                    if (ispravan) {
                        if (!pronadjen) {
                            zajednicko = kandidat;
                            pronadjen = true;
                        } else {
                            for (int j = 0; j < 4; j++) {
                                if (zajednicko[j] != kandidat[j]) {
                                    isto[j] = false;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    if (!pronadjen) {
        cout << "****\n";
        return 0;
    }

    for (int i = 0; i < 4; i++) {
        if (isto[i]) {
            cout << zajednicko[i];
        } else {
            cout << '*';
        }
    }

    cout << '\n';
    return 0;
}

Zašto proveravamo celu poruku? Uslov se odnosi na svaku primljenu poruku zasebno: u svakoj mora postojati tačno jedna greška. Samo biranje najčešćeg slova na svakoj poziciji ne mora zadovoljiti ovaj uslov.

ZADATAK 25 2022/23. · 8. razred

Broj trocifrenih parnih

Nizovi Cifre Brojanje

Napomena: Zadatak sa 2. kruga kvalifikacija, sezona 2022/23, za 8. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje i Nizovi.

Opciono: Dinamički niz – vector.

Napisati program koji za dati niz cifara ispisuje broj različitih trocifrenih parnih brojeva koji se mogu sastaviti od datih cifara.

Prilikom formiranja svakog broja, svaki element ulaznog niza može se upotrebiti najviše jednom. Brojevi sa istim ciframa na istim pozicijama računaju se samo jednom, čak i ako se do njih može doći izborom različitih elemenata niza.

Ulaz

U prvom redu nalazi se broj cifara N, gde je 3 ≤ N ≤ 50000. U drugom redu nalazi se N cifara razdvojenih razmacima. Svaka ulazna vrednost predstavlja cifru od 0 do 9.

Izlaz

Ispisati jedan ceo broj — broj različitih trocifrenih parnih brojeva koji se mogu sastaviti.

Primer 1

Ulaz

4
2 4 2 2

Izlaz

Mogući brojevi su 222, 224, 242 i 422.

Primer 2

Ulaz

3
0 1 0

Izlaz

Jedini mogući trocifreni paran broj je 100. Broj koji počinje nulom ne smatra se trocifrenim brojem.

Primer 3

Ulaz

3
4 1 2

Izlaz

Mogući brojevi su 124, 142, 214 i 412.

Ideja za rešavanje: Prebroj pojavljivanja svake cifre od 0 do 9. Zatim isprobaj sve kombinacije cifara stotina, desetica i jedinica. Cifra stotina ne sme biti nula, a cifra jedinica mora biti parna. Za svaku kombinaciju proveri da li u ulaznom nizu postoji dovoljan broj pojavljivanja svake cifre.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int frekvencija[10] = {};

    for (int i = 0; i < n; i++) {
        int cifra;
        cin >> cifra;
        frekvencija[cifra]++;
    }

    int broj = 0;

    for (int stotine = 1; stotine <= 9; stotine++) {
        for (int desetice = 0; desetice <= 9; desetice++) {
            for (int jedinice = 0; jedinice <= 8; jedinice += 2) {
                int potrebno[10] = {};

                potrebno[stotine]++;
                potrebno[desetice]++;
                potrebno[jedinice]++;

                bool moguce = true;

                for (int cifra = 0; cifra <= 9; cifra++) {
                    if (potrebno[cifra] > frekvencija[cifra]) {
                        moguce = false;
                        break;
                    }
                }

                if (moguce) {
                    broj++;
                }
            }
        }
    }

    cout << broj << '\n';
    return 0;
}

Svaka kombinacija cifara predstavlja tačno jedan broj, pa se nijedan broj ne broji više puta. Niz potrebno proverava i slučajeve u kojima se ista cifra pojavljuje na dve ili tri pozicije.

ZADATAK 26 2022/23. · 8. razred

Puž

Matrice Spiralno kretanje Stringovi

Napomena: Zadatak sa 2. kruga kvalifikacija, sezona 2022/23, za 8. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje, Stringovi i Nizovi.

Opciono: Dinamički niz – vector.

Nemanja ima šest godina i počeo je da uči da čita i piše. Od strica je dobio vežbanku za učenje slova sa vežbom koja se zove „Puž”. U vežbi je potrebno popuniti tabelu dimenzija n × m slovima zadate rečenice.

Popunjavanje počinje u gornjem levom uglu. Slova se upisuju nadesno do ivice tabele, zatim naniže, potom ulevo, pa nagore. Kada se dođe do granice popunjenog dela, nastavlja se istim kružnim postupkom kroz unutrašnjost tabele dok se sva polja ne popune.

U tabelu se upisuju samo slova; razmaci, znaci interpunkcije i ostali znakovi se ignorišu. Tabelu je popunio stric, a Nemanju zanima da li se u rečenici koja je korišćena za popunjavanje nalazi ime njegovog omiljenog superheroja.

Napisati program koji rekonstruiše nisku dobijenu čitanjem tabele po istoj spiralnoj putanji, a zatim u njoj traži ime superheroja.

Tabela sa slovima popunjenim spiralnim redosledom

Ulaz

U prvom redu nalaze se dva cela broja n i m, gde je 2 ≤ n, m ≤ 50. Oni predstavljaju broj redova i broj kolona tabele.

U narednih n redova nalazi se po m malih slova engleske abecede koja predstavljaju popunjenu tabelu. U poslednjem redu nalazi se ime superheroja koje tražimo — niska dužine najviše 30 znakova, sastavljena od malih slova engleske abecede.

Izlaz

Ispisati poziciju u rekonstruisanoj rečenici na kojoj počinje ime superheroja. Pozicije se broje od 1. Ako se ime ne pojavljuje, ispisati -1. Ako se pojavljuje više puta, ispisati poziciju njegovog prvog pojavljivanja.

Primer 1

Ulaz

4 5
mnogo
jdrmv
aaneo
psmil
spajdrmen

Izlaz

Čitanjem tabele spiralnim redosledom dobija se niska mnogovolimspajdrmena. Ime spajdrmen počinje na 11. poziciji.

Primer 2

Ulaz

5 5
dalis
rnuui
ccudt
oivoi
adelg
crnaudovica

Izlaz

-1

Rekonstruisana niska ne sadrži crnaudovica. Tražena niska se ne pojavljuje u tekstu.

Ideja za rešavanje: Čuvaj granice nepročitanog dela tabele: gornji red, donji red, levu kolonu i desnu kolonu. U svakoj iteraciji pročitaj gornji red sleva nadesno, desnu kolonu odozgo nadole, donji red zdesna nalevo i levu kolonu odozdo nagore. Proveri da se granice nisu preklopile, kako nijedno polje ne bi bilo pročitano dva puta. Na kraju upotrebi find da pronađeš ime superheroja.

C++ rešenje

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> tabela(n);

    for (int i = 0; i < n; i++) {
        cin >> tabela[i];
    }

    string superhero;
    cin >> superhero;

    string tekst;

    int gore = 0;
    int dole = n - 1;
    int levo = 0;
    int desno = m - 1;

    while (gore <= dole && levo <= desno) {
        for (int j = levo; j <= desno; j++) {
            tekst += tabela[gore][j];
        }
        gore++;

        for (int i = gore; i <= dole; i++) {
            tekst += tabela[i][desno];
        }
        desno--;

        if (gore <= dole) {
            for (int j = desno; j >= levo; j--) {
                tekst += tabela[dole][j];
            }
            dole--;
        }

        if (levo <= desno) {
            for (int i = dole; i >= gore; i--) {
                tekst += tabela[i][levo];
            }
            levo++;
        }
    }

    size_t pozicija = tekst.find(superhero);

    if (pozicija == string::npos) {
        cout << -1 << '\n';
    } else {
        cout << pozicija + 1 << '\n';
    }

    return 0;
}

Funkcija find vraća poziciju koja počinje od nule, dok se u zadatku pozicije broje od 1. Zato na pronađenu poziciju dodajemo 1. Provere granica sprečavaju da se polja ponovo pročitaju kada ostane samo jedan red ili jedna kolona.

ZADATAK 27 2022/23. · 8. razred

Najmanji dobitak

Nizovi Sortiranje Efikasnost

Napomena: Zadatak sa 2. kruga kvalifikacija, sezona 2022/23, za 8. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje, Nizovi i Sortiranje.

Zamislimo ogromnu matricu popunjenu nulama. Svakim potezom (aᵢ, bᵢ, cᵢ), svi elementi u prvih aᵢ redova i prvih bᵢ kolona matrice povećavaju se za cᵢ.

Potrebno je odrediti najmanju pozitivnu vrednost koja se nalazi u matrici nakon svih n poteza.

Ulaz

U prvom redu standardnog ulaza nalazi se broj poteza n (1 ≤ n ≤ 50000). U svakom od narednih n redova nalaze se po tri prirodna broja aᵢ, bᵢ i cᵢ, razdvojena razmacima. Vrednosti aᵢ i bᵢ nisu veće od milijardu, a zbir svih cᵢ ne prelazi dve milijarde.

Smatrati da matrica ima više od milijardu redova i više od milijardu kolona.

Izlaz

Ispisati jedan ceo broj — najmanju pozitivnu vrednost u matrici.

Primer 1

Ulaz

Izlaz

Nakon sva četiri poteza, matrica počinje ovako:

5 5 4 3 3 0 0 ...
4 4 4 3 3 0 0 ...
3 3 3 3 3 0 0 ...
3 3 3 3 3 0 0 ...
0 0 0 0 0 0 0 ...
...

Najmanja pozitivna vrednost u matrici je 3.

Primer 2

Ulaz

2
3 7 3
4 5 2

Izlaz

Nakon oba poteza, matrica počinje ovako:

5 5 5 5 5 3 3 0 0 ...
5 5 5 5 5 3 3 0 0 ...
5 5 5 5 5 3 3 0 0 ...
2 2 2 2 2 0 0 0 0 ...
0 0 0 0 0 0 0 0 0 ...
...

Najmanja pozitivna vrednost u matrici je 2.

Ideja za rešavanje: Potez (aᵢ, bᵢ, cᵢ) utiče na polja čiji su redni broj najviše aᵢ i broj kolone najviše bᵢ. Zato vrednost u polju (aᵢ, bᵢ) predstavlja zbir svih cⱼ za koje važi aⱼ ≥ aᵢ i bⱼ ≥ bᵢ. Dovoljno je izračunati takav zbir za svaki potez i uzeti najmanji. Sortiranjem po aᵢ i Fenwickovim stablom za zbirove po bᵢ, svi potrebni zbirovi mogu se izračunati za O(n log n).

C++ rešenje

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

struct Potez {
    ll a, b, c;
};

struct Fenwick {
    int n;
    vector<ll> stablo;

    Fenwick(int velicina) {
        n = velicina;
        stablo.assign(n + 1, 0);
    }

    void dodaj(int i, ll vrednost) {
        while (i <= n) {
            stablo[i] += vrednost;
            i += i & -i;
        }
    }

    ll zbir(int i) {
        ll rezultat = 0;

        while (i > 0) {
            rezultat += stablo[i];
            i -= i & -i;
        }

        return rezultat;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Potez> potezi(n);
    vector<ll> kolone;

    for (int i = 0; i < n; i++) {
        cin >> potezi[i].a >> potezi[i].b >> potezi[i].c;
        kolone.push_back(potezi[i].b);
    }

    sort(kolone.begin(), kolone.end());
    kolone.erase(unique(kolone.begin(), kolone.end()), kolone.end());

    // Veći a obrađujemo pre manjeg a.
    sort(potezi.begin(), potezi.end(),
         [](const Potez& x, const Potez& y) {
             return x.a > y.a;
         });

    Fenwick fw((int)kolone.size());
    ll odgovor = (1LL << 62);

    int pocetak = 0;

    while (pocetak < n) {
        int kraj = pocetak;

        while (kraj < n &&
               potezi[kraj].a == potezi[pocetak].a) {
            kraj++;
        }

        // Prvo dodaj sve poteze sa istim a.
        for (int i = pocetak; i < kraj; i++) {
            int pozicija = lower_bound(
                kolone.begin(), kolone.end(), potezi[i].b
            ) - kolone.begin();

            // Obrnuti indeks: veće b odgovara manjem indeksu.
            int indeks = (int)kolone.size() - pozicija;
            fw.dodaj(indeks, potezi[i].c);
        }

        // Upit obuhvata sve poteze sa a_j >= a_i i b_j >= b_i.
        for (int i = pocetak; i < kraj; i++) {
            int pozicija = lower_bound(
                kolone.begin(), kolone.end(), potezi[i].b
            ) - kolone.begin();

            int indeks = (int)kolone.size() - pozicija;
            ll vrednost = fw.zbir(indeks);

            odgovor = min(odgovor, vrednost);
        }

        pocetak = kraj;
    }

    cout << odgovor << '\n';
    return 0;
}

Zašto proveravamo samo polja (aᵢ, bᵢ)? Svako polje koje ima pozitivnu vrednost pokriveno je bar jednim potezom, recimo potezom i. To polje ima redni broj reda najviše aᵢ i broj kolone najviše bᵢ. U polju (aᵢ, bᵢ) može biti manje poteza koji doprinose zbiru, ali će potez i i dalje doprinositi. Zato vrednost u polju (aᵢ, bᵢ) nije veća od vrednosti u proizvoljnom polju koje pokriva potez i. Prema tome, minimum među poljima (aᵢ, bᵢ) jednak je najmanjoj pozitivnoj vrednosti u celoj matrici.

Složenost: O(n log n) vremenski i O(n) memorijski.

ZADATAK 28 2022/23. · 7. razred

Seča drva

Matrice Prefiksni zbirovi Optimizacija

Napomena: Zadatak sa 3. kruga kvalifikacija, sezona 2022/23, za 7. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje i Nizovi.

Opciono: Dinamički niz – vector.

Ana i Biljana pripremaju drva za ogrev za zimu. Ana je nasekla komade drveta raznih oblika i istovarila ih na traku. Traka pomera drva ka testeri koja ih seče na dva dela. Testera se postavlja na jednu od dozvoljenih pozicija, a tokom sečenja ne može da se pomera.

Kada se sečenje završi, Ana uzima sve drvo koje je palo sa jedne strane testere, a Biljana sve sa druge. Žele da postave testeru tako da se količine drveta koje dobiju što manje razlikuju.

Mašina je zabeležila oblik svakog komada drveta matricom dimenzije k × k. Vrednost 1 označava deo na kome postoji drvo, a 0 prazno polje. Testera se može postaviti na pozicije 0, 1, 2, ..., k.

Napisati program koji za zadate oblike drveta određuje najmanju moguću apsolutnu razliku između količina drveta koje Ana i Biljana dobiju.

Primer oblika drveta za zadatak Seča drva — Primer oblika drveta

Ulaz

U prvom redu nalazi se prirodan broj n, broj komada drveta, gde je n ≤ 10⁷. U drugom redu nalazi se prirodan broj k, najveća dimenzija matrice, gde je k ≤ 10⁷.

Zatim se unosi n matrica dimenzije k × k. Svaka matrica sastoji se od k redova sa po k brojeva: 0 ako na tom mestu nema drveta ili 1 ako ga ima. U svim test primerima važi n · k · k ≤ 10⁷.

Izlaz

Ispisati najmanju moguću apsolutnu razliku između količina drveta koje Ana i Biljana dobiju.

Primer 1

Ulaz

Izlaz

Ovo je primer iz teksta zadatka.

Primer 2

Ulaz

Izlaz

Razlika 8 postiže se ako se testera postavi na poziciju 1 ili na poziciju 2.

Primer 3

Ulaz

Izlaz

Razlika 2 postiže se ako se testera postavi na poziciju 3.

Ideja za rešavanje: Nije potrebno čuvati sve matrice. Za svaki red matrice prebroj jedinice i dodaj ih zbiru tog reda. Kada obradiš sve komade drveta, zbir prvih p redova predstavlja količinu drveta sa jedne strane testere postavljene na poziciju p. Ukupna količina drveta umanjena za taj zbir predstavlja količinu sa druge strane. Isprobaj sve pozicije od 0 do k i izaberi najmanju apsolutnu razliku.

C++ rešenje

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<long long> zbirReda(k, 0);

    for (int komad = 0; komad < n; komad++) {
        for (int red = 0; red < k; red++) {
            for (int kolona = 0; kolona < k; kolona++) {
                int x;
                cin >> x;
                zbirReda[red] += x;
            }
        }
    }

    long long ukupno = 0;
    for (int red = 0; red < k; red++) {
        ukupno += zbirReda[red];
    }

    long long prvaStrana = 0;
    long long odgovor = ukupno;

    // Pozicija 0: sva drvna masa je na drugoj strani.
    // Posle svakog koraka proverava se sledeća pozicija testere.
    for (int pozicija = 0; pozicija <= k; pozicija++) {
        long long drugaStrana = ukupno - prvaStrana;
        long long razlika = llabs(prvaStrana - drugaStrana);

        odgovor = min(odgovor, razlika);

        if (pozicija < k) {
            prvaStrana += zbirReda[pozicija];
        }
    }

    cout << odgovor << '\n';
    return 0;
}

Složenost: Vremenska složenost je O(n · k² + k), jer se svaki element svake matrice učita jednom. Dodatna memorija je O(k).

Otvori originalno rešenje

ZADATAK 29 2022/23. · 7. razred

Kontrolna cifra

Stringovi Cifre Kontrolna suma

Napomena: Zadatak sa 3. kruga kvalifikacija, sezona 2022/23, za 7. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje, Stringovi i Nizovi.

Opciono: Dinamički niz – vector.

Kreditne kartice imaju 16 cifara, od kojih se poslednja koristi kao kontrolna cifra i izračunava se na osnovu ostalih 15.

Cifre se dele u dve grupe prema pozicijama koje se broje od nule, sleva nadesno. Cifre na parnim pozicijama množe se sa 2. Ako je dobijeni rezultat dvocifren, sabiraju se njegove cifre. Cifre na neparnim pozicijama ostaju nepromenjene.

Zatim se sabiraju sve transformisane i nepromenjene cifre. Kontrolna cifra bira se tako da njenim dodavanjem tom zbiru dobijemo broj deljiv sa 10.

Napisati program koji na osnovu prvih 15 cifara određuje kontrolnu cifru.

Ulaz

Unosi se niska od tačno 15 cifara.

Izlaz

Ispisati jednu cifru — izračunatu kontrolnu cifru.

Primer 1

Ulaz

430239720231900

Izlaz

Cifre na parnim pozicijama su 4, 0, 3, 7, 0, 3, 9 i 0. Posle množenja sa 2 i sabiranja cifara dvocifrenih rezultata dobijaju se 8, 0, 6, 5, 0, 6, 9 i 0.

Cifre na neparnim pozicijama ostaju 3, 2, 9, 2, 2, 1 i 0. Njihov zbir je 19, a zbir transformisanih cifara sa parnih pozicija je 34. Ukupan zbir je 53, pa je kontrolna cifra 7 jer je 53 + 7 = 60.

Ideja za rešavanje: Učitaj cifre kao string kako bi se sačuvale sve pozicije. Prođi kroz prvih 15 znakova. Cifre na parnim indeksima udvostruči; ako je rezultat veći od 9, oduzmi 9. Saberi dobijene vrednosti. Kontrolna cifra je (10 − zbir % 10) % 10.

C++ rešenje

#include <iostream>
#include <string>
using namespace std;

int main() {
    string broj;
    cin >> broj;

    int zbir = 0;

    for (int i = 0; i < 15; i++) {
        int cifra = broj[i] - '0';

        if (i % 2 == 0) {
            cifra *= 2;

            if (cifra > 9) {
                cifra -= 9;
            }
        }

        zbir += cifra;
    }

    int kontrolna = (10 - zbir % 10) % 10;
    cout << kontrolna << '\n';

    return 0;
}

Kada se cifra udvostruči, oduzimanje 9 od rezultata većeg od 9 odgovara sabiranju njegovih cifara: na primer, 7 · 2 = 14, a 1 + 4 = 5, odnosno 14 − 9 = 5.

ZADATAK 30 2022/23. · 8. razred

Obrtanje

Stringovi Veliki brojevi Palindromi

Napomena: Zadatak sa 2. kruga kvalifikacija, sezona 2022/23, za 8. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje, Petlje, Stringovi i Nizovi.

Opciono: Dinamički niz – vector.

Dat je broj N i broj njegovih obrtanja r. Potrebno je ispisati da li je broj koji se dobija posle r uzastopnih obrtanja broja N jednak početnom broju N.

Obrtanjem broja dobija se broj zapisan istim ciframa, ali obrnutim redosledom. Na primer, obrtanjem broja 310 dobija se 13, a obrtanjem broja 2227 dobija se 7222.

Ulaz

U prvom redu nalazi se broj N, a u drugom broj r. Oba broja su nenegativna cela i važi 0 ≤ N < 10⁵⁰⁰⁰⁰ i 0 ≤ r < 1 000 000.

U testovima vrednim 60% poena važi 0 ≤ N < 200 000 i 0 ≤ r < 15.

Izlaz

Ispisati DA ako je rezultat posle r obrtanja jednak početnom broju, a u suprotnom ispisati NE.

Primer 1

Ulaz

1239999999999999999999321
787657

Izlaz

DA

Primer 2

Ulaz

1000000020000000300000004
458698

Izlaz

DA

Primer 3

Ulaz

10000000200000003000000040
2

Izlaz

NE

Ideja za rešavanje: Ne moramo zaista da obavimo do milion obrtanja. Ako je r = 0, broj ostaje nepromenjen. Ako je N = 0, takođe ostaje isti za bilo koji broj obrtanja. Ako se N završava nulom i r je pozitivan, prvo obrtanje uklanja te završne nule, pa broj više ne može biti jednak početnom. U ostalim slučajevima obrtanje se ponaša kao obična promena redosleda znakova: paran broj obrtanja vraća početni broj, a neparan broj ga vraća samo ako je N palindrom.

C++ rešenje

#include <iostream>
#include <string>
using namespace std;

int main() {
    string N;
    long long r;

    cin >> N >> r;

    if (r == 0 || N == "0") {
        cout << "DA\n";
        return 0;
    }

    // Obrtanje uklanja završne nule broja.
    if (N.back() == '0') {
        cout << "NE\n";
        return 0;
    }

    // Dva obrtanja vraćaju broj bez završnih nula.
    if (r % 2 == 0) {
        cout << "DA\n";
        return 0;
    }

    // Kod neparnog broja obrtanja N mora biti palindrom.
    bool palindrom = true;

    for (int i = 0; i < (int)N.size() / 2; i++) {
        if (N[i] != N[N.size() - 1 - i]) {
            palindrom = false;
            break;
        }
    }

    cout << (palindrom ? "DA" : "NE") << '\n';
    return 0;
}

String omogućava rad sa brojem koji ima do 50.000 cifara, bez prekoračenja opsega numeričkih tipova. Provera palindroma traje O(L), gde je L broj cifara broja N, dok broj obrtanja r ne utiče na vreme izvršavanja.

ZADATAK 31 2022/23. · 7. razred

Naizmenična podela

Strategija Rekurzija Matematika

Napomena: Zadatak sa 3. kruga kvalifikacija, sezona 2022/23, za 7. razred. Preuzet sa takprog.petlja.org.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje i Petlje.

Prema priči iz zadatka, bog trgovine i kakaoa Ek Chuah i bog munje Kʼawiil bore se za poslednju štanglicu čokolade. Štanglica ima n kockica.

Ek Chuah prvi pravi jedan rez i deli štanglicu na dva dela. Zatim Kʼawiil bira jedan od ta dva dela i uzima ga. Postupak se nastavlja na delu koji je ostao: bogovi naizmenično prave rezove i uzimaju odabrane delove. Kada ostane samo jedna kockica, ona pripada bogu koji je sledeći na redu da je uzme.

Obojica žele da dobiju što više čokolade i igraju optimalno. Napisati program koji određuje koliko će kockica dobiti Ek Chuah.

Ulaz

U jednom redu unosi se prirodan broj n, gde je 1 ≤ n ≤ 10⁹.

Izlaz

Ispisati jedan ceo broj — broj kockica koje će Ek Chuah dobiti ako oba boga igraju optimalno.

Primer 1

Ulaz

Izlaz

Ek Chuah podeli štanglicu na delove od 4 i 3 kockice. Kʼawiil uzima deo od 4 kockice. Zatim Kʼawiil deli preostale 3 kockice na delove od 1 i 2, a Ek Chuah uzima deo od 2 kockice. Poslednja kockica pripada Kʼawiilu. U ovom primeru Ek Chuah dobija 2, a Kʼawiil 5 kockica.

Primer 2

Ulaz

Izlaz

Primer 3

Ulaz

Izlaz

Primer 4

Ulaz

Izlaz

Ideja za rešavanje: Optimalni potez deli preostali deo što ravnomernije, jer protivnik bira koji deo uzima. Zato se broj kockica koje igrač može da osvoji može izračunati pomoću rekurzivne funkcije. Nije potrebno simulirati svako sečenje — dovoljno je nekoliko rekurzivnih poziva dok se broj ne svede na 1.

C++ rešenje

#include <iostream>
using namespace std;

long long f(long long n) {
    if (n == 1) {
        return 1;
    }

    return n - f(n / 2);
}

int main() {
    long long n;
    cin >> n;

    if (n == 1) {
        cout << 0 << '\n';
    } else {
        cout << f(n / 2) << '\n';
    }

    return 0;
}

Složenost: O(log n) vremenski i O(log n) memorijski zbog steka rekurzivnih poziva.

ZADATAK 32 Razred i sezona nisu navedeni

Ko prvi igra

Nizovi Sortiranje Uslovi

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje i Nizovi.

Ana, Boban i Vlada žele da igraju društvenu igru. Da bi odredili redosled igranja, svako od njih baca kockicu. Prvi igra onaj ko je dobio najveći broj, drugi onaj ko je dobio sledeći najveći broj, a treći igrač onaj ko je dobio najmanji broj.

Napisati program koji ispisuje redosled igranja na osnovu rezultata bacanja kockica.

Ulaz

Unose se tri različita broja a, b i v, razdvojena razmacima. Svaki broj je između 1 i 6. Oni predstavljaju rezultate bacanja kockica Ane, Bobana i Vlade, tim redom.

Izlaz

Ispisati slova A, B i V prema redosledu kojim igrači igraju. Slova se ispisuju bez razmaka.

Primer 1

Ulaz

2 6 3

Izlaz

BVA

Boban je dobio 6, Vlada 3, a Ana 2, pa igraju redom B, V, A.

Primer 2

Ulaz

5 4 3

Izlaz

ABV

Primer 3

Ulaz

2 1 4

Izlaz

VAB

Ideja za rešavanje: Sačuvaj rezultat bacanja svake osobe zajedno sa njenim slovom. Zatim poređaj igrače po rezultatu od najvećeg ka najmanjem i ispiši njihova slova tim redom.

C++ rešenje

#include <algorithm>
#include <iostream>
using namespace std;

struct Igrac {
    int rezultat;
    char slovo;
};

int main() {
    Igrac igraci[3];

    cin >> igraci[0].rezultat
        >> igraci[1].rezultat
        >> igraci[2].rezultat;

    igraci[0].slovo = 'A';
    igraci[1].slovo = 'B';
    igraci[2].slovo = 'V';

    sort(igraci, igraci + 3,
         [](const Igrac& x, const Igrac& y) {
             return x.rezultat > y.rezultat;
         });

    for (int i = 0; i < 3; i++) {
        cout << igraci[i].slovo;
    }

    cout << '\n';
    return 0;
}

Uz svaki rezultat čuva se i slovo igrača, tako da se pri sortiranju ne izgubi informacija o tome kome rezultat pripada. Lambda-funkcija poredi rezultate opadajuće.

ZADATAK 33 2023/24. · Razred nije potvrđen

Zbir izdvojenih grupa cifara iz broja

Cifre Celobrojno deljenje Ostatak pri deljenju

Napomena: U dostavljenom tekstu zadatak je naveden u odeljku o kvalifikacijama 2023/24. za 6. razred, ali zaglavlje tog odeljka navodi zadatke 35–37. Razred zato treba potvrditi. Portal naveden kao izvor: takprog.petlja.org/osnovnaskola.

Potrebno predznanje: Podaci u C++, Operatori u C++ i Grananje.

Uneti šestocifreni ceo broj i sabrati dvocifrene brojeve koji se dobijaju izdvajanjem prve dve i poslednje dve cifre početnog broja.

Na primer, za broj 123456 prve dve cifre formiraju broj 12, a poslednje dve cifre broj 56. Traženi zbir je 12 + 56 = 68.

Ulaz

Unosi se jedan šestocifreni ceo broj.

Izlaz

Ispisati zbir broja koji čine prve dve cifre i broja koji čine poslednje dve cifre unetog broja.

Primer 1

Ulaz

Izlaz

Prve dve cifre daju 12, a poslednje dve 56. Zbir je 12 + 56 = 68.

Primer 2

Ulaz

Izlaz

Celobrojnim deljenjem sa 10000 dobija se 67, a ostatak pri deljenju sa 100 je 41. Zato je traženi zbir 67 + 41 = 108.

Ideja za rešavanje: Za izdvajanje prve dve cifre podeli broj sa 10000 celobrojno. Za izdvajanje poslednje dve cifre izračunaj ostatak pri deljenju sa 100. Saberi dobijene vrednosti.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int broj;
    cin >> broj;

    int prveDve = broj / 10000;
    int poslednjeDve = broj % 100;

    cout << prveDve + poslednjeDve << '\n';

    return 0;
}

Složenost: O(1) vremenski i O(1) memorijski, jer se obavlja fiksan broj aritmetičkih operacija.

34. Preklapanje cifara

Napomena: Zadatak iz programiranja. Razred nije posebno naveden u dostavljenoj postavci.

Potrebno predznanje: Podaci u C++, Operatori u C++.

Mare i Paja igraju igricu i došli su do nivoa na kojem treba da reše šifru. Shvatili su da je šifra petocifren broj koji je bio zapisan na zidu na prethodnom nivou igrice.

Nijedan od njih ne može da se seti celog broja, ali se sećaju njegovih delova. Mare je zapamtio prve tri cifre, a Paja poslednje tri.

Pomozite im da pređu na sledeći nivo tako što ćete odrediti traženi petocifreni broj. Pretpostavite da su obojica ispravno zapamtila cifre i da su uneti podaci ispravni.

Ulaz

U prvom redu nalazi se trocifren broj koji je zapamtio Mare. U drugom redu nalazi se trocifren broj koji je zapamtio Paja.

Izlaz

Ispisati traženi petocifreni broj.

Primer 1

Ulaz

145
563

Izlaz

Objašnjenje: Mare je zapamtio prve tri cifre, pa broj počinje ciframa 145. Paja je zapamtio poslednje tri cifre, pa se broj završava ciframa 563. Traženi broj je 14563.

Primer 2

Ulaz

788
851

Izlaz

Prvi broj treba da čini početak rezultata, dok od drugog broja treba preuzeti samo poslednje dve cifre.

Poslednje dve cifre drugog broja dobijaju se pomoću operatora ostatka pri deljenju sa 100:

drugi % 100

Prvi broj pomnožimo sa 100 kako bismo napravili mesta za poslednje dve cifre, a zatim dodamo izdvojene cifre drugog broja.

rezultat = prvi * 100 + drugi % 100;

#include <iostream>
using namespace std;

int main() {
    int prvi, drugi;
    cin >> prvi >> drugi;

    int rezultat = prvi * 100 + drugi % 100;
    cout << rezultat << '\n';

    return 0;
}

35. Najveća prednost domaćih

Napomena: Zadatak iz programiranja. Razred nije posebno naveden u dostavljenoj postavci.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje u programu u C/C++, Petlje.

Dat je rezultat košarkaške utakmice nakon svake četvrtine. Odrediti kolika je najveća moguća prednost domaće ekipe tokom utakmice.

Rezultati su dati nakon završetka svake četvrtine. Tokom četvrtine, domaća ekipa može da postigne svoje poene pre nego što gostujuća ekipa postigne svoje poene u toj četvrtini.

Ulaz

U svakom od četiri reda standardnog ulaza nalaze se po dva cela nenegativna broja razdvojena razmakom.

Svaki red odgovara rezultatu nakon jedne četvrtine, redom. Prvi broj predstavlja broj poena domaće ekipe, a drugi broj broj poena gostujuće ekipe. Nijedan broj nije veći od 200.

Izlaz

Ispisati jedan ceo broj — najveću moguću prednost domaće ekipe. Ako domaća ekipa ni u jednom trenutku nije mogla da ima prednost, ispisati 0.

Primer 1

Ulaz

Izlaz

Obrazloženje: U jednom trenutku rezultat je mogao da bude 78:54, što predstavlja prednost domaće ekipe od 24 poena.

Primer 2

Ulaz

Izlaz

Obrazloženje: Domaća ekipa nikada nije bila u vođstvu. Najpovoljniji rezultat za nju bio je na početku utakmice, kada je rezultat bio 0:0.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int domaci, gosti;
    int prethodniGosti = 0;
    int najvecaPrednost = 0;

    for (int i = 0; i < 4; i++) {
        cin >> domaci >> gosti;

        najvećaPrednost = max(najvećaPrednost,
                             domaci - prethodniGosti);

        prethodniGosti = gosti;
    }

    cout << najvećaPrednost << '\n';
    return 0;
}

36. Promena škole

Napomena: Zadatak iz programiranja. Razred nije posebno naveden u dostavljenoj postavci.

Potrebno predznanje: Podaci u C++, Operatori u C++, Grananje u programu u C/C++.

Na kraju prvog razreda srednje škole Ivana je odlučila da se prebaci iz medicinske škole u gimnaziju. U gimnaziji su odlučili da joj računaju prosečnu ocenu samo iz predmeta koji postoje u obe škole.

Znamo da se \(k\) Ivaninih predmeta iz medicinske škole neće računati u prosek u gimnaziji. Odrediti Ivanin novi prosek ako su poznati ukupan broj predmeta koje je slušala u medicinskoj školi (\(n\)), ocene iz predmeta koji se neće računati i njen dosadašnji prosek \(p\).

Pretpostaviti da je Ivana završila razred, odnosno da nije imala nijednu zaključenu jedinicu.

Prosek ocena \(a_1,a_2,\ldots,a_n\) računa se kao:

\((a_1+a_2+\cdots+a_n)/n\)

Ulaz

U prvom redu standardnog ulaza nalazi se prirodan broj \(n\), a u drugom broj \(k\), pri čemu važi \(1 \leq k < n \leq 50\).

U narednih \(k\) redova date su Ivanine zaključne ocene iz predmeta koji se neće računati u novi prosek. Svaka ocena je prirodan broj od 2 do 5.

U poslednjem redu nalazi se broj \(p\), koji predstavlja Ivanin dosadašnji prosek iz medicinske škole, zaokružen na dve decimale.

Izlaz

Ispisati novi Ivanin prosek, zaokružen na dve decimale.

Primer 1

Ulaz

Izlaz

4.50

Primer 2

Ulaz

Izlaz

4.67

Ukupan zbir svih Ivaninih ocena može se dobiti približno kao \(p \cdot n\). Zatim od tog zbira oduzimamo ocene iz predmeta koji se neće računati u novi prosek.

Preostali zbir delimo brojem predmeta koji ulaze u novi prosek, odnosno brojem \(n-k\).

Formula je:

noviProsek = (p * n - zbirIzbacenihOcena) / (n - k);

Za ispis na dve decimale koristimo `fixed` i `setprecision(2)` iz biblioteke `iomanip`.

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    int zbirIzbacenihOcena = 0;

    for (int i = 0; i < k; i++) {
        int ocena;
        cin >> ocena;
        zbirIzbacenihOcena += ocena;
    }

    double p;
    cin >> p;

    double ukupniZbir = p * n;
    double noviProsek =
        (ukupniZbir - zbirIzbacenihOcena) / (n - k);

    cout << fixed << setprecision(2)
         << noviProsek << '\n';

    return 0;
}

37. PIN aplikacije od PIN-a telefona

Napomena: Zadatak sa kvalifikacija za školsku 2024/25. godinu. U postojećoj postavci naveden je 8. razred.

Potrebno predznanje: Podaci u C++, Operatori u C++, Operatori — primeri.

Student treba da odredi četvorocifreni PIN za novu aplikaciju, ali nije siguran da će ga dobro zapamtiti. Zato je smislio da novi PIN izračuna na osnovu PIN-a svog telefona.

Sabraće PIN svog telefona, broj koji se dobija kada se tom PIN-u zamene prva i poslednja cifra i broj koji se dobija kada se zamene dve središnje cifre.

Novi PIN čine poslednje četiri cifre tako dobijenog zbira.

Na primer, ako je PIN telefona 1234, računa se zbir \(1234 + 4231 + 1324 = 6789\), pa je novi PIN 6789.

Ulaz

Sa standardnog ulaza unosi se četvorocifreni PIN telefona. PIN može da sadrži vodeće nule.

Izlaz

Ispisati četvorocifreni PIN aplikacije, uključujući vodeće nule ako ih ima.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Objašnjenje: Zbir je \(9999 + 9999 + 9999 = 29997\), pa poslednje četiri cifre daju 9997.

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

int main() {
    string pin;
    cin >> pin;

    string prvi = pin;
    string drugi = pin;
    string treci = pin;

    swap(drugi[0], drugi[3]);
    swap(treci[1], treci[2]);

    int zbir = stoi(prvi) + stoi(drugi) + stoi(treci);
    int noviPin = zbir % 10000;

    cout << setw(4) << setfill('0')
         << noviPin << '\n';

    return 0;
}

38. Horoskop

Napomena: Zadatak sa 2. kruga kvalifikacija, sezona 2019/20. Razred nije potvrđen u dostavljenoj postavci.

Izvor: dms.rs/informatika-osnovne-skole

Potrebno predznanje: Podaci u C++, Grananje u programu u C/C++, Petlje, Stringovi.

Jedinstveni matični broj građana (JMBG) je niz od 13 cifara. Prve dve cifre predstavljaju dan, a sledeće dve mesec rođenja. Na primer, ako JMBG počinje sa 0904, osoba je rođena 9. aprila, a ako počinje sa 3112, osoba je rođena 31. decembra.

Perica želi da prebroji koliko osoba sa spiska pripada svakom horoskopskom znaku. Za svaki znak poznati su početni i završni datumi:

OVAN — od 21. marta do 20. aprila
BIK — od 21. aprila do 21. maja
BLIZANCI — od 22. maja do 21. juna
RAK — od 22. juna do 22. jula
LAV — od 23. jula do 22. avgusta
DEVICA — od 23. avgusta do 22. septembra
VAGA — od 23. septembra do 23. oktobra
ŠKORPIJA — od 24. oktobra do 22. novembra
STRELAC — od 23. novembra do 21. decembra
JARAC — od 22. decembra do 20. januara
VODOLIJA — od 21. januara do 19. februara
RIBE — od 20. februara do 20. marta

Ulaz

U prvom redu nalazi se broj \(N\) (\(1 \leq N \leq 200\)), koji predstavlja broj JMBG-ova na spisku.

U svakom od narednih \(N\) redova nalazi se po jedan JMBG od 13 cifara, bez razmaka.

Izlaz

Ispisati 12 celih brojeva, svaki u posebnom redu. Prvi broj predstavlja broj osoba u znaku Ovna, drugi u znaku Bika i tako redom, sve do dvanaestog broja koji predstavlja broj osoba u znaku Riba.

Primer 1

Ulaz

5
1504279718463
0412622712918
1903326718649
0710262713307
0104646719372

Izlaz

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;

    int broj[12] = {};

    for (int i = 0; i < N; i++) {
        string jmbg;
        cin >> jmbg;

        int dan = stoi(jmbg.substr(0, 2));
        int mesec = stoi(jmbg.substr(2, 2));

        int znak = -1;

        if ((mesec == 3 && dan >= 21) ||
            (mesec == 4 && dan <= 20)) {
            znak = 0; // Ovan
        } else if ((mesec == 4 && dan >= 21) ||
                   (mesec == 5 && dan <= 21)) {
            znak = 1; // Bik
        } else if ((mesec == 5 && dan >= 22) ||
                   (mesec == 6 && dan <= 21)) {
            znak = 2; // Blizanci
        } else if ((mesec == 6 && dan >= 22) ||
                   (mesec == 7 && dan <= 22)) {
            znak = 3; // Rak
        } else if ((mesec == 7 && dan >= 23) ||
                   (mesec == 8 && dan <= 22)) {
            znak = 4; // Lav
        } else if ((mesec == 8 && dan >= 23) ||
                   (mesec == 9 && dan <= 22)) {
            znak = 5; // Devica
        } else if ((mesec == 9 && dan >= 23) ||
                   (mesec == 10 && dan <= 23)) {
            znak = 6; // Vaga
        } else if ((mesec == 10 && dan >= 24) ||
                   (mesec == 11 && dan <= 22)) {
            znak = 7; // Škorpija
        } else if ((mesec == 11 && dan >= 23) ||
                   (mesec == 12 && dan <= 21)) {
            znak = 8; // Strelac
        } else if ((mesec == 12 && dan >= 22) ||
                   (mesec == 1 && dan <= 20)) {
            znak = 9; // Jarac
        } else if ((mesec == 1 && dan >= 21) ||
                   (mesec == 2 && dan <= 19)) {
            znak = 10; // Vodolija
        } else {
            znak = 11; // Ribe
        }

        broj[znak]++;
    }

    for (int i = 0; i < 12; i++) {
        cout << broj[i] << '\n';
    }

    return 0;
}

39. Artimogrifi

Napomena: Zadatak sa 2. kruga kvalifikacija. Razred i sezona nisu potvrđeni u dostavljenoj postavci.

Potrebno predznanje: Podaci u C++, Stringovi, Nizovi.

Pri rešavanju jedne poznate vrste aritmetičkih rebusa potrebno je ista slova zameniti istim ciframa, a različita slova različitim ciframa, tako da se dobije tačna jednakost.

Na primer, za rebus SNEG + KRUG = SPORT jedno od rešenja je 1937 + 8627 = 10564. U ovom zadatku ne proverava se da li je jednakost tačna, već samo da li je zamena slova ciframa pravilno izvedena.

Na primer, ponuđeno „rešenje” 4832 + 5962 = 10794 nije ispravno, iako je jednakost tačna. Slovo S je na jednom mestu zamenjeno cifrom 4, a na drugom cifrom 1. Takođe, cifra 4 odgovara dvama različitim slovima.

Napisati program koji proverava da li je zamena slova ciframa pravilno izvedena.

Ulaz

U prvom redu unosi se string koji predstavlja aritmetički rebus. Može da sadrži velika slova engleske abecede, razmake, znake matematičkih operacija i znak jednakosti. Ukupna dužina stringa nije veća od 100, a broj različitih slova nije veći od 10.

U drugom redu unosi se string koji predstavlja ponuđeno rešenje rebusa iz prvog reda. Drugi string se od prvog razlikuje isključivo po tome što je svako slovo zamenjeno nekom cifrom.

Izlaz

Ispisati `da` ako je zamena pravilna, bez obzira na to da li je jednakost tačna. U suprotnom ispisati `ne`.

Primer 1

Ulaz

SNEG + KRUG = SPORT
2341 + 8751 = 20679

Izlaz

da

Primer 2

Ulaz

SNEG + KRUG = SPORT
4832 + 5962 = 10794

Izlaz

ne

#include <iostream>
#include <string>
using namespace std;

int main() {
    string rebus, resenje;
    getline(cin, rebus);
    getline(cin, resenje);

    if (rebus.size() != resenje.size()) {
        cout << "ne\n";
        return 0;
    }

    int slovoUCifru[26];
    int cifraUSlovo[10];

    for (int i = 0; i < 26; i++) {
        slovoUCifru[i] = -1;
    }

    for (int i = 0; i < 10; i++) {
        cifraUSlovo[i] = -1;
    }

    for (int i = 0; i < (int)rebus.size(); i++) {
        char slovo = rebus[i];
        char znak = resenje[i];

        if (slovo >= 'A' && slovo <= 'Z') {
            if (znak < '0' || znak > '9') {
                cout << "ne\n";
                return 0;
            }

            int indeksSlova = slovo - 'A';
            int cifra = znak - '0';

            if (slovoUCifru[indeksSlova] != -1 &&
                slovoUCifru[indeksSlova] != cifra) {
                cout << "ne\n";
                return 0;
            }

            if (cifraUSlovo[cifra] != -1 &&
                cifraUSlovo[cifra] != indeksSlova) {
                cout << "ne\n";
                return 0;
            }

            slovoUCifru[indeksSlova] = cifra;
            cifraUSlovo[cifra] = indeksSlova;
        } else {
            if (slovo != znak) {
                cout << "ne\n";
                return 0;
            }
        }
    }

    cout << "da\n";
    return 0;
}

40. Dve police

Takmičenje: drugi krug kvalifikacija

Razred: razred nije potvrđen

Postavka zadatka

U prodavnici se prodaju dve vrste polica čije su dužine i cene poznate. Police želimo da postavimo duž jednog zida tako da popunimo što veći deo njegove dužine. Ako se ista dužina zida može popuniti na više načina, biramo onu kombinaciju polica koja ima najmanju ukupnu cenu.

Napisati program koji određuje najveću moguću dužinu zida koju možemo da popunimo policama i najmanju cenu po kojoj to možemo da uradimo.

Ulaz

U prvom redu standardnog ulaza nalazi se ceo broj z (1 ≤ z ≤ 10⁶) koji predstavlja dužinu zida. U naredna dva reda nalaze se podaci o vrstama polica: dužina i cena. Dužina svake police je prirodan broj između 1 i 10⁶, a cena je prirodan broj između 1 i 1000.

Izlaz

Ispisati najveću moguću dužinu zida koja se može popuniti policama i najmanju ukupnu cenu za tu dužinu, razdvojene jednim razmakom.

Primer

Ulaz

24
3 10
5 8

Izlaz

24 54

Jedan način da se popuni svih 24 jedinice zida jeste da se upotrebe tri police dužine 3 i tri police dužine 5. Njihova ukupna cena je 3 · 10 + 3 · 8 = 54.

Ideja rešenja

Za svaku dužinu zida od 0 do z računamo najmanju cenu kojom se ta dužina može potpuno popuniti. Do neke dužine možemo doći dodavanjem police prve ili druge vrste na već popunjeni deo zida. Kada izračunamo sve mogućnosti, tražimo najveću dostižnu dužinu koja nije veća od z.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int z;
    cin >> z;

    int a, ca, b, cb;
    cin >> a >> ca;
    cin >> b >> cb;

    const long long INF = LLONG_MAX / 4;
    vector<long long> dp(z + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= z; i++) {
        if (i >= a && dp[i - a] != INF) {
            dp[i] = min(dp[i], dp[i - a] + ca);
        }

        if (i >= b && dp[i - b] != INF) {
            dp[i] = min(dp[i], dp[i - b] + cb);
        }
    }

    for (int i = z; i >= 0; i--) {
        if (dp[i] != INF) {
            cout << i << ' ' << dp[i] << '\n';
            break;
        }
    }

    return 0;
}

41. Najveći broj od datih cifara

Takmičenje: treći krug kvalifikacija

Razred: razred nije potvrđen

Postavka zadatka

Za dati prirodan broj potrebno je ispisati najveći broj koji se može zapisati koristeći iste cifre, pri čemu se svaka cifra upotrebljava isti broj puta kao u polaznom broju.

Ulaz

U prvom redu standardnog ulaza nalazi se broj N. Broj može imati najviše 30 cifara.

Izlaz

Ispisati najveći broj koji se može sastaviti od cifara broja N.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Ideja rešenja

Da bi broj bio što veći, njegove cifre treba poređati od najveće ka najmanjoj. Broj čitamo kao string jer može imati 30 cifara, što je više nego što staje u standardne celobrojne tipove.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string n;
    cin >> n;

    sort(n.begin(), n.end(), greater<char>());

    cout << n << '\n';

    return 0;
}

42. Riziko

Takmičenje: treći krug kvalifikacija

Razred: razred nije potvrđen

Postavka zadatka

Tokom igre Riziko napadač i odbrambeni igrač ulaze u bitke bacanjem kockica. Svaki igrač ima tri kockice, ali u zavisnosti od trenutnog stanja igre može da baci jednu, dve ili tri kockice.

Nakon bacanja, kockice svakog igrača poređaju se od najveće ka najmanjoj. Zatim se porede najjače kockice, pa druge po jačini, a zatim i najslabije kockice, ukoliko postoje kod oba igrača. Ako je jedan igrač bacio manje kockica, neupoređene slabije kockice drugog igrača se zanemaruju.

Ako napadač ima strogo veći broj na kockici od odbrambenog igrača, odbrambeni igrač gubi jedan poen. U suprotnom, napadač gubi jedan poen. Dakle, u slučaju jednakih vrednosti poen gubi napadač.

Napisati program koji određuje koliko poena gubi napadač, a koliko odbrambeni igrač.

Ulaz

Prvi red sadrži broj kockica koje je bacio napadač (1, 2 ili 3). Drugi red sadrži vrednosti njegovih kockica, od 1 do 6. Treći red sadrži broj kockica koje je bacio odbrambeni igrač (1, 2 ili 3), a četvrti red vrednosti njegovih kockica.

Izlaz

Ispisati broj poena koje gubi napadač i broj poena koje gubi odbrambeni igrač, razdvojene jednim razmakom.

Primer

Ulaz

Izlaz

1 2

Napadačeve kockice su 6, 5 i 3, a odbrambenog igrača 5, 4 i 3. Napadač dobija prvo poređenje, jer je 6 veće od 5. U drugom poređenju 5 je veće od 4, pa odbrambeni igrač gubi još jedan poen. U trećem poređenju vrednosti su jednake, pa napadač gubi jedan poen.

Ideja rešenja

Sortiramo oba niza kockica opadajuće. Poređenje ponavljamo onoliko puta koliko ima kockica kod igrača koji ih je bacio manje. Za svako poređenje uvećamo broj izgubljenih poena odgovarajućeg igrača.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    int napad[3], odbrana[3];

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> napad[i];
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> odbrana[i];
    }

    sort(napad, napad + n, greater<int>());
    sort(odbrana, odbrana + m, greater<int>());

    int izgubljeniNapad = 0;
    int izgubljenaOdbrana = 0;
    int brojPoredjenja = min(n, m);

    for (int i = 0; i < brojPoredjenja; i++) {
        if (napad[i] > odbrana[i]) {
            izgubljenaOdbrana++;
        } else {
            izgubljeniNapad++;
        }
    }

    cout << izgubljeniNapad << ' '
         << izgubljenaOdbrana << '\n';

    return 0;
}

43. ATP pobednik

Takmičenje: treći krug kvalifikacija

Razred: razred nije potvrđen

Postavka zadatka

Tokom godine održavaju se brojni teniski turniri na kojima teniseri osvajaju poene. Poeni osvojeni na različitim turnirima sabiraju se, a na kraju godine teniseri se rangiraju prema ukupnom broju poena.

Napisati program koji na osnovu rezultata svih turnira određuje tenisera sa najviše osvojenih poena i ispisuje njegovo prezime i ukupan broj poena. Pretpostaviti da pobednik ima strogo više poena od svih ostalih tenisera.

Ulaz

U prvom redu standardnog ulaza nalazi se broj n. U narednih n redova nalaze se prezime tenisera i broj poena osvojenih na jednom turniru. Isti teniser može da se pojavi više puta.

Izlaz

Ispisati prezime pobednika i njegov ukupan broj poena, razdvojene jednim razmakom.

Primer 1

Ulaz

9
Djokovic 1000
Nadal 800
Federer 600
Nadal 1000
Federer 800
Djokovic 600
Djokovic 1000
Cicipas 800
Nadal 600

Izlaz

Djokovic 2600

Primer 2

Ulaz

6
Zverev 1000
Cicipas 800
Medvedev 700
Thiem 1000
Cicipas 800
Medvedev 600

Izlaz

Cicipas 1600

Ideja rešenja

Za svakog tenisera vodimo ukupan zbir poena. Kada učitamo rezultat turnira, dodajemo osvojene poene zbiru tog tenisera. Nakon obrade svih redova pronalazimo tenisera sa najvećim ukupnim zbirom.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    map<string, long long> poeni;

    for (int i = 0; i < n; i++) {
        string prezime;
        long long brojPoena;

        cin >> prezime >> brojPoena;
        poeni[prezime] += brojPoena;
    }

    string pobednik;
    long long najvisePoena = -1;

    for (const auto& teniser : poeni) {
        if (teniser.second > najvisePoena) {
            najvisePoena = teniser.second;
            pobednik = teniser.first;
        }
    }

    cout << pobednik << ' ' << najvisePoena << '\n';

    return 0;
}

Kvalifikacije za okružna takmičenja iz informatike

Gorivo

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Kakuro provera

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Spisak proizvoda

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Razumevanje i rešavanje zadatka

Primer obračuna

Uputstvo — ideja rešenja

1. Učitavanje cena

2. Početna suma

3. Prolazak kroz nisku

4. Provera kupljenog proizvoda

5. Zašto koristimo 'j', a ne "j"?

6. Koliko traje algoritam?

Rešenje 1 — jednostavnija varijanta

Objašnjenje koda

Rešenje 2 — varijanta sa substr()

Objašnjenje druge varijante

Poređenje dve varijante

Vremenska složenost

Majstor

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Primer 3

Ulaz

Izlaz

Zrak

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Broj dana odmerenog treninga

Postavka zadatka

Ulaz

Izlaz

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Kuvar

5. Zašto koristimo `'j'`, a ne `"j"`?

Rešenje 2 — varijanta sa `substr()`