Imprimă pagina - 613 NKPerm

Titlul: 613 NKPerm
Scris de: Andrei Grigorean din Noiembrie 25, 2007, 15:00:25

Aici puteţi discuta despre problema NKPerm (http://infoarena.ro/problema/nkperm).

Titlul: Răspuns: 613 NKPerm
Scris de: Sima Cotizo din Ianuarie 01, 2008, 17:31:29

E corect in articol secventa urmatoare?

Cod:

...
        daca cate[i] != 0:     
            cate[i]--   
            cate[i+1]++   
            daca i = ultim:   
                // fara valori egale pe pozitii adiacente   
                rez += cate[i]*numara(cate, i+1)   
            altfel:   
                rez += (cate[i]+1)*numara(cate, i+1)   
            cate[i+1]++   
            cate[i]--
...

a doua oara nu trebuia sa facem cate[i+1]--, cate[ i]++ ? ... adica nu e un fel de back ce face aici?

Titlul: Răspuns: 613 NKPerm
Scris de: Marius Stroe din Ianuarie 01, 2008, 23:51:24

Ba da, cate[i+1] -- si cate[ i] ++. Trebuie sa se revina la valorile initiale.

Titlul: Răspuns: 613 NKPerm
Scris de: Sima Cotizo din Ianuarie 02, 2008, 12:19:04

Ok, multumesc! :)

Eu nu prea am inteles partea asta. Adica : stim ca ultima cifra pusa apare de ultim ori (sau ca ultima cifra e ultim? ... cred ca de fapt apare de ultim ori)... facem un for si stim ca pt o valoare i avem cate[ i] numere care apar de i ori. Luam fiecare numar (teoretic) si il mai bagam o data la sfarsit, deci de aici vine rez += cate[ i] *numara(cate, i+1);... pe pseudocod, asta e cazul in care i!=ultim... dar de unde vine adunarea din else? ... adica dupa mine ar fi exact invers,

Cod:

daca (i!=ultim)
    rez+=cate[i]*numara(cate, i+1);
altfel
    rez+=(cate[i]-1)*numara(cate,i+1);

e corect? :?

Titlul: Răspuns: 613 NKPerm
Scris de: Mircea Pasoi din Ianuarie 02, 2008, 22:53:54

Pseudocodul din articol e corect deoarece ai decrementat cate[ i ] inainte.

Titlul: Răspuns: 613 NKPerm
Scris de: Sima Cotizo din Ianuarie 03, 2008, 10:08:04

:oops: ai dreptate

PS: am modificat eu articolul ca sa fie cum a zis si Marius mai sus... :?

Titlul: Răspuns: 613 NKPerm
Scris de: Mircea Pasoi din Ianuarie 03, 2008, 15:14:52

Foarte bine ca l-ai modificat.

Titlul: Răspuns: 613 NKPerm
Scris de: Cotletz Ovidiu din Martie 21, 2008, 14:07:47

Imi poate explica cineva cum fac aici memoizarea ? Sunt in total 20^6*6 rezultate care vine cam 1500MB

Titlul: Răspuns: 613 NKPerm
Scris de: Paul-Dan Baltescu din Martie 21, 2008, 15:53:49

Cu map din STL.

Titlul: Răspuns: 613 NKPerm
Scris de: Cotletz Ovidiu din Martie 21, 2008, 16:52:29

Si deci daca nu stiu si nici n-am de gand sa invat STL nu am sanse sa fac pb ?

Titlul: Răspuns: 613 NKPerm
Scris de: Andrei Grigorean din Martie 21, 2008, 20:40:34

Poti sa bagi cu hash-uri ;)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Noiembrie 25, 2007, 15:00:25