Peti domaći

Scrabble

U igri "Scrabble" igrači na početku imaju na raspolaganju određeni broj pločica, pri čemu svaka pločica sadrži neko slovo abecede. Tokom igre, svaki od igrača na svom potezu pokušava da sastavi što dužu reč tako što će postaviti pločice na tablu za igru. Reč nosi onoliko poena koliko ima slova.

Takođe, igrači mogu dobiti bonus poene ako odigrana reč ne sadrži ni jedno od slova koje je igrač već iskoristio. Tada se broj poena za datu reč duplira.

Napisati program koji izračunava finalni broj poena datog igrača, nakon odigranih $n$ rundi.

Ulaz

Sa standardnog ulaza se najpre učitava niska bez belina sastavljena od slova engleske abecede koja predstavlja početne pločice igrača. Nakon toga se učitava broj $n$, a zatim i $n$ reči koje igrač redom odigrava.

Izlaz

Na standardni izlaz ispisati ukupan broj poena datog igrača. U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

Ulaz

abaokbdkedsota
3
baba
deda
kokos

Izlaz

Objašnjenje

Reči baba i kokos donose bonus poene, dok reč deda ponavlja slovo a.

Primer

Ulaz

abaokbdkedsot
3
baba
deda
kokos

Izlaz za greške

-1

Objašnjenje

Reč deda ne može biti odigrana jer ne postoji dostupno slovo a.

Nadvlačenje konopca

Na takmičenju u nadvlačenju konopca učestvuju dve ekipe. Za svakog člana ekipe, poznata je njegova snaga. Ukoliko je pri nadvlačenju najjači član jedne ekipe jači od najjačeg člana druge ekipe za barem $k$, tada ta ekipa pobeđuje.

Vremenom, najjači takmičar u ekipi se umori i sedne na klupu za odmor. Takođe, povremeno se najslabiji takmičar na klupi dovoljno odmori i vrati u ekipu.

Napisati program koji simulira jednu partiju nadvlačenja konopca i ispisuje koji tim je pobedio.

Ulaz

Prvi red sadrži dve celobrojne vrednosti:

n – broj članova po ekipi

k – minimalna razlika snage potrebna za pobedu

Drugi red sadrži n celih brojeva $a_1, a_2, \dots, a_n$, koji predstavljaju snage članova prve ekipe.
Treći red sadrži n celih brojeva $b_1, b_2, \dots, b_m$, koji predstavljaju snage članova druge ekipe.

Četvrti red sadrži broj upita q.
Sledećih q redova opisuje upite. Svaki upit može biti jednog od sledeća dva tipa:

odmor A – najjači član tima A (A = 1 ili 2) se umorio i izlazi iz igre (seda na klupu)
vrati A – najslabiji član tima A (A = 1 ili 2) koji je na klupi se odmorio i ulayi u igre.

Pretpostaviti da će u svakom trenutku u igri biti barem jedan igrač za svaku od ekipa.

Izlaz

Na standardni izlaz ispisati 1 ukoliko je prva ekipa pobedila, 2 ukoliko je druga ekipa pobedila ili 0 ukoliko je nerešeno.

Primer

Ulaz

4 5
15 10 20 17
14 18 8 12
6
odmor 1
odmor 2
odmor 1
vrati 1
odmor 2
vrati 2

Izlaz

Objašnjenje

Nakon petog upita, najjači takmičar u prvoj ekipi ima snagu 17, a u drugoj 12.

Primer

Ulaz

4 5
15 10 20 17
14 18 8 12
6
odmor 1
odmor 2
odmor 1
vrati 2
vrati 1
odmor 1

Izlaz

Pec

Kartaška igra "Pec" može se igrati sa špilom karata na kojim su bilo kakvi simboli. Igra funkcioniše tako što igrači naizmenično stavljaju karte na jednu gomilu. Ukoliko neki igrač primeti da je drugi igrač odigrao simbol koji je već odigran ranije (nalazi se na gomili), može da kaže "pec" kako bi proverio svoju tvrdnju. Ukoliko je u pravu, igrač koji je "upecan" (odigrao je kartu čiji je simbol već ranije bio na gomili) kupi karte sa gomile sve dok ne naiđe na simbol sa odigrane karte (uključujući drugu kartu sa datim simbolom). Ukoliko pak igrač koji je rekao "pec" pogreši, on kupi sve karte sa gomile.

Napisati generičku klasu pec<T> koja implementira strukturu za simuliranje igre "Pec" sa simbolima tipa T. Klasa treba da podržava sledeće operacije:

void dodaj(const T& simbol) - dodaje novu kartu na gomilu sa datim simbolom.
bool pecni(const T& simbol) - proverava da li je dati simbol već na gomili.
int skini(const T& simbol) - skida karte sa gomile dok se ne dođe do datog simbola (uljučujući njega). Ukoliko dati simbol ne postoji na gomili, baca izuzetak std::out_of_range.
int skini_sve() - skida sve karte sa gomile

Prve dve operacije treba da budu složenosti $O(1)$, a druge dve $O(n)$, gde je $n$ broj karata na gomili.

Ulaz

U prvom redu nalazi se broj upita q.

Svaki od narednih q redova sadrži jedan od sledećih upita:

d x – dodaj kartu sa simbolom x na gomilu

p – pokušaj da "pecneš"

Simboli su tipa T (u test primerima tip int).

Izlaz

Za svaki od upita tipa p ispisati koliko je karata igrač koji mora da kupi karte pokupio.

Primer

Ulaz

11
d 5
d 3
d 7
p 
d 10
d 4
d 7
d 2
d 5 
d 4
p

Izlaz

3
5

Pozorište

Napisati generičku klasu pozoriste<N, M> koja implementira strukturu za rezervisanje karata u pozorištu čija sedišta su poređana u N vrsta i M kolona. Klasa treba da podržava sledeće operacije:

void ispisi() const - ispisuje trenutno stanje zauzetosti sedišta na standardni izlaz. Zauzeta sedišta označiti sa x, a slobodna sa o.
bool rezervisi(size_t vrsta, size_t kolona) - Rezerviše mesto na poziciji (vrsta, kolona). Ukoliko je traženo mesto zauzeto, funkcija vraća false, a inače true. Ukoliko sedište sa prosleđenim indeksima ne postoji, baca izuzetak std::out_of_range sa odgovarajućom porukom (pogledati drugi test primer).
size_t broj_slobodnih() - vraća broj slobodnih mesta.

Funkcije rezerviši i broj slobodnih treba da radi u vremenskoj složenosti $O(1)$. Dok memorijska složenost treba da bude $O(n)$, gde je $n$ broj trenutno zauzetih mesta.

Ulaz

U prvom redu nalazi se broj upita q.

Svaki od narednih q redova predstavlja jedan upit i može biti jednog od sledećih oblika:

r v k – pokušaj rezervacije mesta u vrsti v i koloni k

s – ispis trenutnog stanja pozorišta

b – ispis broja slobodnih mesta

Izlaz

Za svaki upit r v k ispisati:

OK ako je rezervacija uspešna
NE ako je mesto već zauzeto

Za svaki od upita b ispisati jedan ceo broj – broj slobodnih mesta.

Za svaki od upita s ispisati matricu sa karakterima o i x koja predstavlja trenutno stanje pozorišta.

Primer

Ulaz

7
b
r 1 2
r 0 0
r 1 2
s
b
r 2 3

Izlaz

12
OK
OK
NE
x o o o
o o x o
o o o o
10
OK

Primer

Ulaz

7
b
r 1 2
r 0 5
r 1 2
s
b
r 2 3

Izlaz

12
OK
NE
o o o o
o o x o
o o o o
11
OK

Izlaz za greške

Nevalidni indeksi mesta

Polasci

Napisati klasu polasci koja implementira strukturu za čuvanje polazaka jedne autobuske linije. Za svaki polazak su poznati ime stanice i vreme polaska. Klasa treba da podržava sledeće operacije:

void dodaj(const std::string& stanica, int sati, int minuti) - dodaje novi polazak sa zadate stanice u zadato vreme.
void ukloni(const std::string& stanica, int sati, int minuti) - uklanja polazak sa određene stanice u zadato vreme ukoliko on postoji. U suprotnom, baca izuzetak std::out_of_range.
int sledeci_polazak(const std::string& stanica, int sati, int minuti) - vraća vreme u minutima do prvog polaska sa zadate stanice u istom danu, nakon zadatog vremena, ukoliko postoji. U suprotnom, baca izuzetak std::out_of_range sa odgovarajućom porukom (pogledati drugi test primer).

Sve operacije treba da budu složenosti ne veće od $O(\log n)$, gde je $n$ broj polazaka.

Ulaz

Sa standardnog ulaza, sve do kraja ulaza, učitavaju se naredbe u formatu:

d stanica sati minuti - dodaje polazak sa zadatim podacima u strukturu
o stanica sati minuti - uklanja polazak sa zadatim podacima iz strukture
p stanica sati minuti - proverava vreme do polaska sa zadate stanice nakon zadatog vremena, u istom danu

Izlaz

Na standardni izlaz ispisati za svaki od p upita vreme do sledećeg polaska u minutima. Ako dođe do izuzetka, ispisati poruku izuzetka na standardni izlaz za greške i nastaviti izvršavanje.

Primer

Ulaz

d Beograd 11 30
d Beograd 12 45
d Nis 11 45
p Beograd 11 40
d Beograd 12 0
p Beograd 11 40
o Beograd 12 0
p Beograd 11 40

Izlaz

65
20
65

Primer

Ulaz

d Beograd 11 30
d Beograd 12 45
d Nis 11 45
p Beograd 13 40
d Beograd 12 0
p Beograd 11 40

Izlaz

Izlaz za greške

Nema polazaka nakon zadatog vremena

Objašnjenje

Prvi upit p nije validan