OJI Liceu 2010

[•CezarMocan]

Iti explic eu .
Prima problema ar putea fi reformulata in felul urmator: sa se gaseasca numarul de partitii ale lui N (partitie = sir de numere cu suma N), de lungime D (adica formate din D numere), astfel incat fiecare numar din partitie sa fie >= K. Pentru a rezolva asta facem programare dinamica: C[ i ][ j ] = numarul de solutii daca am fixat primele i numere din partitie si avem obtinuta suma j. Raspunsul se va gasi in C[D][N]. Te las sa te gandesti la recurenta, daca vrei ti-o zic. Se poate face in O(N^2 * D) - facand dinamica inainte, sau daca optimizezi in O(N * D), cu sume partiale.


La cea de-a doua e mai simplu, dupa ce ai determinat toate cuvintele tii sirul D[ i ] cu semnificatia lungimea maxima a unui lant avand proprietatea din enunt care se termina cu cuvantul i, si L[ch] = lumgimea maxima a unui lant pana la pozitia i (adica din ce am calculat pana acum) care se termina cu caracterul ch. D[ i ] = L[prima_litera_din_cuvantul_i] + 1. Si daca D[ i ] > L[ultima_litera_din_cuvantul_i] atunci actualizezi valoarea din L. Raspunsul va fi numarul de cuvinte - maximul din sirul D (numarul minim de cuvinte eliminate). Pentru a face reconstituirea se tine un vector suplimentar, prev[ i ] = cuvantul care vine inaintea cuvantului i in solutia care da valoarea D[ i ].

Sper ca ai inteles! Spor la implementat!

[•moon]

Ca sa verific k-ul as fi putut sa implementez de mai multe ori dijkstra (de 9 ori maxim, din moment ce k era intre 2<10) ... sau as fi putut sa construiesc muchiile treptat, pe baza celor vizitate anterior  .

Oricum, chiar si daca nu as fi verificat k-ul, sunt sigur ca ar fi obtinut >= 30 puncte.

[•popoiu.george]

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);

[•skull]

Ca sa verific k-ul as fi putut sa implementez de mai multe ori dijkstra (de 9 ori maxim, din moment ce k era intre 2<10) ... sau as fi putut sa construiesc muchiile treptat, pe baza celor vizitate anterior  .

Oricum, chiar si daca nu as fi verificat k-ul, sunt sigur ca ar fi obtinut >= 30 puncte.

Daca nu iei k-ul in considerare = 0 pct.

[•O_Neal]

evaluatorul folosit se poate gasi undeva? nu inca nu? sau? iar despre teste? daca le aveti sau ceva.. spuneti.. skull ti-am dat PM cu mail(mai devreme si am dat unu si acu)  sa imi trmiti daca ai, mersi!

[•f.v.anton]

Ca sa verific k-ul as fi putut sa implementez de mai multe ori dijkstra (de 9 ori maxim, din moment ce k era intre 2<10) ... sau as fi putut sa construiesc muchiile treptat, pe baza celor vizitate anterior  .

Oricum, chiar si daca nu as fi verificat k-ul, sunt sigur ca ar fi obtinut >= 30 puncte.

Daca nu iei k-ul in considerare = 0 pct.

garantez si eu pt asta, ca asa am facut eu, nu l-am luat in considerare si ma asteptam sa prind ceva puncte, dar de unde...0.

[•skull]

evaluatorul folosit se poate gasi undeva? nu inca nu? sau? iar despre teste? daca le aveti sau ceva.. spuneti.. skull ti-am dat PM cu mail(mai devreme si am dat unu si acu)  sa imi trmiti daca ai, mersi!

N-am primit niciun PM.

Gasesti evaluatorul pentru XI-XII aici sau aici.

[•O_Neal]

am dat 3 PM-uri nush de ce nu s-au trimis.. mersi l-am luat

[•popoiu.george]

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

LE : Ti-am dat si eu PM.

[•dornescuvlad]

pune-l si pe cel de-a zecea te rog aici

[•toni2007]

Iti explic eu .
Prima problema ar putea fi reformulata in felul urmator: sa se gaseasca numarul de partitii ale lui N (partitie = sir de numere cu suma N), de lungime D (adica formate din D numere), astfel incat fiecare numar din partitie sa fie >= K. Pentru a rezolva asta facem programare dinamica: C[ i ][ j ] = numarul de solutii daca am fixat primele i numere din partitie si avem obtinuta suma j. Raspunsul se va gasi in C[D][N]. Te las sa te gandesti la recurenta, daca vrei ti-o zic. Se poate face in O(N^2 * D) - facand dinamica inainte, sau daca optimizezi in O(N * D), cu sume partiale.


La cea de-a doua e mai simplu, dupa ce ai determinat toate cuvintele tii sirul D[ i ] cu semnificatia lungimea maxima a unui lant avand proprietatea din enunt care se termina cu cuvantul i, si L[ch] = lumgimea maxima a unui lant pana la pozitia i (adica din ce am calculat pana acum) care se termina cu caracterul ch. D[ i ] = L[prima_litera_din_cuvantul_i] + 1. Si daca D[ i ] > L[ultima_litera_din_cuvantul_i] atunci actualizezi valoarea din L. Raspunsul va fi numarul de cuvinte - maximul din sirul D (numarul minim de cuvinte eliminate). Pentru a face reconstituirea se tine un vector suplimentar, prev[ i ] = cuvantul care vine inaintea cuvantului i in solutia care da valoarea D[ i ].

Sper ca ai inteles! Spor la implementat!

Cam asa am facut si eu.

[•skull]

Nu-l am decat pe cel de la XI-XII.

[•andrei-alpha]

Au fost adaugate problemele de la OJI 11-12 in Arhiva de probleme.

[•moon]

Metoda greedy obtine 10 puncte si nu tine cont de k....

[•dornescuvlad]

Bogdan Andre, te rog pune si la a 10-a

[•GavrilaVlad]

Problemele de la a 10-a cat si de la a 9-a sunt in lucru. Vor aparea zilele urmatoare 

[•wefgef]

Felicitari Marius!

http://olimpiada.info/oji2010/index.php?cid=rezultate&w=lic&judet=09&clasa=12

[•Robytzza]

 
am vorbit cu cineva o sa se modifice

[•Stefanaj]

http://www.liis.ro/~cex_is/Informatica/pregatire.html


gasiti aici evaluatoarele pt orice clasa la "arhiva si evaluatoare"

[•smith_s9]

Felicitari celor calificati! Ne vedem la ONI .

Eu am luat 70 de puncte, back la ambele probleme (a XII-a). Pt immortal imi mai ramasese doar o ora si in graba am facut o eroare in gandire si am facut o solutie cu complexitate mai mare decat era nevoie. Am luat 40p ).

[•za_wolf]

ne vedem la oni friendz    

[•dornescuvlad]

cand se pun loturile 

[•Mishu91]

cand se pun loturile 

Asta depinde de fiecare județ. La noi, de exemplu s-a afișat lotul pentru oni.

[•dornescuvlad]

E real sau e doar un scenariu inventat de tine pt a ironiza subiectele ?  

[•cricri]

E real sau e doar un scenariu inventat de tine pt a ironiza subiectele ?  

din pacate,real....