Priprema za državno takmičenje iz informatike

Uputstvo — ideja rešenja

1. Učitavanje tablice

Tablicu čuvamo u matrici znakova char tablica[3][3]. Cifre su zapisane bez razmaka, ali cin >> znak čita po jedan znak, pa učitavanje radi bez ikakvog dodatnog razdvajanja. Kada bismo cifre učitavali u int, ceo red (npr. 123) bio bi učitan kao jedan broj.

2. Dijagonale

U i-tom redu cifra glavne dijagonale je tablica[i][i], a cifra sporedne dijagonale tablica[i][2 - i].

3. Formiranje brojeva

Broj gradimo cifru po cifru, odozgo nadole: broj = broj * 10 + cifra. Cifru dobijamo iz znaka oduzimanjem znaka nula: znak - '0'.

4. Proizvod

Na kraju ispisujemo proizvod dva dobijena trocifrena broja. Najveći mogući proizvod je 999 · 999 = 998001, što staje u int.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    char tablica[3][3];

    // Cifre su zapisane bez razmaka, ali cin >> char čita jedan po jedan znak
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> tablica[i][j];
        }
    }

    int glavna = 0;      // broj od cifara glavne dijagonale
    int sporedna = 0;    // broj od cifara sporedne dijagonale

    for (int i = 0; i < 3; i++) {
        // cifra glavne dijagonale u i-tom redu je u koloni i
        glavna = glavna * 10 + (tablica[i][i] - '0');
        // cifra sporedne dijagonale u i-tom redu je u koloni 2 - i
        sporedna = sporedna * 10 + (tablica[i][2 - i] - '0');
    }

    cout << glavna * sporedna << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Učitavanje

Učitamo ceo broj. Zbir kvadrata inicijalizujemo na 0 pre početka petlje.

2. Izdvajanje cifara

Petlja while (broj > 0): cifra na desnom kraju je broj % 10, a broj / 10 uklanja tu cifru. Postupak se ponavlja dok ostatak broja ne postane 0.

3. Provera parnosti

Cifra je neparna ako je cifra % 2 != 0.

4. Zbir

Za svaku neparnu cifru zbiru dodamo njen kvadrat cifra * cifra.

C++ rešenje

#include <iostream>
using namespace std;

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

    int zbir = 0;                  // zbir kvadrata neparnih cifara, na početku 0
    while (broj > 0) {
        int cifra = broj % 10;     // cifra na desnom kraju
        broj = broj / 10;          // uklanja cifru na desnom kraju

        if (cifra % 2 != 0) {      // da li je cifra neparna
            zbir += cifra * cifra;
        }
    }

    cout << zbir << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Funkcija za broj delilaca

Napravimo funkciju brojDelilaca(n). Ona petljom prolazi kroz brojeve od 1 do n i broji one koji dele n (uslov n % i == 0).

2. Glavna petlja

Posle učitavanja prvog člana ponavljamo korak N − 1 puta (prvi član je već poznat): novi član je clan + brojDelilaca(clan).

3. Ispis

Posle petlje ispisujemo poslednji dobijeni član.

4. Provera na primeru

Za a1 = 2: 2 ima delioce 1 i 2 (2 + 2 = 4), 4 ima delioce 1, 2, 4 (4 + 3 = 7), 7 ima delioce 1 i 7 (7 + 2 = 9).

C++ rešenje

#include <iostream>
using namespace std;

// Broj delilaca prirodnog broja n
int brojDelilaca(int n) {
    int br = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {          // i je delilac broja n
            br++;
        }
    }
    return br;
}

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

    int clan = a1;                 // trenutni član niza
    for (int i = 1; i < n; i++) {  // potrebno je n - 1 koraka do n-tog člana
        clan = clan + brojDelilaca(clan);
    }

    cout << clan << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Prva pojava

Prva pojava broja n je u sredini reda n. Pre tog reda ima (n − 1)² članova, pa je pozicija (n − 1)² + n. Za k = 1 to je odgovor.

2. Ostale pojave

Posle reda n svaki red ima po dve pojave: prva (leva) je na poziciji (M − 1)² + n, a druga (desna) na poziciji (M − 1)² + 2M − n, gde je M redni broj reda.

3. Koji red

Za k ≥ 2 neka je j = k − 1 broj pojava posle prve. Pojave j = 1, 2 su u redu n + 1, pojave j = 3, 4 u redu n + 2 itd., dakle red je M = n + (j + 1) / 2. Ako je j neparno, tražena je leva pojava, a ako je parno desna.

4. Simulacija ili formula

Rešenje 1 prolazi red po red i „troši“ pojave (po dve u svakom redu), a rešenje 2 direktno računa red i poziciju formulom, bez petlje.

5. Tip podataka

Pozicija može biti reda (1,5·106)² ≈ 2,25·1012, što ne staje u int. Zato koristimo long long.

Rešenje 1: red po red (simulacija)

#include <iostream>
using namespace std;

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

    // Red M ima 2M - 1 članova, pa je pre reda M ukupno (M-1)^2 članova.
    // Broj n se prvi put javlja u redu n (samo jednom, u sredini),
    // a u svakom narednom redu M > n javlja se po dva puta:
    // na mestu n (sleva) i na mestu 2M - n.
    long long red = n;                 // red u kome tražimo pojavljivanje
    long long preostalo = k - 1;       // pojavljivanja posle prvog (u redu n)

    while (preostalo > 0) {
        red++;                         // prelazimo u sledeći red, koji ima 2 pojavljivanja
        if (preostalo >= 2) {
            preostalo -= 2;            // preskačemo oba pojavljivanja iz ovog reda
        } else {
            break;                     // tražena pojava je prva u ovom redu
        }
    }

    long long pre = (red - 1) * (red - 1);   // broj članova pre ovog reda
    long long pozicija;

    if (red == n) {
        pozicija = pre + n;                  // jedina pojava u sredini reda n
    } else if (preostalo == 1) {
        pozicija = pre + n;                  // leva pojava u redu
    } else {
        pozicija = pre + 2 * red - n;        // desna pojava u redu
    }

    cout << pozicija << endl;
    return 0;
}

Rešenje 2: formula

#include <iostream>
using namespace std;

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

    long long pozicija;
    if (k == 1) {
        // prva pojava: sredina reda n
        pozicija = (n - 1) * (n - 1) + n;
    } else {
        long long j = k - 1;               // koliko pojava posle prve
        long long red = n + (j + 1) / 2;   // po dve pojave u svakom redu posle n-tog
        long long pre = (red - 1) * (red - 1);
        if (j % 2 == 1) {
            pozicija = pre + n;            // neparno j: leva pojava u redu
        } else {
            pozicija = pre + 2 * red - n;  // parno j: desna pojava u redu
        }
    }

    cout << pozicija << endl;
    return 0;
}

Uputstvo — ideja rešenja

I način: metoda grube sile

Napravimo funkciju koja vraća broj delilaca prosleđenog broja: petljom menjamo delilac d od 1 do samog broja i brojimo one za koje je broj deljiv sa d. U glavnom delu petljom prolazimo od a do b i brojimo one brojeve za koje funkcija vrati neparnu vrednost. Ovo je sporo već za male granice (za b = 1015 bi trajalo godinama).

II način: optimizovan

Delioci se grupišu u parove (d, x / d). Parovi uvek imaju dva različita broja, osim kada je d = x / d, tj. kada je x potpun kvadrat. Dakle neparan broj delilaca imaju samo potpuni kvadrati. Umesto brojanja delilaca, napravimo funkciju koja proverava da li je broj potpun kvadrat. I dalje prolazimo kroz sve brojeve od a do b.

III način: potpuno optimizovan

Ne proveravamo sve brojeve od a do b, nego odredimo najmanji i najveći ceo broj čiji se kvadrat nalazi u intervalu. Zatim brojimo cele brojeve između njih. Petlja ima oko √b ≈ 3·107 koraka, što je prihvatljivo.

IV način: formula

Potpunih kvadrata u [1, x] ima ⌊√x⌋, pa u [a, b] ih ima ⌊√b⌋ − ⌊√(a − 1)⌋. Ovo se računa u konstantnom vremenu.

Pažnja pri korenovanju

Funkcija sqrt radi sa realnim brojevima i za velike vrednosti može dati rezultat koji je za 1 manji ili veći od tačnog. Zato dobijeni ceo broj k proveravamo i korigujemo dok ne važi k² ≤ x < (k + 1)². Za brojeve do 10¹⁵ proizvodi staju u long long.

I način (gruba sila)

#include <iostream>
using namespace std;

// Broj delilaca broja x (metoda grube sile)
long long brojDelilaca(long long x) {
    long long br = 0;
    for (long long d = 1; d <= x; d++) {
        if (x % d == 0) br++;
    }
    return br;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long brojac = 0;
    for (long long x = a; x <= b; x++) {
        if (brojDelilaca(x) % 2 == 1) {      // neparan broj delilaca
            brojac++;
        }
    }

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

II način (provera kvadrata)

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

// Samo potpuni kvadrati imaju neparan broj delilaca
bool potpunKvadrat(long long x) {
    long long k = (long long)sqrtl((long double)x);
    // ispravka eventualne greške pri zaokruživanju
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k * k == x;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long brojac = 0;
    for (long long x = a; x <= b; x++) {
        if (potpunKvadrat(x)) brojac++;
    }

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

III način (samo kvadrati)

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

// Najveći ceo broj k takav da je k * k <= x
long long celiKoren(long long x) {
    long long k = (long long)sqrtl((long double)x);
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k;
}

int main() {
    long long a, b;
    cin >> a >> b;

    // najmanji k sa k * k >= a
    long long prvi = celiKoren(a);
    if (prvi * prvi < a) prvi++;

    // najveći k sa k * k <= b
    long long poslednji = celiKoren(b);

    // proveravamo samo kvadrate od prvi * prvi do poslednji * poslednji
    long long brojac = 0;
    for (long long k = prvi; k <= poslednji; k++) {
        brojac++;                      // k * k je u intervalu [a, b]
    }

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

IV način (formula)

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

long long celiKoren(long long x) {
    if (x <= 0) return 0;
    long long k = (long long)sqrtl((long double)x);
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k;
}

int main() {
    long long a, b;
    cin >> a >> b;

    // Kvadrata u [1, b] ima celiKoren(b), a u [1, a - 1] ima celiKoren(a - 1)
    cout << celiKoren(b) - celiKoren(a - 1) << endl;
    return 0;
}

Uputstvo — ideja rešenja

I način: ugnježdene petlje

Spoljašnja petlja ide kroz N deljenja, a unutrašnja učitava k karata. Svaku kartu poredimo sa prethodnom iz istog deljenja. Ako je tekuća manja od prethodne, deljenje je neispravno. Važno je da se i posle greške učitaju sve preostale karte tog deljenja, da bi se ulaz ispravno čitao.

II način: vektori

Karte jednog deljenja učitamo u vektor. Napravimo kopiju vektora i sortiramo samo kopiju. Ako se kopija razlikuje od originala, original nije bio sortiran, pa je Baja pogrešio.

Brojanje

U oba načina brojač neispravnih deljenja povećavamo za 1 svaki put kada deljenje nije neopadajuće složeno.

I način (ugnježdene petlje)

#include <iostream>
using namespace std;

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

    int neispravnih = 0;
    for (int deljenje = 0; deljenje < n; deljenje++) {
        int prethodna;
        cin >> prethodna;              // prva karta u deljenju
        bool uredu = true;

        for (int i = 1; i < k; i++) {
            int tekuca;
            cin >> tekuca;             // učitavamo sve karte, čak i posle greške
            if (tekuca < prethodna) {  // nije neopadajuće
                uredu = false;
            }
            prethodna = tekuca;
        }

        if (!uredu) neispravnih++;
    }

    cout << neispravnih << endl;
    return 0;
}

II način (vektori)

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

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

    int neispravnih = 0;
    for (int deljenje = 0; deljenje < n; deljenje++) {
        vector<int> karte(k);
        for (int i = 0; i < k; i++) cin >> karte[i];

        vector<int> sortirane = karte;               // kopija originalnog niza
        sort(sortirane.begin(), sortirane.end());    // sortiramo samo kopiju

        if (sortirane != karte) {                    // različiti => Baja je pogrešio
            neispravnih++;
        }
    }

    cout << neispravnih << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Učitavanje

Učitamo n i niz poena (opadajući poredak), zatim m i za svako pitanje prag.

2. Šta se traži

Pošto su poeni sortirani od najvećeg ka najmanjem, takmičari koji prolaze čine početak niza. Traženi broj je indeks prve pozicije na kojoj je broj poena manji od praga (ili n ako takve pozicije nema).

3. Linearna pretraga

Za svako pitanje krećemo od početka niza i brojimo takmičare dok je poeni[i] >= prag. U najgorem slučaju to je n · m = 2,5·109 koraka.

4. Binarna pretraga

Zbog sortiranosti možemo da prepolovimo niz u svakom koraku: ako je srednji element ≥ prag, svi levo od njega takođe prolaze, pa traženu granicu tražimo desno; inače levo. Svako pitanje tada traje O(log n).

Rešenje 1: linearna pretraga

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

int main() {
    int n;
    cin >> n;
    vector<int> poeni(n);             // poeni su sortirani od najvećeg ka najmanjem
    for (int i = 0; i < n; i++) cin >> poeni[i];

    int m;
    cin >> m;
    for (int q = 0; q < m; q++) {
        int prag;
        cin >> prag;

        // linearna pretraga: brojimo takmičare sa poenima >= prag
        int broj = 0;
        while (broj < n && poeni[broj] >= prag) {
            broj++;
        }
        cout << broj << "\n";
    }
    return 0;
}

Rešenje 2: binarna pretraga

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

int main() {
    int n;
    cin >> n;
    vector<int> poeni(n);             // opadajući poredak
    for (int i = 0; i < n; i++) cin >> poeni[i];

    int m;
    cin >> m;
    for (int q = 0; q < m; q++) {
        int prag;
        cin >> prag;

        // binarna pretraga prve pozicije na kojoj je poeni[pozicija] < prag
        int levo = 0, desno = n;      // traženi indeks je u [levo, desno]
        while (levo < desno) {
            int sredina = (levo + desno) / 2;
            if (poeni[sredina] >= prag) {
                levo = sredina + 1;   // prolaze i svi levo od sredine, tražimo dalje desno
            } else {
                desno = sredina;      // sredina je već ispod praga
            }
        }
        cout << levo << "\n";         // levo je ujedno broj takmičara koji prolaze
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Učitavanje

Učitamo n i petljom n puta učitamo visinu (int) i pol (char).

2. Dva maksimuma

Pamtimo posebno najveću visinu dečaka i posebno najveću visinu devojčica. Za svakog učenika, u zavisnosti od pola, ažuriramo odgovarajući maksimum.

3. Poređenje

Na kraju poredimo dva maksimuma i ispisujemo traženu poruku: oznaku pola višeg učenika i razliku, ili znak =.

C++ rešenje

#include <iostream>
using namespace std;

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

    int najvisiDecak = 0, najvisaDevojcica = 0;
    for (int i = 0; i < n; i++) {
        int visina;
        char pol;
        cin >> visina >> pol;

        if (pol == 'm') {
            if (visina > najvisiDecak) najvisiDecak = visina;
        } else if (pol == 'z') {
            if (visina > najvisaDevojcica) najvisaDevojcica = visina;
        }
    }

    if (najvisiDecak > najvisaDevojcica) {
        cout << "m " << najvisiDecak - najvisaDevojcica << endl;
    } else if (najvisaDevojcica > najvisiDecak) {
        cout << "z " << najvisaDevojcica - najvisiDecak << endl;
    } else {
        cout << "=" << endl;
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Ukupan broj strana

Učitamo poglavlja u niz i usput sabiramo ukupan broj strana ukupno.

2. Razlika za jednu podelu

Ako je u prvom delu (poglavlja 0 do i) levo strana, u drugom je ukupno − levo. Razlika je |ukupno − 2·levo|.

3. Najbolja podela

Za svako i od 0 do n − 2 (iza poslednjeg poglavlja se ne deli) povećavamo levo i računamo razliku. Pamtimo najmanju razliku i poglavlje na kome je dobijena.

4. Jednake razlike

Poglavlje menjamo samo kada je razlika strogo manja od dotadašnje najmanje. Tako pri jednakosti ostaje ranije poglavlje, kako zadatak zahteva.

C++ rešenje

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

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

    int levo = 0;                  // broj strana u poglavljima 0..i
    int najmanjaRazlika = ukupno + 1;
    int najboljePoglavlje = 0;

    // podela se vrši iza poglavlja i, pa je poslednja moguća podela iza n - 2
    for (int i = 0; i < n - 1; i++) {
        levo += strane[i];
        int desno = ukupno - levo;
        int razlika = abs(desno - levo);

        // strogo manja razlika: pri jednakosti ostaje raniji (kraći prvi deo)
        if (razlika < najmanjaRazlika) {
            najmanjaRazlika = razlika;
            najboljePoglavlje = i;
        }
    }

    cout << najboljePoglavlje << endl;
    return 0;
}

Uputstvo — ideja rešenja

Ideja

Cifre su strogo rastuće gledano sleva udesno kada je svaka cifra strogo manja od cifre desno od nje. Ekvivalentno, gledano zdesna ulevo, cifre su strogo opadajuće.

Rešenje 1: cifre sa desna

Cifre izdvajamo od poslednje (x % 10), a x /= 10 je uklanja. Pamtimo prethodnu (desnu) cifru, na početku je to vrednost 10, veća od svake cifre. Ako je tekuća cifra veća ili jednaka prethodnoj, brojevi nisu rastući i petlju prekidamo. Time se izbegava računanje broja cifara.

Rešenje 2: niska

Broj učitamo kao nisku. Susedne znakove poredimo operatorom <=: znakovi cifara su poređani istim redom kao i cifre, pa je poređenje ispravno.

Rešenje 1: cifre sa desna

#include <iostream>
using namespace std;

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

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

        // Idemo od cifre najmanje težine (zdesna ulevo). Cifre su strogo rastuće
        // gledano sleva, ako su strogo opadajuće gledano zdesna.
        int x = broj;
        int prethodna = 10;        // veća od svake cifre
        bool rastuce = true;

        while (x > 0) {
            int cifra = x % 10;
            if (cifra >= prethodna) {   // leva cifra nije manja od desne
                rastuce = false;
                break;
            }
            prethodna = cifra;
            x /= 10;
        }

        if (rastuce) {
            cout << broj << "\n";
        }
    }
    return 0;
}

Rešenje 2: broj kao niska

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

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

    for (int i = 0; i < n; i++) {
        string broj;
        cin >> broj;                // broj učitavamo kao nisku cifara

        bool rastuce = true;
        for (size_t j = 1; j < broj.size(); j++) {
            if (broj[j] <= broj[j - 1]) {   // cifre se porede kao znakovi
                rastuce = false;
                break;
            }
        }

        if (rastuce) {
            cout << broj << "\n";
        }
    }
    return 0;
}

Uputstvo — ideja rešenja

Rešenje 1: dve petlje

Sortiramo visine rastuće. Za svaku visinu v[i] prolazimo kroz sledeće v[j]. Ako je razlika jednaka r, uvećamo broj parova, a ako je veća od r, prekidamo unutrašnju petlju jer će sve sledeće razlike biti još veće. Za 25 test-primera sa velikim brojem istih visina ovo može biti sporo.

Rešenje 2: binarna pretraga

Sortiramo visine. Za svaku visinu v[i] tražimo koliko ima elemenata jednakih v[i] + r. Pošto je niz sortiran, ti elementi čine jedan neprekidan blok, a funkcija equal_range binarnom pretragom nalazi njegov početak i kraj. Broj elemenata bloka dodajemo rezultatu. Ovako se pravilno broje i ponovljene visine.

Rešenje 3: brojanje

Visine su ograničene na 100000, pa možemo prebrojati koliko učenika ima svaku visinu u nizu broj[h]. Za svaku visinu h broj parova (h, h + r) je broj[h] · broj[h + r]. Rezultat sabiramo po svim visinama. Nije potrebno sortiranje.

Tip podataka

Broj parova može da bude i veći od 10⁹ (npr. ako polovina učenika ima jednu visinu, a druga polovina visinu za r veću), pa brojač treba da bude long long.

Rešenje 1: dve petlje

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

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

    sort(v.begin(), v.end());        // rastući poredak visina

    long long parova = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int razlika = v[j] - v[i];
            if (razlika == r) {
                parova++;
            } else if (razlika > r) {
                break;               // sve dalje razlike su još veće
            }
        }
    }

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

Rešenje 2: binarna pretraga

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

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

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

    long long parova = 0;
    for (int i = 0; i < n; i++) {
        // binarnom pretragom nalazimo sve elemente jednake v[i] + r
        // (oni su uvek desno od i, jer je r >= 1)
        auto opseg = equal_range(v.begin(), v.end(), v[i] + r);
        parova += opseg.second - opseg.first;   // koliko ih ima
    }

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

Rešenje 3: prebrojavanje po visinama

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

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

    const int MAKS = 100000;                 // najveća moguća visina
    vector<long long> broj(MAKS + 1, 0);     // broj[h] = koliko učenika ima visinu h
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        broj[h]++;
    }

    // Za svaku visinu h, parova (h, h + r) ima broj[h] * broj[h + r]
    long long parova = 0;
    for (int h = 1; h + r <= MAKS; h++) {
        parova += broj[h] * broj[h + r];
    }

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

Uputstvo — ideja rešenja

1. Sortiranje

Cene sortiramo opadajuće, da bismo ih obrađivali od najskupljeg ka najjeftinijem. U C++ za to služi sort sa funkcijom poređenja greater<int>().

2. Obilazak

Za svaki predmet proveravamo da li je njegova cena manja ili jednaka preostalom novcu. Ako jeste, oduzimamo je od ostatka.

3. Ispis

Posle obilaska svih predmeta ispisujemo ostatak.

C++ rešenje

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

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

    // od najskupljeg ka najjeftinijem
    sort(cene.begin(), cene.end(), greater<int>());

    int ostatak = novac;
    for (int i = 0; i < n; i++) {
        if (cene[i] <= ostatak) {      // ako ima dovoljno novca, predmet se kupuje
            ostatak -= cene[i];
        }
    }

    cout << ostatak << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Rekurzivna funkcija

Funkcija formiraj(i) popunjava poziciju i, a pozicije 0..i − 1 su već popunjene.

2. Izlaz iz rekurzije

Kada je i == n, svi elementi su postavljeni: ispisujemo niz i vraćamo se nazad.

3. Grananje

Prvo upisujemo 0 i pozivamo formiraj(i + 1). Zatim, ako je i == 0 ili je prethodni element 0, upisujemo 1 i ponovo pozivamo formiraj(i + 1).

4. Redosled

Zbog toga što uvek prvo ispitujemo nulu, a zatim jedinicu, nizovi se ispisuju u rastućem (leksikografskom) poretku.

C++ rešenje

#include <iostream>
using namespace std;

int n;
int niz[10];

// Ispis formiranog binarnog niza
void ispisi() {
    for (int i = 0; i < n; i++) {
        cout << niz[i];
    }
    cout << "\n";
}

// Popunjava poziciju i; pozicije 0..i-1 su već popunjene
void formiraj(int i) {
    if (i == n) {                    // niz je potpun
        ispisi();
        return;
    }

    niz[i] = 0;                      // nula se uvek može upisati
    formiraj(i + 1);

    // jedinica sme samo ako prethodni element nije jedinica
    if (i == 0 || niz[i - 1] == 0) {
        niz[i] = 1;
        formiraj(i + 1);
    }
}

int main() {
    cin >> n;
    formiraj(0);
    return 0;
}

Uputstvo — ideja rešenja

Rešenje 1: svi segmenti

Fiksiramo početak i, a zatim petljom povećavamo kraj j i na tekući zbir dodajemo promena[j]. Svaki put kada je zbir jednak z, povećavamo brojač. Ovo prolazi manje testove.

Rešenje 2: prefiksni zbirovi

Neka je P[j] zbir prvih j promena (P[0] = 0). Zbir segmenta od dana i + 1 do dana j je P[j] − P[i]. Segment ima zbir z kada je P[i] = P[j] − z.

Brojanje

Kako idemo kroz dane, održavamo mapu videno koja za svaku vrednost prefiksnog zbira pamti koliko se puta do sada pojavila. Za svako j rezultatu dodajemo videno[P[j] − z], a zatim upišemo i P[j]. Na početku je videno[0] = 1 (prazan prefiks).

Tip podataka

Broj segmenata može da bude oko 1,25·10⁹, što prelazi granicu tipa int, pa brojač mora biti long long.

Rešenje 1: svi segmenti

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

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

    long long brojac = 0;
    for (int i = 0; i < n; i++) {        // početak perioda
        int zbir = 0;
        for (int j = i; j < n; j++) {    // kraj perioda
            zbir += promena[j];
            if (zbir == z) brojac++;
        }
    }

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

Rešenje 2: prefiksni zbirovi i mapa

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

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

    // prefiks[j] = zbir prvih j promena. Period (i, j] ima zbir prefiks[j] - prefiks[i].
    // Zato za svaki prefiks tražimo koliko ranijih prefiksa ima vrednost (prefiks - z).
    map<int, int> videno;
    videno[0] = 1;                  // prazan prefiks (pre prvog dana)

    int prefiks = 0;
    long long brojac = 0;
    for (int i = 0; i < n; i++) {
        int promena;
        cin >> promena;
        prefiks += promena;

        auto it = videno.find(prefiks - z);
        if (it != videno.end()) {
            brojac += it->second;
        }
        videno[prefiks]++;
    }

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

Uputstvo — ideja rešenja

Rešenje 1: svi brojevi

U petlji od a do b proveravamo uslov i % c == 0 i brojimo. Za b do 10¹⁵ to je previše koraka.

Rešenje 2: koraci od c

Prvi umnožak broja c koji je ≥ a je (a + c − 1) / c * c. Od njega idemo u koracima od c do b i brojimo. Za mali delilac c (npr. 2) i dalje ima previše koraka.

Rešenje 3: formula

Umnožaka broja c među brojevima od 1 do x ima x / c (celobrojno deljenje). Zato je broj umnožaka u [a, b] jednak b / c − (a − 1) / c. Računa se u konstantnom vremenu.

Tip podataka

Brojevi dostižu 10¹⁵, pa je potreban 64-bitni tip, npr. unsigned long long ili long long.

Čitanje iz datoteke (pri testiranju)

Prilikom vežbanja primere možete čitati iz datoteke umesto sa standardnog ulaza, ako na početak funkcije main dodate freopen("deljivi.01.in", "r", stdin); (i #include <cstdio>). Ovu liniju treba ukloniti pre predaje rešenja.

Rešenje 1: svi brojevi

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    unsigned long long brojac = 0;
    for (unsigned long long i = a; i <= b; i++) {   // proveravamo svaki broj
        if (i % c == 0) {
            brojac++;
        }
    }

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

Rešenje 2: koraci od c

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    // prvi umnožak broja c koji nije manji od a
    unsigned long long i = (a + c - 1) / c * c;

    unsigned long long brojac = 0;
    while (i <= b) {
        brojac++;
        i += c;                      // sledeći umnožak je za c veći
    }

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

Rešenje 3: formula

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    // Umnožaka broja c u [1, x] ima x / c (celobrojno deljenje).
    // U [a, b] ih ima: (u [1, b]) - (u [1, a - 1]).
    unsigned long long rezultat = b / c - (a - 1) / c;

    cout << rezultat << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Ulaz

Učitamo težine četiri torbe i nosivosti dva putnika.

2. Rekurzija

Funkcija resi(i, kap1, kap2, br1, br2) obrađuje torbu sa rednim brojem i. Parametri kap1 i kap2 su preostale nosivosti putnika, a br1 i br2 broj torbi koje već nose (najviše 2).

3. Tri mogućnosti

Za torbu i razmatramo: (1) niko je ne nosi (njenu težinu dodajemo „neponetom“ delu); (2) prvi putnik je nosi – ako ima slobodnu ruku i dovoljno nosivosti; (3) drugi putnik je nosi, pod istim uslovima. Funkcija vraća najmanji ukupni teret koji ostaje neponet.

4. Kraj rekurzije

Kada su sve četiri torbe obrađene (i == 4), nema više neponetog tereta, pa vraćamo 0.

5. Broj mogućnosti

Postoji najviše 34 = 81 načina da se torbe rasporede, pa je ovakvo potpuno ispitivanje (pretraga svih mogućnosti) veoma brzo.

C++ rešenje

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

int tezina[4];      // težine torbi

// Minimalna težina torbi koje neće biti poneti, ako su torbe 0..i-1 već raspoređene.
// kap1, kap2 - preostala nosivost putnika, br1, br2 - broj torbi koje već nose
int resi(int i, int kap1, int kap2, int br1, int br2) {
    if (i == 4) {
        return 0;                    // sve torbe su obrađene
    }

    // 1) torbu i niko ne nosi (potrebna je tuđa pomoć)
    int najbolje = tezina[i] + resi(i + 1, kap1, kap2, br1, br2);

    // 2) torbu nosi prvi putnik (ako ima mesta u ruci i nosivosti)
    if (br1 < 2 && tezina[i] <= kap1) {
        najbolje = min(najbolje, resi(i + 1, kap1 - tezina[i], kap2, br1 + 1, br2));
    }

    // 3) torbu nosi drugi putnik
    if (br2 < 2 && tezina[i] <= kap2) {
        najbolje = min(najbolje, resi(i + 1, kap1, kap2 - tezina[i], br1, br2 + 1));
    }

    return najbolje;
}

int main() {
    for (int i = 0; i < 4; i++) cin >> tezina[i];
    int p1, p2;
    cin >> p1 >> p2;

    cout << resi(0, p1, p2, 0, 0) << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Šta je oscilovanje

Podniz osciluje ako se smer promene stalno menja: pa raste, pa opada, pa raste... Jednaki susedni elementi prekidaju oscilovanje (nema ni povećanja ni smanjenja).

2. Smer promene

Za svaka dva susedna merenja određujemo smer: +1 ako brzina raste, −1 ako opada, 0 ako je ista.

3. Dužina trenutnog podniza

Pamtimo dužinu trenutna trenutnog oscilujućeg podniza i smer poslednje promene. Ako je novi smer 0, dužina se vraća na 1. Ako je novi smer suprotan prethodnom, dužina raste za 1. U ostalim slučajevima (isti smer ili prethodno nije bilo promene) podniz počinje od prethodnog elementa, pa je dužina 2.

4. Najduži podniz

Pamtimo najveću vrednost dužine najduza. Ako je najduza ≥ k, ispisujemo da, inače ne; u drugom redu ispisujemo najduza.

5. Brzina

Brojeva ima do milion, pa uključujemo brže čitanje: ios::sync_with_stdio(false); cin.tie(nullptr);. Nije potrebno čuvati ceo niz – dovoljna je prethodna vrednost.

C++ rešenje

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);     // brz ulaz, jer ima do milion brojeva
    cin.tie(nullptr);

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

    double prethodna;
    cin >> prethodna;

    int trenutna = 1;                // dužina trenutnog oscilujućeg podniza
    int najduza = 1;
    int smer = 0;                    // smer poslednje promene: +1 raste, -1 opada, 0 nema

    for (int i = 1; i < n; i++) {
        double x;
        cin >> x;

        int novi;                    // smer promene prethodna -> x
        if (x > prethodna) novi = 1;
        else if (x < prethodna) novi = -1;
        else novi = 0;

        if (novi == 0) {
            trenutna = 1;            // jednaki susedi prekidaju oscilovanje
        } else if (smer != 0 && novi == -smer) {
            trenutna++;              // smer se promenio: oscilovanje se nastavlja
        } else {
            trenutna = 2;            // novi početak: prethodna i x čine podniz dužine 2
        }
        smer = novi;
        prethodna = x;

        if (trenutna > najduza) najduza = trenutna;
    }

    cout << (najduza >= k ? "da" : "ne") << "\n" << najduza << "\n";
    return 0;
}

Uputstvo — ideja rešenja

1. Podaci o patikama

Cene su manje od 50000, pa patike možemo grupisati po ceni: za svaku cenu c čuvamo vektor naziva patika koje koštaju tačno c (vector<vector<string>>).

2. Sortiranje imena

Nazive u svakoj grupi sortiramo leksikografski.

3. Najskuplja koju možemo da priuštimo

Za svaki mogući budžet x unapred izračunamo najskuplja[x] – najveću cenu ≤ x za koju postoji bar jedna patika (ili −1 ako takve nema). To radimo jednim prolazom: ako postoje patike sa cenom x, to je x, a inače vrednost za x − 1.

4. Upiti

Za svakog kupca jednim pristupom nizu dobijamo cenu: ako je −1, ispisujemo nema, inače ispisujemo sve nazive iz te grupe sa cenom.

5. Alternativa

Patike se mogu sortirati po ceni, a zatim se za svaki budžet binarnom pretragom nalazi najskuplja patika koja nije skuplja od budžeta. Prebrojavanje po cenama je jednostavnije jer su cene male.

6. Brzina

Upita ima do milion, pa uključujemo brz ulaz i izlaz i izbegavamo endl (koristimo "\n").

C++ rešenje

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

int main() {
    ios::sync_with_stdio(false);     // brz ulaz i izlaz zbog velikog broja upita
    cin.tie(nullptr);

    const int MAKS = 50000;          // cene su manje od 50000
    vector<vector<string>> poCeni(MAKS);   // poCeni[c] = nazivi patika sa cenom c

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string naziv;
        int cena;
        cin >> naziv >> cena;
        poCeni[cena].push_back(naziv);
    }
    for (int c = 0; c < MAKS; c++) {
        sort(poCeni[c].begin(), poCeni[c].end());   // leksikografski poredak unutar iste cene
    }

    // najskuplja[x] = najveća cena <= x za koju postoji bar jedan model (ili -1)
    vector<int> najskuplja(MAKS, -1);
    for (int x = 0; x < MAKS; x++) {
        if (!poCeni[x].empty()) najskuplja[x] = x;
        else if (x > 0) najskuplja[x] = najskuplja[x - 1];
    }

    int k;
    cin >> k;
    for (int q = 0; q < k; q++) {
        int budzet;
        cin >> budzet;
        if (budzet >= MAKS) budzet = MAKS - 1;

        int cena = najskuplja[budzet];
        if (cena == -1) {
            cout << "nema\n";
        } else {
            for (const string &naziv : poCeni[cena]) {
                cout << naziv << " " << cena << "\n";
            }
        }
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Reči su nezavisne

Svaka reč se rotira za jedno slovo pri svakom pritisku, nezavisno od ostalih. Cela rečenica se vraća u početno stanje onda kada se sve reči istovremeno vrate u početno stanje.

2. Za jednu reč

Reč dužine L vraća se u početno stanje posle L pritisaka, ali možda i ranije ako je periodična. Na primer reč abcabc ima dužinu 6, ali se posle 3 rotacije dobija ista reč, pa je njen broj pritisaka 3. Broj pritisaka je najmanja perioda reči, ako ona deli dužinu reči, a inače je to dužina reči.

3. Najmanja perioda

Najmanju periodu računamo pomoću prefiks-funkcije (KMP algoritma): ako je pi dužina najdužeg pravog prefiksa koji je ujedno i sufiks reči, perioda je L − pi. Ako L nije deljivo periodom, reč nije periodična i broj pritisaka je L. Za male reči (do 100 slova) dovoljno je jednostavno ispitivanje svih delilaca dužine.

4. Svi zajedno

Ako reč 1 treba p1 pritisaka, reč 2 treba p2 itd., rečenica je u početnom stanju kada je broj pritisaka deljiv svim pi, a najmanji takav broj je njihov NZS. NZS računamo pomoću NZD (Euklidov algoritam): NZS(a, b) = a / NZD(a, b) * b.

5. Tip podataka

Rezultat može biti do 10¹⁸, pa koristimo long long. Deljenje radimo pre množenja da ne bi došlo do prekoračenja.

C++ rešenje

#include <iostream>
#include <string>
#include <sstream>
#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;
}

// Najmanji broj pomeranja prvog slova na kraj posle kog se reč vraća u početno stanje.
// To je najmanja perioda reči, ako deli dužinu reči; inače je to cela dužina.
int periodReci(const string &r) {
    int duzina = r.size();
    vector<int> pi(duzina, 0);               // prefiks-funkcija (KMP)
    for (int i = 1; i < duzina; i++) {
        int j = pi[i - 1];
        while (j > 0 && r[i] != r[j]) j = pi[j - 1];
        if (r[i] == r[j]) j++;
        pi[i] = j;
    }
    int p = duzina - pi[duzina - 1];         // najmanja perioda
    if (duzina % p == 0) return p;
    return duzina;
}

int main() {
    string linija;
    getline(cin, linija);
    istringstream ulaz(linija);

    long long rezultat = 1;                  // NZS perioda svih reči
    string rec;
    while (ulaz >> rec) {
        long long p = periodReci(rec);
        rezultat = rezultat / nzd(rezultat, p) * p;
    }

    cout << rezultat << endl;
    return 0;
}

Uputstvo — ideja rešenja

1. Dve petlje

Spoljašnja petlja ide kroz n nizova, a unutrašnja kroz k elemenata jednog niza.

2. Uslov za jedan element

Element x na poziciji j je ispravan ako x i j imaju istu parnost, tj. x % 2 == j % 2. Zaista: na parnoj poziciji (j % 2 == 0) mora biti paran broj (x % 2 == 0), a na neparnoj neparan.

3. Učitavanje do kraja reda

Čak i kada se utvrdi da niz nije ispravan, moraju se učitati preostali elementi tog niza, da bi sledeći niz bio ispravno učitan. Zato koristimo logičku promenljivu ispravan, a ne prekidamo petlju.

4. Ispis

Posle unutrašnje petlje ispisujemo da ili ne.

C++ rešenje

#include <iostream>
using namespace std;

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

    for (int i = 0; i < n; i++) {          // n nizova
        bool ispravan = true;
        for (int j = 0; j < k; j++) {      // k elemenata niza
            int x;
            cin >> x;                      // učitavamo sve elemente, i posle greške
            // na parnim pozicijama treba da je paran broj, na neparnim neparan:
            // ostatak pri deljenju sa 2 mora da bude jednak ostatku pozicije
            if (x % 2 != j % 2) {
                ispravan = false;
            }
        }
        cout << (ispravan ? "da" : "ne") << "\n";
    }
    return 0;
}

Uputstvo — ideja rešenja

1. Dve mape

Čuvamo dva rečnika: naSrpski (engleska reč → srpska) i naEngleski (srpska reč → engleska). Za svaki učitani par upisujemo oba smera.

2. Upiti

Ako je traženi jezik en, reč je srpska pa je tražimo u mapi naEngleski. Ako je traženi jezik sr, reč je engleska pa je tražimo u mapi naSrpski.

3. Nepoznata reč

Pretragu radimo funkcijom find. Ako reči nema u mapi, ispisujemo ?. Operator [] ne koristimo za pretragu jer bi za nepoznatu reč dodao novi (prazan) element.

4. Brzina

Koristimo unordered_map (prosečno konstantno vreme pristupa) ili običnu map (logaritamsko) – oba su dovoljna za 50000 reči i upita.

C++ rešenje

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

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

    int n;
    cin >> n;
    unordered_map<string, string> naSrpski;     // engleska reč -> srpska reč
    unordered_map<string, string> naEngleski;   // srpska reč -> engleska reč

    for (int i = 0; i < n; i++) {
        string engleski, srpski;
        cin >> engleski >> srpski;              // u primeru je prvo engleska, pa srpska reč
        naSrpski[engleski] = srpski;
        naEngleski[srpski] = engleski;
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string jezik, rec;
        cin >> jezik >> rec;                    // jezik je na koji se prevodi

        if (jezik == "en") {
            auto it = naEngleski.find(rec);     // rec je srpska
            cout << (it == naEngleski.end() ? "?" : it->second) << "\n";
        } else {
            auto it = naSrpski.find(rec);       // rec je engleska
            cout << (it == naSrpski.end() ? "?" : it->second) << "\n";
        }
    }
    return 0;
}