Znam da baš nema veze s OOP-om..No trebam pomoć oko zadatka PATULJCI na ovom linku.=)
Dakle, prva stvar koja bi ti trebala pasti na pamet je da smrdi na koristenje dinamickog programiranja. Ono sto sam prvo pomislio je slijedece:
Krenemo od prvog patuljka, i za svakog patuljka zapisemo koliko je do njega bilo kapica koje boje. Tada kad nas zanima koliko je bilo kapica koje boje izmedu patuljaka X..Y, samo oduzmemo broj kapica, dakle X..Y = 1..Y - 1..X. Za to bi nam trebalo polje velicine NxC za pamtiti broj i boju svih kapica koje se pojavljuju od prvog do n-tog patuljka za svaki n izmedu 1 i N.
Da bismo sve to izracunali imamo slijedeci broj potrebnih operacija (sve uzima u obzir najgori moguci slucaj):
N operacija za popunjavanje polja (< 300 000 - zanemarivo)
M * (C + C) < 10 000 * 20 000 = 200 000 000 (za svaku od M slika trebamo prvo oduzetu kolicinu kapica za svaku boju, te pritom provjeriti je li za neku od tih boja imamo dovoljno kapica da se objavi slika). 200 milijuna nije za baciti, ali bi se trebalo izvrsiti ispod jedne sekunde, ako se ne vrti na nekoj prastaroj krami od kompjutera.
Ono sto je problem je memorija N * C moze biti cak 3 000 000 000 ~ 3GB, a mi imamo samo 32MB, pa moramo smisliti kako da tome doskocimo.
No, buduci da mozemo dobiti maksimalno 10 000 zadanih parova, onda niti ne trebamo tocan broj kapica od prvog do svakog od patuljaka, nego samo tih (najvise) 20 000 koji su nam bitni. Dakle, prvo pogledamo koji parovi se traze, tada za svakog od patuljaka koji nam je bitan zapisemo u tablicu za svaku boju kapica koliko ih se pojavljuje do njega (opet isto kao u prvom slucaju, samo ne zapisujemo za svakog patuljka). To nam je 20 000 * 10 000 = 200 MB, sto je nazalost jos uvijek previse.
E sad se tu kompliciraju stvari, i vjerojatno se ovo moze bolje, ali meni je ovako palo na pamet:
Ulazni podatke o pocetnom i zavrsnom patuljku mozemo shvatiti kao koordinate tocaka u ravnini. Udaljenost dvije takve tocke (x1, x2) i (y1, y2) definiramo kao |y1 - x1| + |y2 - x2|, zato jer ako imamo podatak koliko kapica koje boje se pojavljuje izmedu patuljaka x1 i x2, tada nam upravo toliko operacije treba da izracunamo taj podatak za ovaj drugi par (samo dodamo ili oduzmemo razliku izmedu pocetnih, x1 i y1 i krajnjih - mozemo zamisliti kao setnju). Sad uzmemo bilo koji par za pocetak, krenemo od pocetnog patuljka i prebrojimo kapice do krajnjeg. Sad od preostalih parova odaberemo najblizi po ovoj udaljenosti, i iz ovog rezultata izracunamo slijedeci, i tako anstavimo dok ne prodemo sve parove. Na samo racunanje do kjeg para idemo slijedece nam ode 50 000 000 operacija, sto nije grozno, za provjeru postoji li dobra kapica ode 100 000 000, dok za samo preracunavanje rezultata od jednog para za drugi trenutacno nemam pojma kako bih izracunao, no mislim da ne bi trebalo biti previse.
Ne znam bi li radilo za najteze test primjere, mozda je ipak presporo, ali mislim da bi
