Okružna takmičenja iz informatike – zadaci

Uputstvo — ideja rešenja

1. Dve moguće podele

Trocifren broj abc može da se podeli na dva načina: a · bc i ab · c. Znak množenja postavlja se ili iza prve ili iza druge cifre.

2. Razdvajanje cifara

Celobrojno deljenje i ostatak daju delove broja: n / 100 je prva cifra, n % 100 poslednje dve cifre, n / 10 prve dve cifre, a n % 10 poslednja cifra.

3. Poređenje

Izračunamo oba proizvoda i ispišemo veći (funkcija max). Nule u sredini (npr. 105) ne smetaju: n % 100 je tada samo 5.

C++ rešenje

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

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

    // Podela 1: prva cifra i poslednje dve cifre
    int proizvod1 = (n / 100) * (n % 100);
    // Podela 2: prve dve cifre i poslednja cifra
    int proizvod2 = (n / 10) * (n % 10);

    cout << max(proizvod1, proizvod2) << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Zbirovi i ocene za dizajn

Za svakog programera čuvamo ocenu za dizajn i zbir obe ocene. Dovoljna su dva niza od po tri elementa.

2. Traženje pobednika

Pretpostavimo da vodi programer A. Zatim redom proveravamo B i C: novi programer preuzima vođstvo samo ako ima strogo veći zbir, ili isti zbir i strogo veću ocenu za dizajn.

3. Zašto ovo rešava i treći uslov

Pošto vođstvo menjamo samo kod strogo boljeg rezultata, pri potpunoj jednakosti ostaje raniji programer – a to je upravo onaj koji je prvi predstavio igricu.

4. Ispis

Indeks pobednika (0, 1 ili 2) pretvaramo u slovo izrazom (char)('A' + indeks).

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int dizajn[3], zbir[3];

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

    int pobednik = 0;                      // za sada vodi programer A
    for (int i = 1; i < 3; i++) {
        if (zbir[i] > zbir[pobednik] ||
            (zbir[i] == zbir[pobednik] && dizajn[i] > dizajn[pobednik])) {
            pobednik = i;
        }
    }

    cout << (char)('A' + pobednik) << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Pomoćna funkcija

Napravimo funkciju prelep(x) koja vraća true ako su sve cifre broja x različite.

2. Provera cifara

Cifre izdvajamo sa x % 10 i skraćujemo broj sa x /= 10. Pomoću niza videna[10] pamtimo koje smo cifre već srele; ako se neka cifra javi drugi put, broj nije prelep.

3. Broj 0

Za x = 0 petlja mora da se izvrši bar jednom, zato koristimo do { ... } while (x > 0). Broj 0 ima jednu cifru, pa je prelep.

4. Brojanje

Petljom for prođemo kroz sve brojeve od m do n i brojimo one za koje funkcija vrati true. Za najviše 10 miliona brojeva, sa najviše 8 cifara, to je dovoljno brzo.

C++ rešenje

#include <iostream>
using namespace std;

// Vraća true ako su sve cifre broja x međusobno različite
bool prelep(int x) {
    bool videna[10] = {false};

    do {
        int cifra = x % 10;
        if (videna[cifra]) {
            return false;
        }
        videna[cifra] = true;
        x /= 10;
    } while (x > 0);

    return true;
}

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

    int brojac = 0;
    for (int i = m; i <= n; i++) {
        if (prelep(i)) {
            brojac++;
        }
    }

    cout << brojac << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Sve vreme u minutima

Vreme pretvorimo u minute od ponoći: sat * 60 + minut. Tako se vremena lako upoređuju i oduzimaju.

2. Zajednički interval

Svi su u firmi istovremeno tek kada stigne poslednji od njih, a to je trenutak max svih dolazaka, i traje do odlaska prvog, odnosno min svih odlazaka.

3. Provera i ispis

Ako je najraniji odlazak − najkasniji dolazak veći od nule, sastanak je moguć. Trajanje u satima je / 60, a u minutima % 60. Inače ispisujemo ne.

C++ rešenje

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

int main() {
    int dolazakNajkasniji = 0;          // najkasniji dolazak (u minutima od ponoći)
    int odlazakNajraniji = 24 * 60;     // najraniji odlazak

    for (int i = 0; i < 5; i++) {
        int sd, md, so, mo;
        cin >> sd >> md >> so >> mo;
        dolazakNajkasniji = max(dolazakNajkasniji, sd * 60 + md);
        odlazakNajraniji = min(odlazakNajraniji, so * 60 + mo);
    }

    int trajanje = odlazakNajraniji - dolazakNajkasniji;
    if (trajanje > 0) {
        cout << trajanje / 60 << " " << trajanje % 60 << endl;
    } else {
        cout << "ne" << endl;
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Šta se traži

Brod sa kružnom linijom od t dana u luci je u danima t, 2t, 3t, .... Svi brodovi su zajedno u luci u prvom danu koji je deljiv svim trajanjima – to je njihov najmanji zajednički sadržalac (NZS).

2. NZS preko NZD

Za dva broja važi NZS(a, b) = a / NZD(a, b) * b. NZD računamo Euklidovim algoritmom: dok je b != 0, zamenjujemo (a, b) parom (b, a % b).

3. Više brojeva

NZS više brojeva računamo postepeno: krenemo od 1 i svaki učitani broj „ugradimo“ u dotadašnji rezultat.

4. Tip podataka

Rezultat može biti mnogo veći od najvećeg ulaznog broja (npr. za brojeve oko 360 i do pet brodova prelazi milijardu), pa koristimo long long. Deljenje radimo pre množenja da bi međurezultat bio što manji.

C++ rešenje

#include <iostream>
using namespace std;

long long nzd(long long a, long long b) {
    while (b != 0) {
        long long ostatak = a % b;
        a = b;
        b = ostatak;
    }
    return a;
}

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

    long long nzs = 1;
    for (int i = 0; i < n; i++) {
        long long dani;
        cin >> dani;
        nzs = nzs / nzd(nzs, dani) * dani;   // NZS(nzs, dani)
    }

    cout << nzs << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Zašto ne realni brojevi

Tip double pamti oko 15–16 cifara, a traži se i do 1000 decimala. Zato decimale računamo „pisanim deljenjem“ – cifru po cifru, samo sa celim brojevima.

2. Celobrojni deo

Ispišemo m / n (celobrojno deljenje), a zatim zarez. Preostaje ostatak ostatak = m % n.

3. Svaka sledeća decimala

Ostatak pomnožimo sa 10 (kao kad „spustimo nulu“). Sledeća decimala je ostatak / n, a novi ostatak ostatak % n. Ovo ponavljamo k puta.

4. Primer

Za 1 / 7: ostatak 1 → 10 : 7 = 1 (ostatak 3) → 30 : 7 = 4 (ostatak 2) → 20 : 7 = 2 (ostatak 6) → ... pa dobijamo 0,142857...

C++ rešenje

#include <iostream>
using namespace std;

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

    cout << m / n << ",";          // celobrojni deo količnika
    int ostatak = m % n;

    for (int i = 0; i < k; i++) {
        ostatak *= 10;
        cout << ostatak / n;       // sledeća decimala
        ostatak %= n;
    }
    cout << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Broj kao niska

Broj K učitamo kao nisku (string) i prolazimo kroz njene znakove, jedan po jedan.

2. Pravila za svaku cifru

Cifre 0–5 dodajemo trenutnoj šifri; cifra 6 završava šifru; cifre 7, 8 i 9 preskačemo.

3. Kraj broja

Kraj broja takođe završava šifru. Najlakše je da na nisku dodamo još jednu šesticu pa da se poslednja šifra završi na isti način kao i ostale.

4. Šifra mora da ima smisla

Prazna šifra (npr. dve šestice zaredom) se ne broji. Šifra sastavljena samo od nula predstavlja broj 0, što ne može biti šifra, pa se ni ona ne broji.

5. Ispis

Šifre čuvamo u vektoru. Pošto redosled nije bitan, ispisujemo ih od poslednje ka prvoj da bi izlaz odgovarao primeru (5 23).

C++ rešenje

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

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

    vector<string> sifre;
    string trenutna = "";

    for (char c : k + "6") {                 // dodatna šestica zatvara poslednju šifru
        if (c >= '0' && c <= '5') {
            trenutna += c;
        } else if (c == '6') {
            // šifra se završava; broj 0 ne može biti šifra
            bool samoNule = true;
            for (char x : trenutna) {
                if (x != '0') samoNule = false;
            }
            if (!trenutna.empty() && !samoNule) {
                sifre.push_back(trenutna);
            }
            trenutna = "";
        }
        // cifre 7, 8 i 9 se ignorišu
    }

    cout << "Sifre su:";
    for (int i = (int)sifre.size() - 1; i >= 0; i--) {   // redosled nije bitan
        cout << " " << sifre[i];
    }
    cout << endl;
    cout << "Poslate su " << sifre.size() << " sifre" << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Brojači pobeda

Za svaku ekipu uvodimo brojač pobeda i postavljamo ga na 0.

2. Tri runde

Za svaku rundu uporedimo poene dve ekipe: više poena znači da pobedniku povećamo brojač za 1, a pri jednakosti ne radimo ništa.

3. Pobednik

Ako neka ekipa ima strogo više pobeda od obe ostale, ona je pobednik. U svim ostalim slučajevima (dve ekipe izjednačene na vrhu ili sve tri izjednačene) ispisujemo DP.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int R11, R12, R21, R23, R32, R33;
    cin >> R11 >> R12 >> R21 >> R23 >> R32 >> R33;

    int p1 = 0, p2 = 0, p3 = 0;     // broj pobeda svake ekipe

    // runda 1: ekipe 1 i 2
    if (R11 > R12) p1++;
    else if (R11 < R12) p2++;

    // runda 2: ekipe 1 i 3
    if (R21 > R23) p1++;
    else if (R21 < R23) p3++;

    // runda 3: ekipe 2 i 3
    if (R32 > R33) p2++;
    else if (R32 < R33) p3++;

    if (p1 > p2 && p1 > p3) cout << 1 << endl;
    else if (p2 > p1 && p2 > p3) cout << 2 << endl;
    else if (p3 > p1 && p3 > p2) cout << 3 << endl;
    else cout << "DP" << endl;

    return 0;
}

Uputstvo — ideja rešenja

1. Koji senzori su u liniji

Neka je sredina sobe u nuli. U liniji sa rednim brojem i (počevši od 0) senzori su na rastojanjima 0, ±R, ±2R, ..., ±i·R od sredine, pa je tu 2i + 1 senzora.

2. Šta lik pokriva

Lik širine S pokriva deo poda od −S/2 do S/2. Senzor na rastojanju k·R je aktiviran ako je k·R ≤ S/2, odnosno 2·k·R ≤ S.

3. Najdalji aktivirani senzor

Nađemo najveće k za koje je 2·k·R ≤ S (petljom: povećavamo k dok uslov važi). Dalji senzori nikada nisu aktivirani, ma koliko linija bilo.

4. Zbir po linijama

U liniji i aktivirano je 2·min(i, k) + 1 senzora. Saberemo to za i od 0 do N − 1.

5. Realni brojevi

Poređenje realnih brojeva može da pogreši zbog zaokruživanja, pa uz S dodajemo mali dodatak 1e-9. Pretpostavka je da senzor koji lik samo dodiruje ivicom računamo kao aktiviran.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int n;
    double r, s;
    cin >> n >> r >> s;

    // Koliko je senzora na svakoj strani od sredine aktivirano (najviše):
    // senzor na k-tom mestu od sredine je udaljen k*r od sredine,
    // pa ga lik širine s dodiruje ako je k*r <= s/2.
    int k = 0;
    while ((k + 1) * 2 * r <= s + 1e-9) {
        k++;
    }

    int ukupno = 0;
    for (int i = 0; i < n; i++) {            // i = broj senzora levo od sredine u ovoj liniji
        int sa_svake_strane = (i < k) ? i : k;
        ukupno += 2 * sa_svake_strane + 1;
    }

    cout << ukupno << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Treći ugao

Zbir uglova je 180°, pa je treći ugao 180 − a − b.

2. Redosled provera

Prvo proveravamo da li je neki ugao jednak 90° (pravougli). Zatim da li je neki veći od 90° (tupougli). Ako nijedno ne važi, trougao je oštrougli.

3. Pažnja

Proveru ne radimo samo za unete uglove – i treći ugao može biti prav ili tup (primer 1 i 2).

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int c = 180 - a - b;       // treći ugao

    if (a == 90 || b == 90 || c == 90) {
        cout << "pravougli" << endl;
    } else if (a > 90 || b > 90 || c > 90) {
        cout << "tupougli" << endl;
    } else {
        cout << "ostrougli" << endl;
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Kolona i vrsta

Svaki kvadrat ima stranicu 100 piksela. Pikseli 1–100 su u prvoj koloni, 101–200 u drugoj, 201–300 u trećoj. Pošto se pikseli broje od 1, od koordinate oduzimamo 1: kolona = (x − 1) / 100 daje 0, 1 ili 2.

2. Zašto oduzimanje

Bez oduzimanja piksel 100 bi dao 100 / 100 = 1, tj. pogrešnu kolonu. Sa oduzimanjem je (100 − 1) / 100 = 0, što je tačno.

3. Isto za vrstu

vrsta = (y − 1) / 100, pri čemu se vrste broje odozdo naviše.

4. Redni broj kvadrata

Pre kvadrata u datoj vrsti nalazi se vrsta punih vrsta od po 3 kvadrata, pa je traženi broj vrsta * 3 + kolona + 1.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;

    int kolona = (x - 1) / 100;    // 0, 1 ili 2 (sa leva na desno)
    int vrsta = (y - 1) / 100;     // 0, 1 ili 2 (odozdo naviše)

    cout << vrsta * 3 + kolona + 1 << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Označimo nepoznatu

Neka je p broj poena u prvoj partiji.

2. Ostale partije preko p

Druga: p + 1042. Treća: p + (p + 1042) = 2p + 1042. Četvrta: (2p + 1042) / 2 = p + 521.

3. Rešenje

Dobili smo C = p + 521, odnosno p = C − 521. Program učita C i ispiše C − 521.

C++ rešenje

#include <iostream>
using namespace std;

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

    // Neka je p broj poena u prvoj partiji:
    //   druga partija:   p + 1042
    //   treća partija:   p + (p + 1042) = 2p + 1042
    //   četvrta partija: (2p + 1042) / 2 = p + 521
    // Dakle, c = p + 521, odnosno p = c - 521.
    cout << c - 521 << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Ključna ideja

Na ispravnom putokazu zbir a + b jednak je ukupnoj dužini puta od Agrada do Begrada, dakle isti za sve ispravne putokaze.

2. Tri ista, jedan drugačiji

Tri zbira su jednaka, a jedan se razlikuje. Treba naći onaj koji se razlikuje.

3. Analiza slučajeva

Ako su zbirovi prvog i drugog putokaza jednaki, netačan je treći ili četvrti: treći je netačan ako se razlikuje od prvog, inače je netačan četvrti. Ako se zbirovi prvog i drugog razlikuju, netačan je jedan od njih: ako je treći jednak prvom, netačan je drugi, inače prvi.

4. Tip podataka

Zbir dva broja manja od 10⁹ može preći granicu tipa int, zato koristimo long long.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    long long a[4], b[4], zbir[4];
    for (int i = 0; i < 4; i++) {
        cin >> a[i] >> b[i];
        zbir[i] = a[i] + b[i];       // trebalo bi da je isti za sve putokaze
    }

    if (zbir[0] == zbir[1]) {
        // prva dva se slažu, pa je netačan treći ili četvrti
        if (zbir[2] != zbir[0]) cout << 3 << endl;
        else cout << 4 << endl;
    } else {
        // jedan od prva dva je netačan; treći odlučuje koji
        if (zbir[2] == zbir[0]) cout << 2 << endl;
        else cout << 1 << endl;
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Koje su cifre proste

Jednocifreni prosti brojevi su 2, 3, 5 i 7. Cifre 0, 1, 4, 6, 8 i 9 nisu proste.

2. Izdvajanje cifara

Cifre broja izdvajamo odozgo nadole petljom: n % 10 je poslednja cifra, a n /= 10 je odbacuje.

3. Proizvod i slučaj bez prostih cifara

Proizvod počinje od 1 i množi se prostim ciframa. Pošto je 1 i proizvod „praznog skupa“, posebnom logičkom promenljivom pamtimo da li smo ijednu prostu cifru sreli. Ako nismo, ispisujemo -1.

C++ rešenje

#include <iostream>
using namespace std;

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

    long long proizvod = 1;
    bool imaProstih = false;

    while (n > 0) {
        int cifra = n % 10;
        // prosti brojevi među ciframa: 2, 3, 5 i 7
        if (cifra == 2 || cifra == 3 || cifra == 5 || cifra == 7) {
            proizvod *= cifra;
            imaProstih = true;
        }
        n /= 10;
    }

    if (imaProstih) cout << proizvod << endl;
    else cout << -1 << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Učitavanje cele linije

Pošto niska sadrži razmake, učitavamo je sa getline(cin, s), a ne sa cin >> s.

2. Prolazak kroz nisku

Indeksom i idemo s leva na desno. Razmak preskačemo. Ako je na poziciji i znak [, rečenica traje do prve zatvorene zagrade ]; inače je to običan početak reči koja traje do sledećeg razmaka (ili kraja niske).

3. Isecanje delova

Deo niske isecamo sa s.substr(početak, dužina). Za rečenicu isecamo sadržaj između zagrada, bez samih zagrada.

4. Nastavak

Posle obrade nastavljamo od prve pozicije iza reči, odnosno iza zatvorene zagrade.

C++ rešenje

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

int main() {
    string s;
    getline(cin, s);

    int n = s.size();
    int i = 0;
    while (i < n) {
        if (s[i] == ' ') {                      // razmake preskačemo
            i++;
        } else if (s[i] == '[') {               // rečenica: do zatvorene zagrade
            int j = i + 1;
            while (s[j] != ']') j++;
            cout << s.substr(i + 1, j - i - 1) << endl;
            i = j + 1;
        } else {                                // obična reč: do prvog razmaka
            int j = i;
            while (j < n && s[j] != ' ') j++;
            cout << s.substr(i, j - i) << endl;
            i = j;
        }
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Sporo rešenje

Proverom svakog para (dve petlje) dobijamo oko n²/2 poređenja, a za n = 105 to je 5 milijardi. Dovoljno za 50% poena, ali ne i za sve.

2. Sortiranje

Kada su poeni sortirani, svi takmičari koji sa datim takmičarem čine dobar par nalaze se u jednom neprekidnom bloku odmah ispred njega.

3. Dva pokazivača

Za svakog takmičara desno (redom) pomeramo levo udesno dok je poeni[desno] − poeni[levo] > k. Tada su svi takmičari od levo do desno − 1 dobri parovi sa takmičarem desno, pa dodajemo desno − levo.

4. Složenost i tip

Pokazivač levo samo napreduje, pa je posle sortiranja posao linearan: ukupno O(n log n). Broj parova može biti oko 5·10⁹, pa brojač mora biti long long.

C++ rešenje

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

int main() {
    int n, k;
    cin >> n;
    vector<int> poeni(n);
    for (int i = 0; i < n; i++) cin >> poeni[i];
    cin >> k;

    sort(poeni.begin(), poeni.end());

    long long parova = 0;
    int levo = 0;
    for (int desno = 0; desno < n; desno++) {
        // pomeramo levi kraj dok je razlika prevelika
        while (poeni[desno] - poeni[levo] > k) {
            levo++;
        }
        // takmičar "desno" čini dobar par sa svima iz [levo, desno)
        parova += desno - levo;
    }

    cout << parova << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Obim

Obim trougla je zbir tri stranice: a + b + c.

2. Najveći obim

Pamtimo najveći obim do sada u promenljivoj najveciObim (početna vrednost 0, jer su obimi pozitivni). Posle svakog učitanog trougla ažuriramo je sa max.

3. Pažnja

Trojke ne moramo posebno proveravati: zadatak garantuje da su sve trouglovi.

C++ rešenje

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

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

    int najveciObim = 0;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        najveciObim = max(najveciObim, a + b + c);
    }

    cout << najveciObim << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Koliko ko ima pobeda

U nokaut turniru sa 8 učesnika pobednik dobija 3 meča (četvrtfinale, polufinale, finale), finalista 2 meča (četvrtfinale, polufinale) i izgubi finale, polufinalisti koji su poraženi imaju 1 pobedu, a ostali 0.

2. Brojanje

Za svako ime pamtimo broj pobeda u rečniku map<string, int>. Pri čitanju svakog meča povećamo broj pobeda samo prvom imenu (pobedniku).

3. Rezultat

Pobednik turnira je ime sa 3 pobede, a drugoplasirani ime sa 2 pobede.

4. Alternativa

Isto se može zaključiti i bez broja pobeda: pobednik turnira je jedino ime koje se nikada ne pojavljuje kao poraženo.

C++ rešenje

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

int main() {
    map<string, int> pobede;            // ime -> broj osvojenih mečeva

    for (int i = 0; i < 7; i++) {
        string pobednik, poraz;
        cin >> pobednik >> poraz;
        pobede[pobednik]++;
    }

    string prvi, drugi;
    for (auto &par : pobede) {
        if (par.second == 3) prvi = par.first;    // pobednik turnira: 3 pobede
        if (par.second == 2) drugi = par.first;   // finalista: 2 pobede, a finale je izgubio
    }

    cout << prvi << endl << drugi << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Šta znači „bezbedno“

Neka je prvo dete na drvetu P, a drugo dete na drvetu Q. Deca trče rastojanje |PQ|. Krojač trči do bližeg od dva slobodna drveta, na rastojanje min(|KP|, |KQ|). Pošto krojač pobeđuje i kad stigne istovremeno, razmena je bezbedna samo ako je min(|KP|, |KQ|) > |PQ|.

2. Poređenje bez korenovanja

Rastojanje dve tačke je koren iz dx² + dy². Korenovanje nije potrebno jer su sva rastojanja nenegativna – dovoljno je porediti kvadrate rastojanja, i to celim brojevima (bez grešaka pri zaokruživanju). Kvadrat rastojanja može dostići oko 1,8·10⁹, pa koristimo long long.

3. Petlja po deci

Prvo dete je prvo u spisku. Za svako od preostalih n − 1 dece računamo tri kvadrata rastojanja i uvećavamo brojač ako je razmena bezbedna.

4. Provera na primeru

Za primer 1 razmena sa detetom na (14, 3) nije bezbedna jer je krojač drvetu na (14, 3) bliži nego što deca trče; za dete na (18, 15) rastojanja su jednaka, što znači da krojač stiže istovremeno i razmena nije bezbedna. Jedina bezbedna razmena je sa detetom na (8, 4).

C++ rešenje

#include <iostream>
using namespace std;

long long kvadrat(long long a, long long b, long long c, long long d) {
    // kvadrat rastojanja između tačaka (a, b) i (c, d)
    return (a - c) * (a - c) + (b - d) * (b - d);
}

int main() {
    long long kx, ky;
    int n;
    cin >> kx >> ky >> n;

    long long x[50], y[50];
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    int bezbedno = 0;
    for (int j = 1; j < n; j++) {                 // dete 0 je prvo dete
        long long izmedju = kvadrat(x[0], y[0], x[j], y[j]);   // koliko deca trče
        long long krojacDo0 = kvadrat(kx, ky, x[0], y[0]);
        long long krojacDoJ = kvadrat(kx, ky, x[j], y[j]);
        long long krojac = (krojacDo0 < krojacDoJ) ? krojacDo0 : krojacDoJ;

        // krojač mora da bude strogo dalje od bližeg drveta nego što deca trče
        if (krojac > izmedju) {
            bezbedno++;
        }
    }

    cout << bezbedno << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Šta je tražena dužina

Komad dužine d može da se iseče iz svakog preostalog kanapa samo ako d deli dužinu tog kanapa. Najveće takvo d je najveći zajednički delilac (NZD) svih preostalih dužina.

2. Sporo rešenje

Za svaki izbačeni kanap računati NZD ostalih zahteva O(N²) računanja NZD, što je prespor za N = 2·105.

3. Prefiksi i sufiksi

Izračunamo levo[i] – NZD prvih i kanapa, i desno[i] – NZD kanapa od pozicije i do kraja. Kada izbacimo kanap i, NZD ostalih je NZD(levo[i], desno[i+1]).

4. Početne vrednosti

NZD praznog skupa uzimamo kao 0 jer je NZD(0, x) = x.

5. Rezultat i tip

Od svih izbačenih kanapa biramo onaj sa najvećim dobijenim NZD. Vrednosti dostižu 10¹⁸, pa je long long obavezan.

C++ rešenje

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

long long nzd(long long a, long long b) {
    while (b != 0) {
        long long ostatak = a % b;
        a = b;
        b = ostatak;
    }
    return a;
}

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

    // levo[i]  = NZD prvih i kanapa,  desno[i] = NZD kanapa od pozicije i do kraja
    vector<long long> levo(n + 1, 0), desno(n + 2, 0);
    for (int i = 0; i < n; i++) levo[i + 1] = nzd(levo[i], a[i]);
    for (int i = n - 1; i >= 0; i--) desno[i] = nzd(desno[i + 1], a[i]);

    long long najbolje = 0;
    for (int i = 0; i < n; i++) {
        // izbacujemo kanap i: ostaju kanapi levo od njega i desno od njega
        long long dobijeno = nzd(levo[i], desno[i + 1]);
        if (dobijeno > najbolje) najbolje = dobijeno;
    }

    cout << najbolje << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Prva pomoć: publika

Jedan odgovor ima više glasova od svih ostalih zajedno ako ima više od polovine glasova. Pošto je ukupno 100 glasova, uslov je glasovi[i] > 50. Ako postoji takav odgovor, ispisujemo ga i završavamo program.

2. Druga pomoć: pola-pola

Tek tada učitavamo drugi red (dva slova). Glasove za slovo čitamo iz niza: glasovi[slovo - 'a']. Ako jedan od ta dva odgovora ima bar 20 glasova više, to je odgovor.

3. Treća pomoć: prijatelj

Ako nijedan uslov nije ispunjen, učitamo treći red i ispišemo slovo koje je prijatelj predložio.

4. Redosled učitavanja

Važno je da drugi i treći red učitavamo samo kada su potrebni – ulaz ih ne sadrži kada je odgovor poznat ranije.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    int glasovi[4];
    for (int i = 0; i < 4; i++) cin >> glasovi[i];

    // 1. pomoć: publika. Jedan odgovor mora imati više glasova od svih ostalih zajedno,
    // a pošto je ukupno 100 glasova, to znači više od 50.
    for (int i = 0; i < 4; i++) {
        if (glasovi[i] > 50) {
            cout << (char)('a' + i) << endl;
            return 0;
        }
    }

    // 2. pomoć: pola-pola
    char prvi, drugi;
    cin >> prvi >> drugi;
    int gp = glasovi[prvi - 'a'];
    int gd = glasovi[drugi - 'a'];

    if (gp - gd >= 20) {
        cout << prvi << endl;
        return 0;
    }
    if (gd - gp >= 20) {
        cout << drugi << endl;
        return 0;
    }

    // 3. pomoć: prijatelj
    char prijatelj;
    cin >> prijatelj;
    cout << prijatelj << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Četiri rasporeda

Papir može biti u dve orijentacije (širina i visina zamene mesta), a slike u dva rasporeda (jedna pored druge ili jedna ispod druge): ukupno 4 mogućnosti.

2. Jedna pored druge

Zajednička širina je w1 + w2, a potrebna visina je veća od dve visine, max(h1, h2). Raspored je ispravan ako je w1 + w2 ≤ širina papira i max(h1, h2) ≤ visina papira.

3. Jedna ispod druge

Potrebna širina je max(w1, w2), a visina h1 + h2. Raspored je ispravan ako je max(w1, w2) ≤ širina i h1 + h2 ≤ visina.

4. Orijentacije papira

Napravimo funkciju koja za zadate dimenzije papira prebroji ispravne rasporede (0, 1 ili 2) i pozovemo je dvaput: za (širina, visina) i za (visina, širina).

C++ rešenje

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

// Da li se slike dimenzija (w1,h1) i (w2,h2) mogu rasporediti
// na papir širine pw i visine ph, jedna pored druge ili jedna iznad druge?
int rasporedi(int pw, int ph, int w1, int h1, int w2, int h2) {
    int broj = 0;
    // jedna pored druge
    if (w1 + w2 <= pw && max(h1, h2) <= ph) broj++;
    // jedna ispod druge
    if (max(w1, w2) <= pw && h1 + h2 <= ph) broj++;
    return broj;
}

int main() {
    int sirina, visina, w1, h1, w2, h2;
    cin >> sirina >> visina >> w1 >> h1 >> w2 >> h2;

    int ukupno = 0;
    ukupno += rasporedi(sirina, visina, w1, h1, w2, h2);   // papir horizontalno
    ukupno += rasporedi(visina, sirina, w1, h1, w2, h2);   // papir vertikalno (okrenut)

    cout << ukupno << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Sporo rešenje

Za svaku poziciju množiti sve ostale elemente je O(n²), što je sporo za n = 105.

2. Ukupan proizvod i deljenje

Izračunamo proizvod svih elemenata i podelimo ga elementom na toj poziciji. Ovo ne radi ako u nizu ima nula – deljenje nulom nije dozvoljeno.

3. Nule

Proizvod računamo samo od elemenata različitih od nule i brojimo nule. Ako nula nema, rezultat na poziciji i je proizvod / a[i]. Ako je tačno jedna nula, rezultat na njenoj poziciji je proizvod, a svuda drugde 0. Ako ima dve ili više nula, svi su rezultati 0.

4. Tip podataka

Proizvod elemenata različitih od nule može biti 10 puta veći od traženih rezultata, pa koristimo long long.

C++ rešenje

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

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

    int nula = 0;                 // koliko ima nula u nizu
    long long proizvod = 1;       // proizvod svih elemenata različitih od nule
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) nula++;
        else proizvod *= a[i];
    }

    for (int i = 0; i < n; i++) {
        long long rezultat;
        if (nula >= 2) {
            rezultat = 0;                         // u svakom proizvodu ostaje bar jedna nula
        } else if (nula == 1) {
            rezultat = (a[i] == 0) ? proizvod : 0;
        } else {
            rezultat = proizvod / a[i];
        }
        cout << rezultat << (i + 1 < n ? " " : "\n");
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Sortiranje po udaljenosti

Niz sortiramo tako da brojevi sa manjom udaljenošću od x idu ispred. Za istu udaljenost ispred ide manji broj – to je upravo pravilo iz zadatka.

2. Funkcija poređenja

U sort prosleđujemo funkciju koja za dva broja p i q poredi |p − x| i |q − x|, a pri jednakosti p i q.

3. Prvih k

Posle ovog sortiranja traženih k brojeva su prvih k elemenata.

4. Neopadajući izlaz

Izlaz mora biti uređen neopadajuće, pa tih prvih k elemenata ponovo sortiramo (običnim poređenjem) pre ispisa.

C++ rešenje

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

int main() {
    int n, k;
    long long x;
    cin >> n >> k >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // sortiramo po udaljenosti od x, a pri istoj udaljenosti prvo manji broj
    sort(a.begin(), a.end(), [x](long long p, long long q) {
        long long dp = llabs(p - x), dq = llabs(q - x);
        if (dp != dq) return dp < dq;
        return p < q;
    });

    // uzimamo prvih k i ispisujemo ih neopadajuće
    sort(a.begin(), a.begin() + k);
    for (int i = 0; i < k; i++) {
        cout << a[i] << (i + 1 < k ? " " : "\n");
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Rastojanje između dve zgrade

Pošto su sve zgrade na istoj ulici, rastojanje između dve zgrade je apsolutna vrednost razlike njihovih koordinata: abs(a − b).

2. Čitanje bez niza

Dovoljno je da pamtimo koordinatu prethodne zgrade. Prvu zgradu učitamo odvojeno, a zatim za svaku sledeću dodamo abs(trenutna − prethodna) ukupnom putu i ažuriramo prethodna.

3. Slučaj n = 1

Petlja za preostale zgrade se tada ne izvršava, pa je rezultat 0 – bez posebne provere.

C++ rešenje

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

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

    int ukupno = 0;
    int prethodna;
    cin >> prethodna;               // prva zgrada

    for (int i = 1; i < n; i++) {
        int trenutna;
        cin >> trenutna;
        ukupno += abs(trenutna - prethodna);   // put od prethodne do ove zgrade
        prethodna = trenutna;
    }

    cout << ukupno << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Cifre u nizu

Četiri cifre učitamo u niz i sortiramo ih rastuće.

2. Najveći broj

Najveći broj dobijamo kada cifre poređamo opadajuće, tj. čitamo sortirani niz od kraja ka početku.

3. Najmanji broj

Najmanji broj dobijamo rastućim redosledom cifara, ali prva cifra ne sme biti 0. Zato pronađemo prvu cifru različitu od nule i zamenimo je sa cifrom na prvom mestu; ostale cifre ostaju u rastućem redosledu.

4. Razlika

Brojeve formiramo kao c0 · 1000 + c1 · 100 + c2 · 10 + c3 i ispišemo razliku najvećeg i najmanjeg.

5. Provera

Za cifre 0, 0, 1, 2: najveći je 2100, a najmanji 1002 (a ne 0012), pa je razlika 1098.

C++ rešenje

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

int main() {
    int c[4];
    for (int i = 0; i < 4; i++) cin >> c[i];

    sort(c, c + 4);                           // rastuće: c[0] <= c[1] <= c[2] <= c[3]

    // najveći broj: cifre od najveće ka najmanjoj
    int najveci = c[3] * 1000 + c[2] * 100 + c[1] * 10 + c[0];

    // najmanji broj: cifre rastuće, ali prva cifra ne sme biti 0
    int j = 0;
    while (c[j] == 0) j++;                    // prva cifra različita od nule (postoji bar jedna)
    swap(c[0], c[j]);
    int najmanji = c[0] * 1000 + c[1] * 100 + c[2] * 10 + c[3];

    cout << najveci - najmanji << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Table kao niska od 3 znaka

Svaki red učitamo kao string od 3 znaka; tada je t[i][j] znak u vrsti i i koloni j.

2. Osam linija

Pobedničkih linija ima osam: tri vrste, tri kolone i dve dijagonale. Za igrača p proveravamo da li su sva tri polja neke linije jednaka p.

3. Za oba igrača

Isti kod pokrećemo za 'x', a zatim za 'o'. Prazno polje * nikada nije pobednički znak jer proveravamo samo x i o.

4. Nerešeno

Ako ni jedan igrač nema liniju, ispisujemo nereseno.

C++ rešenje

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

int main() {
    string t[3];
    for (int i = 0; i < 3; i++) cin >> t[i];

    // proveravamo za oba igrača
    char igraci[2] = {'x', 'o'};
    for (char p : igraci) {
        bool pobedio = false;

        for (int i = 0; i < 3; i++) {
            if (t[i][0] == p && t[i][1] == p && t[i][2] == p) pobedio = true;   // vrsta i
            if (t[0][i] == p && t[1][i] == p && t[2][i] == p) pobedio = true;   // kolona i
        }
        if (t[0][0] == p && t[1][1] == p && t[2][2] == p) pobedio = true;       // glavna dijagonala
        if (t[0][2] == p && t[1][1] == p && t[2][0] == p) pobedio = true;       // sporedna dijagonala

        if (pobedio) {
            cout << p << endl;
            return 0;
        }
    }

    cout << "nereseno" << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Cela linija

Niska može da sadrži razmake, pa je učitavamo sa getline(cin, s). Običan cin >> s bi stao na prvom razmaku.

2. Klasifikacija znakova

Prolazimo kroz sve znakove. Znak je cifra ako je između '0' i '9', a slovo ako je između 'a' i 'z' ili između 'A' i 'Z'. Sve ostalo (razmaci, znakovi interpunkcije) ne brojimo.

3. Rezultat

Ispisujemo abs(cifre − slova) – apsolutnu vrednost, jer slova mogu biti i manje i više brojna od cifara.

C++ rešenje

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

int main() {
    string s;
    getline(cin, s);               // niska može da sadrži razmake

    int cifre = 0, slova = 0;
    for (char c : s) {
        if (c >= '0' && c <= '9') {
            cifre++;
        } else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            slova++;
        }
    }

    cout << abs(cifre - slova) << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Šta treba da znamo

Pitanje „koliko računa ima tačno x dinara“ možemo odmah da odgovorimo ako stalno čuvamo broj računa po stanju. Zato nam trebaju dve mape.

2. Dve mape

map<string, long long> stanje čuva stanje svakog korisnika (podrazumevano 0), a map<long long, int> brojRacuna čuva koliko računa ima dato stanje.

3. Početak

Na početku svih k korisnika ima 0 dinara, pa je brojRacuna[0] = k. To je važno: korisnici koje još nismo videli takođe se broje u upitu upit 0.

4. Uplata

Za operaciju ime x: staro stanje je stanje[ime]. Smanjimo brojRacuna[staro], postavimo novo stanje staro + x i povećamo brojRacuna[novo].

5. Upit

Za upit x ispisujemo brojRacuna[x]. Ako stanje x ne postoji u mapi, mapa ga automatski stvara sa vrednošću 0.

C++ rešenje

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

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

    map<string, long long> stanje;           // stanje računa svakog korisnika
    map<long long, int> brojRacuna;          // koliko računa ima tačno dato stanje
    brojRacuna[0] = k;                       // na početku svih k računa ima 0 dinara

    for (int i = 0; i < n; i++) {
        string rec;
        long long x;
        cin >> rec >> x;

        if (rec == "upit") {
            cout << brojRacuna[x] << endl;
        } else {
            long long staro = stanje[rec];   // ako korisnik nije viđen, stanje je 0
            brojRacuna[staro]--;             // račun napušta staro stanje ...
            stanje[rec] = staro + x;
            brojRacuna[staro + x]++;         // ... i prelazi u novo
        }
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Sporo rešenje

Za svaku zastavicu proveriti svaku rupu je O(m·n), što je 10¹⁰ poređenja – previše. Dovoljno je za prvu grupu primera (m, n ≤ 100).

2. Samo dve rupe su bitne

Ako su rupe sortirane, od svih rupa zastavici z mogu biti najbliže samo dve: prva rupa desno od nje (ili na njoj) i poslednja rupa levo od nje. Ako ni jedna od te dve nije na rastojanju ≤ d, nijedna rupa je ne ruši.

3. Binarna pretraga

Prvu rupu koja nije levo od zastavice nalazimo funkcijom lower_bound u O(log n). Rupa neposredno pre nje je najbliža leva.

4. Brojanje

Brojimo zastavice kod kojih nijedna od dve najbliže rupe nije dovoljno blizu. Složenost je O(n log n + m log n).

C++ rešenje

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

int main() {
    int m, n;
    cin >> m;
    vector<long long> zastavice(m);
    for (int i = 0; i < m; i++) cin >> zastavice[i];

    cin >> n;
    vector<long long> rupe(n);
    for (int i = 0; i < n; i++) cin >> rupe[i];

    long long d;
    cin >> d;

    sort(rupe.begin(), rupe.end());

    int preostalo = 0;
    for (int i = 0; i < m; i++) {
        long long z = zastavice[i];
        bool uruseno = false;

        // prva rupa koja nije levo od zastavice
        auto it = lower_bound(rupe.begin(), rupe.end(), z);
        if (it != rupe.end() && *it - z <= d) uruseno = true;          // najbliža desno
        if (it != rupe.begin() && z - *(it - 1) <= d) uruseno = true;  // najbliža levo

        if (!uruseno) preostalo++;
    }

    cout << preostalo << endl;
    return 0;
}