Kvalifikacije za okružna takmičenja iz informatike – 5, 6. i 7. razred

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.

Rešenje 1 — šifre kao celi brojevi, cifra po cifra

Šifre se učitavaju kao celi brojevi, a cifre se izdvajaju deljenjem sa 1000, 100 i 10 i ostatkom pri deljenju sa 10. Za svaki prsten posebno se računa direktno okretanje i okretanje „preko nule”, pa se bira manje.

#include <iostream>
#include <algorithm>  // za funkciju min

using namespace std;

int main()
{
    // sif - ispravna šifra, br - trenutno namešten kod
    // A1..D1 - cifre šifre, A2..D2 - cifre trenutnog koda
    int sif, br, A1, B1, C1, D1, A2, B2, C2, D2;

    // x1..x4 - broj okretanja za svaki prsten, x - ukupan broj okretanja
    int x = 0, x1, x2, x3, x4;

    // Brojeve učitavamo kao cele brojeve. Vodeće nule se pri tome gube
    // (0319 postaje 319), ali to ne smeta: izdvajanjem cifara prva cifra
    // će i dalje biti 0.
    cin >> sif >> br;  // npr. 1234 7249

    // Izdvajanje cifara šifre
    A1 = sif / 1000;       // hiljade
    B1 = sif / 100 % 10;   // stotine
    C1 = sif % 100 / 10;   // desetice
    D1 = sif % 10;         // jedinice

    // Izdvajanje cifara trenutnog koda
    A2 = br / 1000;
    B2 = br / 100 % 10;
    C2 = br % 100 / 10;
    D2 = br % 10;

    /*
     * Za svaki prsten postoje dva smera okretanja:
     * - direktno: razlika između cifara,
     * - "preko nule": 10 minus ta razlika, jer su cifre poređane u krug.
     * Biramo manji od ta dva broja.
     *
     * Primer: sa 7 na 1 direktno ima 6 koraka (7-6-5-4-3-2-1),
     * a preko nule 4 koraka (7-8-9-0-1), pa je odgovor 4.
     */

    // Prvi prsten (hiljade)
    if (A1 > A2) {
        x1 = A1 - A2;                // direktna razlika
        x1 = min(x1, A2 + 10 - A1);  // ili okretanje preko nule
    }
    else {
        x1 = A2 - A1;
        x1 = min(x1, A1 + 10 - A2);
    }

    // Drugi prsten (stotine)
    if (B1 > B2) {
        x2 = B1 - B2;
        x2 = min(x2, B2 + 10 - B1);
    }
    else {
        x2 = B2 - B1;
        x2 = min(x2, B1 + 10 - B2);
    }

    // Treći prsten (desetice)
    if (C1 > C2) {
        x3 = C1 - C2;
        x3 = min(x3, C2 + 10 - C1);
    }
    else {
        x3 = C2 - C1;
        x3 = min(x3, C1 + 10 - C2);
    }

    // Četvrti prsten (jedinice)
    if (D1 > D2) {
        x4 = D1 - D2;
        x4 = min(x4, D2 + 10 - D1);
    }
    else {
        x4 = D2 - D1;
        x4 = min(x4, D1 + 10 - D2);
    }

    // Prstenovi se okreću nezavisno, pa se brojevi okretanja sabiraju.
    x = x1 + x2 + x3 + x4;

    cout << x << endl;

    return 0;
}

Rešenje 2 — poboljšana varijanta sa petljom

Šifre se učitavaju kao stringovi, pa se početne nule prirodno čuvaju. Za svaku od četiri pozicije računa se apsolutna razlika cifara d, a okretanje u drugom smeru traje 10 - d. U zbir se dodaje manja vrednost, min(d, 10 - d), pa nisu potrebna četiri if-else bloka.

#include <iostream>
#include <string>
#include <cstdlib>    // za funkciju abs
#include <algorithm>  // za funkciju min

using namespace std;

int main()
{
    // Šifre učitavamo kao stringove, pa se početne nule čuvaju
    // (npr. "0319" ostaje "0319").
    string sifra, kod;
    cin >> sifra >> kod;

    int ukupno = 0;  // ukupan broj okretanja svih prstenova

    // Isti postupak ponavljamo za svaki od četiri prstena.
    for (int i = 0; i < 4; i++) {

        // Pretvaranje znaka cifre u broj: '7' - '0' = 7
        int a = sifra[i] - '0';  // cifra ispravne šifre
        int b = kod[i] - '0';    // cifra na katancu

        // d - broj okretanja u jednom smeru (direktno)
        int d = abs(a - b);

        // U drugom smeru (preko 9 → 0) potrebno je 10 - d okretanja.
        // Biramo kraći put.
        ukupno += min(d, 10 - d);
    }

    cout << ukupno << endl;

    return 0;
}

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.

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;
}

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';

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;
}

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.

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;
}

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';

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;      // broj učenika
    cin >> n;

    // odlicni[r] - broj odličnih učenika u razredu r.
    // Niz ima 9 elemenata da bi indeksi 1..8 odgovarali razredima;
    // element odlicni[0] se ne koristi.
    // {0} postavlja sve brojače na nulu.
    int odlicni[9] = {0};

    // Učitavanje i prebrojavanje u istoj petlji:
    // podatke o učenicima nije potrebno pamtiti.
    for (int i = 0; i < n; i++) {
        int razred;     // razred učenika (od 1 do 8)
        double uspeh;   // uspeh je realan broj, zato double

        cin >> razred >> uspeh;

        // Odličan je uspeh veći ili jednak 4,5.
        // Razred učenika je ujedno i pozicija brojača u nizu.
        if (uspeh >= 4.5) {
            odlicni[razred]++;
        }
    }

    // najvise - najveći broj odličnih pronađen do sada.
    // Počinje od -1, da bi već prvi pregledani razred
    // (čak i sa 0 odličnih) postao početni maksimum.
    int najvise = -1;
    int odgovor = 8;    // razred sa najviše odličnih

    // Razrede obilazimo od 8 ka 1 i odgovor menjamo samo
    // kada nađemo STROGO veći broj (>). Tako pri jednakom
    // broju odličnih ostaje zapamćen veći razred.
    for (int razred = 8; razred >= 1; razred--) {
        if (odlicni[razred] > najvise) {
            najvise = odlicni[razred];
            odgovor = razred;
        }
    }

    cout << odgovor << '\n';

    return 0;
}

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';

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;
}

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.

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;
}

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.

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;
}

Detaljno uputstvo

1. Napravi niz zbirReda dužine k, u početku popunjen nulama.
2. Učitaj svaku od n matrica. Za svaki red izračunaj zbir njegovih elemenata i dodaj ga odgovarajućem elementu niza zbirReda.
3. Saberi sve elemente niza da dobiješ ukupnu količinu drveta.
4. Razmatraj pozicije testere od 0 do k. Postepeno dodaj sledeći red na zbir prve strane, dok količina na drugoj strani dobijaš oduzimanjem od ukupnog zbira.
5. Za svaku poziciju izračunaj apsolutnu razliku i zapamti najmanju.

Pošto je zbir broja polja ograničen uslovom n · k · k ≤ 10⁷, ovakav postupak je dovoljno brz. Memorija se koristi samo za niz od k zbirova redova.

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).

Detaljno uputstvo

1. Učitaj svih 15 cifara u promenljivu tipa string.
2. Za svaku poziciju od 0 do 14 pretvori znak u broj oduzimanjem karaktera '0'.
3. Ako je indeks paran, pomnoži cifru sa 2. Ako je rezultat veći od 9, oduzmi 9; ovo daje isti rezultat kao sabiranje cifara dvocifrenog broja.
4. Dodaj dobijenu vrednost ukupnom zbiru. Na neparnim indeksima dodaj originalnu cifru.
5. Izračunaj kontrolnu cifru formulom (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.

Detaljno uputstvo

Definišimo funkciju f(n) kao optimalan broj kockica koje dobija igrač koji bira deo u igri sa n kockica.

1. Ako je n = 1, preostala kockica ide igraču koji je sledeći na redu da uzme, pa je f(1) = 1.
2. Ako je n veće od 1, optimalna podela je na dva što sličnija dela. Zato igrač koji seče može da obezbedi protivniku najviše onoliko koliko odgovara polovini preostalog broja kockica.
3. Rekurzivno važi f(n) = n - f(n / 2), gde se celobrojno deljenje koristi za izraz n / 2.
4. Za početni broj n, Ek Chuah dobija f(n / 2), osim kada je n = 1. U tom slučaju odgovor je 0 jer je Kʼawiil prvi na redu da uzme jedinu kockicu.

Svaki rekurzivni poziv prepolovi argument, pa je broj poziva reda logaritma broja n.

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.

Detaljno uputstvo

1. Učitaj šestocifreni broj u promenljivu celobrojnog tipa.
2. Izračunaj broj / 10000. Pošto je u pitanju celobrojno deljenje, preostaju prve dve cifre.
3. Izračunaj broj % 100. Ostatak pri deljenju sa 100 predstavlja poslednje dve cifre broja.
4. Saberi dobijene vrednosti i ispiši zbir.

Na primer, za broj 678341 važi 678341 / 10000 = 67 i 678341 % 100 = 41. Rezultat je 67 + 41 = 108.

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.

Detaljno uputstvo

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;

C++ rešenje

#include <iostream>
using namespace std;

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

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

    return 0;
}

Detaljno uputstvo

Pošto su dati rezultati nakon svake četvrtine, razlika između rezultata iz dva uzastopna reda predstavlja broj poena osvojenih u tekućoj četvrtini.

Najveća moguća prednost u određenoj četvrtini može nastati ako domaća ekipa prvo postigne sve svoje poene iz te četvrtine, dok se rezultat gostujuće ekipe još nije promenio.

Ako su rezultati nakon tekuće četvrtine \(D\) i \(G\), a rezultat gostiju nakon prethodne četvrtine \(G_{preth}\), tada je moguća prednost \(D-G_{preth}\). Na početku utakmice rezultat je 0:0, pa se za prvo poređenje koristi prethodni rezultat gostiju 0.

Prolazimo kroz sve četiri četvrtine i pamtimo najveću vrednost razlike. Pošto se traži 0 ako domaći nikada nisu imali prednost, rezultat ne sme biti manji od nule.

C++ rešenje

#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;

        najvecaPrednost = max(najvecaPrednost,
                             domaci - prethodniGosti);

        prethodniGosti = gosti;
    }

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

Detaljno uputstvo

Ukupan zbir svih Ivaninih ocena je ceo broj, ali je prosek p zaokružen na dve decimale, pa je p * n samo približno jednak tom zbiru. Zato ga zaokružimo na najbliži ceo broj, a zatim od njega oduzmemo 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:

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

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

C++ rešenje

#include <iostream>
#include <iomanip>
#include <cmath>
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;

    // p je zaokružen na dve decimale, a pravi zbir ocena je ceo broj.
    long long ukupniZbir = llround(p * n);
    double noviProsek =
        (double)(ukupniZbir - zbirIzbacenihOcena) / (n - k);
    noviProsek += 1e-9; // zaštita od grešaka pri zaokruživanju na 2 decimale

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

    return 0;
}

Detaljno uputstvo

Za svaki JMBG potrebno je pročitati prve četiri cifre. Prve dve predstavljaju dan, a naredne dve mesec rođenja.

Datum možemo predstaviti parom brojeva dan i mesec. Zatim pomoću uslova proveravamo kom znaku pripada i uvećavamo odgovarajući brojač.

Posebnu pažnju treba obratiti na znak Jarca, čiji period prelazi iz decembra u januar. Osoba je Jarac ako je rođena od 22. do 31. decembra ili od 1. do 20. januara.

Na kraju ispisujemo svih 12 brojača redom, po jedan u svakom redu.

C++ rešenje

#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;
}

Detaljno uputstvo

Čitamo oba reda pomoću getline, jer stringovi sadrže razmake i znakove operacija.

Za svako slovo pamtimo kojoj cifri odgovara. Ako se isto slovo pojavi više puta, mora uvek da bude zamenjeno istom cifrom.

Istovremeno pamtimo i obrnuto preslikavanje: svaka cifra sme da odgovara najviše jednom slovu. Tako sprečavamo da dva različita slova budu zamenjena istom cifrom.

Svi znakovi koji nisu slova moraju ostati isti u oba reda. Ako se bilo koji od ovih uslova prekrši, ispisujemo ne; u suprotnom ispisujemo da.

C++ rešenje

#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;
}

Detaljno uputstvo

1. Napravimo niz dp, gde je dp[i] najmanja cena za potpuno popunjavanje dužine i.
2. Postavimo dp[0] = 0, jer za dužinu nula nije potrebna nijedna polica.
3. Za svaku dužinu i proverimo da li možemo da dodamo policu prve vrste ili policu druge vrste.
4. Na kraju pronađemo najveću dužinu za koju postoji rešenje i ispišemo tu dužinu i njenu najmanju cenu.

Složenost je O(z), a memorijska složenost O(z).

C++ rešenje

#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;
}

Detaljno uputstvo

1. Učitamo broj kao niz znakova.
2. Sortiramo cifre u opadajućem redosledu.
3. Ispišemo dobijeni niz znakova.

Sortiranje ima složenost O(d log d), gde je d broj cifara. Pošto je d ≤ 30, postupak je veoma brz.

C++ rešenje

#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;
}

Detaljno uputstvo

1. Učitamo broj kockica i njihove vrednosti za oba igrača.
2. Sortiramo oba niza od najveće ka najmanjoj vrednosti.
3. Odredimo manji od dva broja kockica. Toliko parova možemo da uporedimo.
4. Ako je napadačeva vrednost strogo veća, odbrambeni igrač gubi poen. U suprotnom poen gubi napadač.
5. Ispišemo izgubljene poene napadača, pa odbrambenog igrača.

C++ rešenje

#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;
}

Detaljno uputstvo

1. Učitamo broj rezultata turnira.
2. Koristimo mapu u kojoj je ključ prezime tenisera, a vrednost zbir njegovih poena.
3. Za svaki rezultat dodamo osvojene poene odgovarajućem teniseru.
4. Prođemo kroz mapu i pronađemo najveći zbir.
5. Ispišemo prezime tenisera i njegov zbir poena.

Ako je n broj rezultata, prosečna složenost korišćenja mape je O(n log n).

C++ rešenje

#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;
}