Daca vrei sa ai mai mari sanse sa fii ajutat cred ca ar fi bine sa scrii mai clar codul (sa-l indentezi si sa lasi mai multe spatii astfel in cat sa devina mai lizibil)

Evalul e in asteptare. 

Recurenta din solutie este cumva P^k-1 = ( P^k-1-1 ) * (P-1)! , toate luate modulo P ?

P.S. : Topicul nu este legat de problema.

LE : Imi explicati va rog cum sa precalculez valorile de forma P^k-1 ? Ca nu reusesc sa ma prind.

Am inteles ce este inversul modular, dar am cateva nedumeriri.

Pentru orice numar N>=P, N! % P este automat egal cu 0. Este asa sau gresesc ?

Cum mai calculez inversul modular daca a, b sau c pot fi 0.

Terenul asta e intr-un fel "minat" pentru mine, pt ca nu am cunostinte solide de aritmetica modulara.

Multumesc !

@cipri20 M-am uitat pe sursa ta si calcularea cmmdc e corecta, doar ca tu nu tii cont ca in fisierul de intrare vor fi T teste. Si cred ca e nevoie de long long pentru 100pt.

Sper ca ti-a fost de folos.

Imi puteti explica si mie recurenta de la numarul lui Stirling de speta I ? Chiar nu am reusit sa o pricep.

Nu stiu cum pot calcula numarul lui catalan pentru numere foarte mari. n<=11000 . Este o problema pe campion care cere rezultatul modulo 44711, iar daca aplic modulo pe parcurs ce calculez, imi da un rezultat gresit.

Eu stiu urmatoarele relatii :
C(n) = Comb(2n,n) / n+1
C(n) = Comb(2n,n) - Comb(2n,n-1)
C(n) = [ (4n+2)/(n+2) ] * C(n-1), unde C(0)=C(1)=1

Se poate calcula fara sa implementez operatii pe numere mari ?

PS : problema se numeste 'fotbal' .

O data.

"Ricky Martin de Romania" este genial . [VIDEO]  

http://bit.ly/b8yhD0

LE : Niste bancuri cu chuck norris

1) Chuck Norris secretly sleeps with every woman in the world - as a result, they bleed once a month.
2) Chuck Norris doesn't have ctrl on his keyboard, because he's always on control.
3) Chuck Norris doesn't have a backspace key, because he never mistakes.
4) Pi ends with Chuck Norris , because he is the end of everything.
5) Chuck Norris is always on top during sex, because Chuck Norris never fucks up.

Costurile initiale pot sa fie si 0 ?

Citeste articolul cu solutii. O sa vezi ca nu e nevoie de Knapsack.

http://infoarena.ro/preoni-2008/runda-1/solutii#economie

Sunt 2 cazuri : cand poti aduna de mai multe ori aceeasi valoare si cand poti aduna fiecare valoare o singura data.

Care te intereseaza ?

Cred ca faci confuzie. Da, coada o poti implementa ca un vector.

Daca stii ce este o stiva poti face o analogie.

Daca tii un vector asupra caruia tu impui niste restrictii si il folosesti intr-un anumit fel, poti sa spui ai o stiva sau o coada, etc.

Daca vrei sa intelegi mai bine structurile astea iti sugerez sa incerci sa le folosesti din STL sau sa le implementezi tu (daca stii sa aloci dinamic memorie sau OOP) , atunci cred ca vei intelege cu adevarat semnficatia lor.

Fara indoiala este o problema foarte mare, dar o problema mai mare este ignoranta celor de la minister si lipsa lor de cunostinte in acest domeniu.

LE : Mie cel putin mi se pare normal (si natural) sa se foloseasca ultima versiune a compilatoarelor.

De asemenea, dupa cum spune si Dragos in postul anterior, MinGW Developer Studio nu cred ca este cea mai buna alegere din mai multe puncte de vedere.

1) Proiectul nu mai este in development din 2006 mi se pare.
2) CodeBlocks este un IDE care este in development si net superior lui MinGW Developer Studio. (parere formata dupa utilizarea ambelor medii)

@skull   Il vreau si eu pentru a X-a te rog. Il ai ?

LE : Ti-am dat si eu PM.

Nu inteleg ce e gresit la urmatoarea dinamica (inafara de faptul ca gradul de complexitate nu este optim ) : (clasa a X-a, problema a 2-a )
nrmin[ i ] = numarul minim de cuvinte ce trebuie sterse (din primele i-1 cuvinte ) ca sa obtinem un text ce respecta regulile enuntului, acel text terminandu-se cu al i-lea cuvant

Cod:

for( i=1; i<=nr_cuvinte; i++)
   {

   nrmin[i]=i-1; //stergem tot ce e in stanga

   for( j=1 ; j<i; j++)
      if( respecta_regula(j,i) && nrmin[ i ] > nrmin[j]+(i-j-1) ) nrmin[ i ]=nrmin[j]+(i-j-1); //sterg cuvintele j+1,...,i-1
   
   }

//aflam rezultatul
int minim=INF; //infinit

for( i=1; i<=nr_cuvinte; i++)
   if( nrmin[ i ] + (nr_cuvinte-i) < minim ) //pastrez rezultatul optim pentru primele i cuvinte si sterg tot din dreapta
      minim = nrmin[ i ] + (nr_cuvinte-i);

Da, acum am inteles, multumesc ! 

S-au afisat testele la a 10-a? Eu nu le-am gasit ...

Imbunatatirea ...

Sa presupunem ca nu cunosc notiunea de graf si vreau sa aflu costul minim dintre doua celelule ale unei matrici

Poti sa faci o dinamica cu o coada. Daca vrei detalii PM me.

Urmatoarea problema a fost data la ONI in 2004 si am gasit-o postata pe campion.

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=922

Problema este ca nu reusesc sa imi explic solutia data ( complexitate O(N*K) ), care suna cam asa :

Cu toţii cunoaştem dinamica clasică a distanţei de editare (dacă nu, vezi Cormen). Problema e că rezolvarea clasica este O(N^2) (de fapt N*M, dar N si M sunt foarte apropiate ca valori). Noi trebuie să rezolvam insa in O(K*N).
Pentru aceasta observam ca din toata acea matrice nu ne trebuie decat K elemente in jurul diagonalei principale.
Orice element aflat in afara acestei benzi poate fi considerat infinit, pentru ca ajungerea in colt necesita cel putin K incrementari, deci rezultatul final va fi mai mare decat K.

Daca ati inteles rezolvarea, v-as ruga sa mi-o explicati si mie.

Multumesc ! 

Da, mi-a mers, cred ca gresisem la implementare, multumesc ! 

M-am gandit si eu la aceasta recurenta si i-am dat niste teste usoare, dar din pacate nu este corect. 

Din cate imi amintesc cred ca am vazut problema explicata intr-un articol chiar aici pe infoarena, dar asta era cu ceva timp in urma.

Acum cand am nevoie de rezolvarea problemei, nu am reusit sa o mai gasesc si de aceea postez aici.

Daca cunoasteti rezolvarea as fi recunoscator daca ati explica-o, sau mai bine, sa ma directionati catre articol. (daca exista)

@skull prin recursivitate programul lucreaza cu stiva, si de aici s-ar putea sa fie mai incet programul.