Tip of the day: AB prebrojavanje

Jučer se na Hrvatskoj informatičkoj olimpijadi pojavio zadatak Ljepotica autora Ivana Paljka. U zadatku se traži zbroj velikih brojeva s određenim svojstvom, koji se nalaze između dvaju velikih brojeva A i B (koji imaju do 1000 znamenaka). Zadatke koji odgovaraju navedenom kalupu obično rješavamo tzv. AB prebrojavanjem.

Riječ je naprosto o dinamičkom programiranju koje je zbog pojavljivanja u ovom specifičnom obliku dobilo posebno ime. Zamišljamo da veliki broj gradimo znamenku po znamenku te nas u nekom trenutku zanima na koliko načina možemo napisati broj do kraja (ili zbroj tih mogućnosti, ili nešto drugo, ovisno o zadatku). Poanta je da nam za odgovor na to pitanje nisu bitne sve dosad odabrane znamenke, tj. stanje je moguće opisati manjim brojem parametara, od kojih je jedan redovito pozicija na kojoj se nalazimo (tj. redni broj trenutačne znamenke), a drugi ovisi o zadatku, tj. o traženom svojstvu broja koji konstruiramo (npr. pamtimo broj preostalih promjena u zadatku Ljepotica).

Da bismo se ograničili na brojeve iz intervala [A, B], treba nam još jedan parametar: jesmo li dosad odabranim znamenkama već osigurali da će broj koji konstruiramo biti strogo manji od B, ili on još uvijek može biti jednak B, tj. podudaraju li se dosadašnje znamenke sa znamenkama broja B. U stanja gdje bismo premašili B nećemo ni ući, a to osiguravamo upravo iz navedenog parametra, znajući moramo li pri odabiru trenutačne znamenke paziti da ne premašimo istu znamenku u broju B (ako smo dosad birali iste znamenke kao u broju B).

Takva dinamika ne vodi računa o donjoj granici A, ali poslije samo provedemo isti algoritam s tom granicom da bismo oduzeli brojeve manje od A koje smo prethodno ubrojili. Drugim riječima, računamo koliko ih ima do B, minus koliko ih ima do A – 1, čime dobivamo koliko ih ima od A do B.

Osim ovih generičkih ideja, svaki zadatak ovog tipa može biti na svoj način osobit i ponekad je potrebna još neka specifična dosjetka, kao npr. u zadatku Umnožak koji se također pojavio na HIO, desetak godina prije. Otprilike u to vrijeme i na HONI-ju se pojavio zadatak Trešnja ovoga tipa. Priču je moguće i malo okrenuti, pa tražiti N-ti broj koji zadovoljava neko svojstvo, kao u zadatku Sretni s IBT-a.

Tipičan zadatak za početnike bio bi npr. Sum of Digits – ovakve zadatke lako je debugirati jer je lako skodirati brutfors i izmišljati testne primjere. Još mnogo objašnjenja i zadataka dostupno je na webu ako tražite Digit DP. Primjerice:

2 misli o “Tip of the day: AB prebrojavanje

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s