Pripreme za algoritme(21)

Danas ćemo se baviti malo analizom zadataka sa županijskoga natjecanja 2012.
Svi kodovi su dostupni na web stranici organizatora.

M
Zadatak se svodi na prebrojavanje oznaka od početne do završne umanjene za oznake koje su veće korištene, a nalaze se u intervalu novih oznaka.

učitavanje početka i kraja
pretvaranje oznaka početka i kraja u brojeve: slovo*1000+ostatak
razmak=kraj-početak+1
prebrojavanje (br) koliko oznaka je u intevalu od početka do kraja
ispisivanje razlika-br

Parlament
Algoritam se svodi na analizu polja u kojem smo zabilježili je li u nekoj minuti bilo traženi broj zastupnika (1) ili nije (0).
Traženje intervala koji ima najmanje reklama: napravimo niz uzastopnih suma. Gdje je suma na traženoj duljini intervala veća tamo je očito manje reklama.
Iz pretraživanja treba izbaciti mogućnosti da prijenos počne(p[j]=p[j-1]) i završava reklamom (zadnja minuta prijenosa ne smije biti reklama pa ne smije vrijediti uvjet p [j+t]-p[j+t-2]=1).

Klingonce smo već analizirali, a nekom prilikom ćemo i zadatak pustinja.

U sljedećim nastavcima ćemo još obraditi nekolicinu algoritama.