Osnovni pojmovi

Autor: Ivan Vlahov

Tipični program

Šablona

Različite platforme za natjecateljsko programiranje imaju različite vrste zadataka, različita ograničenja, na nekim natjecanjima smijete koristiti dijelove programskog koda napisane prije natjecanja (npr. Codeforces), a na nekima ne smijete (npr. Natjecanje iz informatike), pa se iz tog razloga i priprema za različita natjecanja razlikuje.

Međutim, više-manje svako rješenje započinje pisanjem sljedećih linija koda:

#include <bits/stdc++.h>

using namespace std;

int main(){
    // Rješenje vašeg zadatka
}

U prvom retku uključujemo biblioteku u kojoj se nalazi velik broj struktura podataka i funkcija koje će nam sigurno trebati tijekom rješavanja zadataka. Iako u jednom zadatku sigurno nećemo koristiti većinu mogućnosti ove biblioteke, bolje je uključiti sve odjednom nego trošiti vrijeme na razmišljanje o tome koju bismo specifičnu biblioteku trebali uključiti.

U drugom retku postavljamo prostor imena std kao zadani prostor imena. Ta naredba nam također olakšava pisanje koda jer bismo inače morali pisati std:: ispred puno drugih izraza (npr. std::cin, std::cout, std::string).

Zatim slijedi funkcija main u koju upisujemo svoje rješenje određenog zadatka.

U slučaju da se planirate natjecati na natjecanjima gdje je dozvoljeno korištenje unaprijed napisanog koda, uvijek je dobro imati spremljen template koji možete samo kopirati i lijepiti te si tako dodatno uštedjeti neko vrijeme.

Kompajliranje

Svoje programe (npr. ako se kod nalazi u datoteci program.cpp) možete kompajlirati i pokrenuti naredbom

g++ -std=c++17 -O2 -Wall program.cpp -o program

u naredbenom retku, što će stvoriti izvršnu datoteku koju ćete zatim moći pokrenuti. Zastavica -O2 označava optimizaciju izvršnog koda, a zastavica -Wall omogućuje izlistavanje svih upozorenja kompajlera.

Dodatne mogućnosti

Iako su gore navedena šablona i naredba za kompajliranje dovoljno dobri, možemo ih još malo doraditi kako bismo brže pisali kod i kako bi se program brže izvršavao.

Možemo ubrzati čitanje ulaznih podataka korištenjem sljedeća dva retka na početku funkcije main:

ios::sync_with_stdio(0);
cin.tie(0);

Više o tome što ova dva retka rade možete pročitati ovdje.

Također, često se događa da shvatite da imate grešku u programu, zbog toga izvršavate svoj program nekoliko puta koristeći iste ulazne podatke, te na kopiranje i lijepljenje ulaznih podataka trošite previše vremena. Taj problem se može izbjeći tako da zalijepite ulazne podatke u neku datoteku (npr. ulaz.txt), te korištenjem naredbe

freopen("ulaz.txt", "r", stdin);

preusmjerite sadržaj datoteke ulaz.txt na standardni ulaz. Međutim, koristeći ovakvo rješenje, morali biste uklanjati ovaj redak prije predaje svog rješenja. Da bismo to izbjegli, možemo koristiti uvjetno kompajliranje na samom početku funkcije main:

#ifdef DEBUG
freopen("ulaz.txt", "r", stdin);
#endif

te dodati zastavicu -DDEBUG u naredbu kompajleru tako da naredba sad izgleda ovako:

g++ -std=c++17 -O2 -Wall -DDEBUG program.cpp -o program

Ovime ćete omogućiti da se na vašem računalu ulaz čita iz datoteke ulaz.txt, a na poslužitelju koji ocjenjuje vaše rješenje sa standardnog ulaza. Uzmite u obzir da se u ovom slučaju datoteka ulaz.txt mora nalaziti u istoj mapi kao i program.cpp.

Nakon ovih poboljšanja, vaša šablona bi trebala izgledati ovako:

#include <bits/stdc++.h>

using namespace std;

int main(){
    #ifdef DEBUG
    freopen("ulaz.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0);
    cin.tie(0);

    // Rješenje vašeg zadatka
}

Poboljšanja specifična za Codeforces

S obzirom da će većina primjera u ovim materijalima biti s natjecanja na platformi Codeforces, treba spomenuti da se na toj platformi ulazni podaci većine zadataka sastoje od više test primjera te se algoritam mora izvršiti više puta u jednom izvršavanju programa. Iz tog razloga možemo napraviti posebnu šablonu za Codeforces koja će izgledati ovako:

#include <bits/stdc++.h>

using namespace std;

int main(){
    #ifdef DEBUG
    freopen("ulaz.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0);
    cin.tie(0);

    int TEST = 1;
    cin >> TEST;

    while(TEST--) {
        // Rješenje vašeg zadatka
    }
}

oprez

Bitno je napomenuti da u svakom zadatku morate pažljivo pročitati kako izgledaju ulazni podaci, nekad se znaju pojaviti i zadaci u kojima se u jednom primjerku ulaza nalazi samo jedan test! U tom slučaju možete samo zakomentirati liniju cin >> TEST; i nastaviti rješavati bez trošenja previše vremena.

Tipovi podataka

int

Cjelobrojni tip podataka int zauzima $32$ bita memorije, odnosno $4$ bajta, te pokriva cijele brojeve od $-2^{31}$ do $2^{31} - 1$, odnosno otprilike od oko $-2.147 \cdot 10^{9}$ do oko $2.147 \cdot 10^{9}$.

U slučaju da trebate izvršiti neke aritmetičke operacije s velikim brojevima, često se dogodi da prekoračimo granicu tipa int te zbog toga rješenja zadataka ispadnu netočna. Na primjer, sljedeći isječak koda daje neočekivano rješenje:

int a = 50000;
int b = a*a;
int c = b/2;

cout << a << " " << b << " " << c;

Očekivali bismo ovakav ispis:

50000 2500000000 1250000000

Međutim, dobijemo ovakav ispis:

50000 -1794967296 -897483648

jer se u varijablu $b$ spremi kriva vrijednost zato što je vrijednost $50000^{2}$ veća od gornje granice tipa int, te se vrijednost "prelije" natrag u negativne brojeve.

long long

Da bismo izbjegli pogreške nastale zbog preljeva (eng. overflow), koristit ćemo tip long long koji zauzima 64 bita memorije, a pokriva cijele brojeve od $-2^{63}$ do $2^{63} - 1$, odnosno od oko $-9.223 \cdot 10^{18}$ do oko $9.223 \cdot 10^{18}$.

Zamjenom tipa int za tip long long u prošlom isječku koda:

long long a = 50000;
long long b = a*a;
long long c = b/2;

cout << a << " " << b << " " << c;

Dobijemo očekivani izlaz:

50000 2500000000 1250000000

Također, s obzirom da kao natjecatelji želimo uštedjeti što je više moguće vremena, možemo na početak naše šablone (ispod #include <bits/stdc++.h> retka) dodati i liniju:

#define ll long long

Te tako uštedjeti vrijeme pišući ll umjesto long long.

float

Želimo li koristiti brojeve s pomičnim zarezom, koristimo tip float.

Bitno je spomenuti da često preciznost tipa float nije dovoljno dobra te ga je bolje izbjegavati. Na primjer, sljedeći isječak koda ne daje očekivani ispis:

float x = 3.14159265f;

cout << x << endl;
printf("%1.8f", x);

Ispis:

3.14159
3.14159274

double

Želimo li koristiti brojeve s pomičnim zarezom dvostruke preciznosti, koristimo tip double. Uzmemo li prošli isječak i promijenimo tip, dobit ćemo drugačiji ispis.

double x = 3.14159265;

cout << x << endl;
printf("%1.8f", x);

Ispis:

3.14159
3.14159265

char

Želimo li u memoriju spremiti neki znak, koristimo tip char. Taj tip je zapravo cjelobrojni tip podataka, može se pretvarati u ostale cjelobrojne tipove te se mogu i vršiti neke aritmetičke operacije s njima, poput zbrajanja i oduzimanja (mogu se vršiti i ostale operacije, ali to nema baš smisla).

cout << (int)'a' << "\n";
cout << (char)('a' + 1) << "\n";
cout << (char)(97) << "\n";
cout << ('a' < 'z') << "\n";
cout << (int)('a' * 'b'); // Ovo, iako radi, nema baš smisla...

Ispis:

97
b
a
1
9506

Aritmetičke operacije nad znakovima mogu se pokazati korisnima prilikom rada sa znakovnim nizovima, ili ako se u zadatku nešto indeksira znakovima umjesto brojevima. Uzmimo na primjer program koji generira Cezarovu šifru za mala slova engleske abecede. U toj šifri se svako slovo pomiče za neki određeni broj "koraka" unaprijed, pa tako npr. za englesku abecedu i 3 koraka slovo a postaje d, b postaje e, c postaje f, a x postaje a, y postaje b, z postaje c. Korištenjem jednostavne aritmetike nad znakovima možemo implementirati ovu šifru:

// uzmimo da je broj koraka 3 kao u primjeru
int step = 3;

char word[7] = "abcxyz";

for(int i=0; i<6; i++) {
    cout << (char)('a' + (word[i] - 'a' + step) % 26);
}

Ovaj isječak koda dat će očekivani ispis:

defabc

string

Želimo li u memoriju spremiti nekakvu riječ ili rečenicu, koristimo string. string nije osnovni tip podataka, već je više kao polje podataka tipa char koje ima ugrađene neke funkcije koje možemo koristiti da bismo manipulirali tim podacima, ali o tome više u poglavlju o tipu string.

Za spremanje podataka u varijablu tipa string možemo koristiti naredbu cin, međutim, ako taj izraz na ulazu sadrži razmake, u varijablu će se spremiti samo prva riječ. Da bismo spremili čitav redak, koristimo naredbu getline. Na primjer, za ulaz:

NatPro je super!

Sljedeći isječak koda

string s;
cin >> s;

cout << s;

će ispisati NatPro, dok će za sljedeći isječak

string s;
getline(cin, s);

cout << s;

ispisati NatPro je super!.

Neke funkcije s kojima ćete se susretati kao argumente primaju tip const char * te iz tog razloga neće raditi s tipom string, međutim, korištenjem funkcije c_str možete pretvoriti string u const char * te tako riješiti potencijalni problem.

string s = "echo NatPro je super!";

// system(s); Ne radi!
system(s.c_str());

U ovom primjeru naredba system izvršava naredbu u naredbenom retku.