*MAGIC i BiG DIGITS*

Zanima me kako se rijesavaju ova dva zadatka za sve bodove.

Sto se tice Magic to ne znam, ali sto se tice bigdigits to znam :) ( bar kako sam ja uradio )

ja sam prvi deo dinamicki

int dp[ a ][ b ][ c ] -> koliko ima brojeva koji pocinju sa cifrom a, imaju b cifara i zbir im je c

i onda to iskoristim pri racunanja: koliko ima brojeva do broja x da ima zbir s

i samo vratim

solve( b, s ) - solve( a-1, s )

Mozes to i jednostavnije:

Brojeve A i B pretvorim u stringove ovako, npr A = 152, B = 12745:

...0012745
...0000152

Sad mi je stanje u dinamici ovakvo: dp [pos][suma][dira_a][dira_b].

Kako se ja krecem od prve do zadnje pozicije, uvijek biram jednu znamenku i tako gradim broj. Da ne bih presao izvan intervala [A, B], potrebne su mi vrijednosti dira_a i dira_b (oni su boolovi) da bih znao jesam li trenutno na granici broja A ili broja B.

Npr. u gornjem primjeru sam recimo dosad sam izgradio ovaj broj: ...00127XX onda mi je dira_B = true jer trenutno idem po granici broja B, sto znaci da sljedeca znamenka ne moze biti > 4.

Veoma zanimljivi test primeri za Big Digits u 26 od 50 test primera je resenje 0 xD

I dalje stoji pitanje za magic.....

i big Digits nisam bas mogao skuziti iz ovih postova. Ako je neko voljan malo detaljnije pojasniti.... :)

Pejstat cu svoj kod da bude jasnije o cem se radi...
http://zadaci.pastebin.com/m6de81c2a

cim se zawrsilo takmicenje pocele diskusije o zadacima...ljudi opustite se malo !

Jel ima neko link za tutorijal o DP-u ? Treba mi jer nikad nisam radio DP. :-(

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Uskoro ce biti i tutorijali na kojima trenutno rade clanovi Komisije, ali za sada je ovo sasvim ok. Veoma je korisna nasa knjiga, od Vugdelije.

Ok, pogledacju to. Mislim da moj profesor ima tu knjigu od M. Vugdelije pa cju da potrazim od njega. Sad upravo citam Programiranje i Programiranje ( Metodicka zbirka zadataka ) od Vugdelije i sadrzi dobro objasnjene primere se detaljnim obrazlozenjem pa smatram da je i Dinamicko Progrmiranje od Vugdelije dobra knjiga. :)

Da, dobra je. Nema nekih naprednih stvari, ali zato ima i vise nego sto je dovoljno za pocetak. Meni je bila veoma korisna kad sam poceo da ucim. Onaj link sa TCa ima naprednih stvari. Kad sklopis i jedno i drugo, onda ti preostaje samo da radis zadatke ;)

Tako cju i da uradim. Spojicju dobro i korisno. :)

I, hoce li neko da uputi narod kako da napredujemo u rijesavanju zadatka magic ???

Pa ovako. Prvo veoma je bitno kako ih popunjavas, dobro je ako kad popunjavas neku kolonu ili vrstu vec imas neka polja popunjenja. U tom cilju najbolje je da prvo popunis dijagonale jer se one brzo popunjavaju i daju ti dosta zgodnih poljia. Javi kako napreduje sa takvim nacinom popunjavanja. Znaci dijagonale, pa onda vrste/kolone.

sto se tice BigDigit tu mogu da pomognem valjda ...

pa ja sam imao matricu d[Z][C] gde sam cuvao na koliko nacina se neka suma Z moze staviti na C cifara, ta matrica se popuni na pocetku ...
onda radim Do(b) - Do(a)
tj.
Do() mi radi recimo da je broj: 87312
trazim na koliko nacina se moze rasporediti suma Z na preostale cifre ...

0ABCD - koliko ima nacina da se S-0 rasporedi na 4 cifre
1ABCD - koliko ima nacina da se S-1 rasporedi na 4 cifre
...
7ABCD - koliko ima nacina da se S-7 rasporedi na 4 cifre

brojac mi uvek ide do cifra[i]-1 da ne bi racunao brojeve vece od b
onda idem na 2. cifru
tj.
80BCD - S-8-0 na 3 cifre
81BCD - S-8-1 na 3 cifre
82BCD - S-8-2 na 3 cifre
...
86BCD - S-8-6 na 3 cifre
i tako za sve cifre, gde cu na kraju gledati:
8730D - S-8-7-3-0 na 1 cifru

a slucaj 8731D cu da proverim if-om da ne bi otisao preko broja b

recimo da bi funkcija Do(b) radila, b = 87312
d[S][4]+d[S-1][4]+d[S-2][4]+...+d[S-7][4]+
d[S-8][3]+d[S-8-1][3]+...+d[S-8-6]+
d[S-8-7][2]+d[S-8-7-1][2]+d[S-8-7-2][2]+
d[S-8-7-3][1]+ 1(ako je 0 <= S-8-7-3-1 < poslednja cifra( u ovom slucaju 2))
samo sam morao da pazim da mi S-nesto ne ode u minus ...

na kraju proverim da li je suma cifara broja b = S, ako jeste resenje uvecam za 1

nadam se da sam bar malo pomogao, i da nikog nisam jos vise zbunio ... :D

Vezano za Magic: nisam shvatio iz zadatka, ako rjesenje postoji, je li nuzno jedinstveno? Naprimjer:

3
1 0 1
0 1 0
1 0 1

?

Mislim da u matrici moraju biti upisani svi
brojevi između 1 i n^2 , znači da se nijedan broj ne smije ponavljati 2 puta...

@tgudlek: nije jedinstveno, ti mozes da izbacis bilo koje

Ja nikako da smislim neko jednostavnije rijesenje za magic od rekurzije. Ali problem nastaje i rekurziom kada je pokusavam napraviti sto vise pametnijom, jer se previse raspisem pa nece da radi u potpunosti kako treba. Ja sam uradio tako da bira uvijek red ili colonu sa najvise popunjenim poljima sa time da nisu do kraja popunjeni. Pa ih popunjavam rekurziom, pazeci da ako sam vec pronasao sumu, ne prekoracim sumu kolone/reda dodavanjem elemenata. U slucaju da mi je poznata suma i da su mi poznti n-1 elementi odredjivao sam n-ti element preko sum-sum_col / red.

kao sto je sloba rekao:

prvo popuni dijagonale, jer ces onda imati po 2 odradjena za svaki red i kolonu, pa ce ti ici brze

@ stjepang:

Za koji zadatak ti je ovaj kod? Izgleda super... :D

Izvinjavam se, nisam poslao link.

Na ovaj kod sam mislio: http://zadaci.pastebin.com/m73211c27

Hehe... Izvinjavam se ostalima zbog offtopic-a, ali nemamo PM, pa moram ovde kontaktirati coveka.

@stjepang:
http://zadaci.pastebin.com/m4ad27886

Opet trie. Ako ti nije mrsko, posalji mi tekstove za ova dva zadatka na codeteam17@googlemail.com

Rjesenja su bas inspirativna. Hvala unapred... ;)