•adi0l
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« : Martie 17, 2009, 19:06:09 » |
|
Salutare tuturor,
Am 2 probleme la care as dori sa ma ajutati cu niste indicatii daca se poate. Nu luati in considerare complexitatile cerute pentru ca sunt doar de umplutura(dar totusi sa nu iasa mai mare:P). Daca m-ati putea ajuta v-as fi recunoscator.
Multumesc, Adi
Problema 1
Sa se calculeze al n-lea numar natural care contine doar pe 2, 3 si 5 ca factori primi (altfel spus, nu are alti divizori in afara de 2, 3 si 5). Primul numar care satisface aceasta conditie este considerat 1.
Restrictii:
* 0 < n <= 1500
Complexitate dorita: O(n * log n)
Intrare:
Datele de intrare se citesc din fisierul "p1.in", care contine o singura linie pe care se alfa n.
Iesire:
Datele de iesire vor fi scrise in fisierul "p1.out". Acesta va contine o singura linie cu numarul ce trebuie calculat.
Exemplu:
p1.in 1000
p1.out 51200000
Primul numar care satisface acea conditie este considerat 1 si se continua cu 2 3 4 5 6....
Problema 2
Avem un numar de n gramezi de bete - cele ce se afla intr-o gramada au dimensiune egala, iar cele din gramezi diferite au dimensiuni diferite. Numarul total de bete este nr, iar dimensiunea maxima a betelor dintr-o gramada este 50. De asemenea, se cunosc numarul de bete din fiecare gramada si faptul ca toate betele au o dimensiune ce este multiplu de 1 cm. Stiind ca toate aceste bete au fost obtinute din ruperea aleatoare (cu respectarea conditiei de multiplu de 1 cm, deci practic se pot rupe numai in multiplii de 1 cm) a unui numar initial de m bete de dimensiune egala, cu conditia ca aceasta dimensiune sa fie cat mai mica posibil, determinati aceasta dimensiune, precum si modul in care au fost rupte betele initiale.
(Explicatie: ma intereseaza numarul de bete de dimensiune minimala egala, deoarece daca consideram cazul in care avem 8 bete egale de 10 cm, am putea sa consideram si 4 bete egale de 20 cm si 2 bete de 40 cm si 1 bat de 80 cm. Tocmai de aceea, ne intereseaza sa gasim doar betele de dimensiune egala cat mai mica posibil.)
Restrictii:
* 0 < nr <= 100 * 0 < S = suma dimensiunilor betelor <= 1000
Complexitate dorita: exponentiala (dar cat mai redusa)
Intrare:
Datele de intrare se citesc din fisierul "p2.in", care contine:
* pe prima linie, numarul de gramezi n; * pe a doua linie, dimensiunile fiecareia dintre cele n gramezi separate prin spatii; * pe a treia limie, numarul de bete din fiecare gramada (deci tot n numere separate prin spatii).
Iesire:
Datele de iesire vor fi scrise in fisierul "p2.out". Acesta va contine:
* pe prima linie doua numere separate printr-un spatiu: dimensiunea betelor de dimensiune egala si numarul acestora; * pe urmatoarele linii, se afla pe fiecare linie in parte dimensiunile betelor rupte ce alcatuiesc cate un bat initial (deci vor fi numar de bete initiale linii).
Exemplu:
p2.in 4 11 7 5 4 1 1 3 3
p2.out 15 3 11 4 7 4 4 5 5 5
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #1 : Martie 17, 2009, 19:13:14 » |
|
Pentru prima problema poti folosi Ciurul lui eratostene(implementari gasesti aici ), pentru a determina numarul care respecta conditia. Daca nu ma insel chiar are complexitatea O(n*log n). A 2 problema se poate rezolva folosind backtraking sau programare dinamica (o recomand).
|
|
« Ultima modificare: Martie 17, 2009, 19:20:07 de către alexandru »
|
Memorat
|
|
|
|
•adi0l
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #2 : Martie 17, 2009, 19:28:25 » |
|
La a doua problema stiu ca trebuie sa folosesc programare dinamica dar ai putea sa detaliezi putin cum?
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #3 : Martie 17, 2009, 19:49:38 » |
|
Pai determeni toate sumele posibile si pentru fiecare suma memorezi ce bat a intervenit si de cate ori apare acea suma . Apoi parcurgi vectorul si vezi daca suma obtinuta * de cate ori apare == suma totala de bete atunci afisezi betele si ai terminat . Sper ca n-am gresit
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #4 : Martie 17, 2009, 20:24:26 » |
|
La prima problema nu prea vad cum ai putea folosi ciurul lui eratostene dar ma rog, probabil ca se poate, nu m-am gandit prea mult. Eu ma gandeam la o alta solutie. Poti sa tii un min-heap, in care initial ai doar numarul 1. Apoi la fiecare pas, extragi minimul din heap, si adaugi min*2, min*3, min*5. Ai de facut N pasi, operatiile de extragere minim si adaugare element intr-un heap au complexitate log N si astfel ai N log N.
|
|
« Ultima modificare: Martie 17, 2009, 20:35:08 de către Savin Tiberiu »
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #5 : Martie 17, 2009, 20:34:51 » |
|
Ar merge ideea de ciur la prima problema: marchezi cu 1 toti multiplii lui 2, 3 si 5, si apoi cu 0 multiplii celorlalte numere prime, dar nu intra in memorie, daca al 1000'lea numar este 51 200 000. Solutia cu heap e mai convenabila.
|
|
« Ultima modificare: Martie 17, 2009, 20:41:29 de către Gabriel Bitis »
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #6 : Martie 17, 2009, 20:46:58 » |
|
Pai daca folosesti un compilator diferit de Borland 3.1 si vectorul il pui de tip char iti merge desigur nu recomand la olimpiada ii mai buna idea lui @Savin Tiberiu
|
|
« Ultima modificare: Martie 18, 2009, 06:53:09 de către alexandru »
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #7 : Martie 17, 2009, 20:58:09 » |
|
Pai daca folosesti un compilator diferit de Borland 3.1 si vectorul il pui de tip char iti merge desigur nu recomand la olimpiada ii mai buna idei lui @Savin Tiberiu Daca tie iti intra in Borland un tablou char de 51 200 000, eu ma las de info.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #8 : Martie 17, 2009, 21:18:59 » |
|
iata o idee si mai buna . Sa presupunem ca am fixat un numar K si vrem sa aflam cate numere care contin ca factori primi numai pe 2, 3 si 5 mai mici decat K exista. Daca am putea calcula acest lucru rapid, am putea sa il cautam binar pe K. Acum ca sa rezolvam aceasta subproblema, consideram numerele de forma 2^x * 3^y * 5^z. Fixam cu 2 for-uri pe y si pe z iar pe x cred ca il putem calcula. Astfel am ajuns la o complexitate de log2(MAX) * log3(MAX) * log5(MAX), unde MAX este o valoare mai mare decat al 1500-lea nr de forma 2^x * 3^y * 5^z, cred ca 2 miliarde ar fi de ajuns. De asemenea e posibil sa putem rezolva subproblema folosind principiul includerii si excluderii, insa nu prea am avut timp sa ma gandesc, dar cred ca ar merge.
|
|
« Ultima modificare: Martie 19, 2009, 12:38:15 de către Savin Tiberiu »
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #9 : Martie 17, 2009, 21:37:21 » |
|
Nu sunt foarte sigur, deci intreb: problema asta e un caz "particular" al problemei numar2? Daca e asa, se poate scoate o rezolvare O(3*N) => O(n). O sa detaliez daca raspunsul la intrebare este "da".
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #10 : Martie 18, 2009, 07:03:23 » |
|
Daca tie iti intra in Borland un tablou char de 51 200 000, eu ma las de info. Pai am incercat in Borland 5.01 si a mers Nu sunt foarte sigur, deci intreb: problema asta e un caz "particular" al problemei numar2 Da, poti sa-l consideri un caz particular (chiar primul exemplu e "cazul particular" numai ca trebuie sa modifici M;) ) Parca solutia oficiala de la aceasta probleme, nu era un fel de back mai complex ?
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #11 : Martie 18, 2009, 10:10:48 » |
|
Nu nu este un caz particular al acelei probleme. Cititi mai cu atentie. Adica voi ziceti ca daca N ar fi 3 si numerele 2 3 5 ar fi aceeasi problema. Ei bine nu este. Acolo numarul 14 = 2 * 7 face parte din sir ptr ca este multiplu de 2. Aici in schimb, numarul 14, nu face parte din numerele care ne intereseaza pe noi.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #12 : Martie 18, 2009, 11:10:31 » |
|
Daca tie iti intra in Borland un tablou char de 51 200 000, eu ma las de info. Pai am incercat in Borland 5.01 si a mers Basme... Nu o sa poti folosi atata memorie.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #13 : Martie 18, 2009, 16:16:55 » |
|
Daca tot suntem la niste indicatii... La problema Insule de la OJI, am determinat cate tari R,G,B sunt in arhipelagul dat. Cum determin lungimea minima a podului? Mi-au spus unii cu Lee, dar nu stiu cum sa-l fac pe matricea asta...
|
|
|
Memorat
|
|
|
|
•adi0l
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #14 : Martie 18, 2009, 17:31:35 » |
|
La prima problema nu prea vad cum ai putea folosi ciurul lui eratostene dar ma rog, probabil ca se poate, nu m-am gandit prea mult. Eu ma gandeam la o alta solutie. Poti sa tii un min-heap, in care initial ai doar numarul 1. Apoi la fiecare pas, extragi minimul din heap, si adaugi min*2, min*3, min*5. Ai de facut N pasi, operatiile de extragere minim si adaugare element intr-un heap au complexitate log N si astfel ai N log N.
cand spui ca extrag minimul din heap la ce te referi?... pentru ca minimul e intotdeauna 1.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #15 : Martie 18, 2009, 17:37:30 » |
|
cand spun ca il extragi zic ca il afli si dupa aia il scoti din heap. Iata heapul dupa primi pasi. Pas 1 : 1 Pas 2 : 2 3 5 (minimul a fost 1, am introdus 2 3 si 5) Pas 3 : 3 4 5 6 10 (minimul a fost 2, am introdus 4, 6 si 10). ... Trebuia totusi sa ai grija ca unele elemente vor aparea de mai multe ori in heap, asa ca atunci cand scoti minimul din heap faci ceva de genul asta: min = get_min(); while (afla_minim() == min) extrage_min();
unde get_min este o functie care iti zice elementul minim din heap, iar extrage_minim scoate cel mai mic element din heap.
|
|
|
Memorat
|
|
|
|
•adi0l
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #16 : Martie 18, 2009, 17:39:01 » |
|
cand spun ca il extragi zic ca il afli si dupa aia il scoti din heap. Iata heapul dupa primi pasi. Pas 1 : 1 Pas 2 : 2 3 5 (minimul a fost 1, am introdus 2 3 si 5) Pas 3 : 3 4 5 6 10 (minimul a fost 2, am introdus 4, 6 si 10). ... Trebuia totusi sa ai grija ca unele elemente vor aparea de mai multe ori in heap, asa ca atunci cand scoti minimul din heap faci ceva de genul asta: min = get_min(); while (afla_minim() == min) extrage_min();
unde get_min este o functie care iti zice elementul minim din heap, iar extrage_minim scoate cel mai mic element din heap. aham... mersi mult.
|
|
|
Memorat
|
|
|
|
•mihai.maruseac
Strain
Karma: 3
Deconectat
Mesaje: 3
|
|
« Răspunde #17 : Martie 18, 2009, 23:00:17 » |
|
Pai determeni toate sumele posibile si pentru fiecare suma memorezi ce bat a intervenit si de cate ori apare acea suma . Apoi parcurgi vectorul si vezi daca suma obtinuta * de cate ori apare == suma totala de bete atunci afisezi betele si ai terminat . Sper ca n-am gresit Ce te faci când poți obține 16 prin 4 bețe de 4 și prin 1 de 4 și 4 de 3? Dacă faci produsul îți dă mai mare de 64 și ți-ar da că suma nu e bună. Testul: 4 bețe de 4 16 bețe de 3
|
|
|
Memorat
|
|
|
|
•warangel
Strain
Karma: -5
Deconectat
Mesaje: 19
|
|
« Răspunde #18 : Martie 19, 2009, 11:33:36 » |
|
problema 1 se poate rezolva in O(n). completam un vector 'v' de la 1->n unde v[ i ] reprezinta al i-lea numar din sirul dorit. v[1]=poz[2]=poz[3]=poz[5]=1; pt i->2,n executa v[i]=minim(v[poz[2]]*2,v[poz[3]]]*3,v[poz[5]]*5); if(v[poz[2]]*2==v[i])poz[2]++; if(v[poz[3]]*3==v[i])poz[3]++; if(v[poz[5]]*5==v[i])poz[5]++; sfarsit;
problema se poate generaliza pentru m numere, nu doar 2,3,5.
|
|
« Ultima modificare: Martie 19, 2009, 13:37:53 de către Bogdan Tataroiu »
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #19 : Martie 19, 2009, 12:37:01 » |
|
Citeste si tu mai atent ce s-a discutat inainte. In primul rand s-a spus deja o solutie mai rapida de o(n). In al doilea rand solutia ta e gresita. E gresita din acelasi motiv pe care l-am zis eu mai sus cand explicam de ce aceasta problema nu e un caz particular al problemei numar2.
|
|
|
Memorat
|
|
|
|
•warangel
Strain
Karma: -5
Deconectat
Mesaje: 19
|
|
« Răspunde #20 : Martie 19, 2009, 13:35:46 » |
|
Citeste si tu mai atent ce s-a discutat inainte. In primul rand s-a spus deja o solutie mai rapida de o(n). In al doilea rand solutia ta e gresita. E gresita din acelasi motiv pe care l-am zis eu mai sus cand explicam de ce aceasta problema nu e un caz particular al problemei numar2.
Am citit discutia destul de bine inainte sa postez. Insa tu nu mi-ai citit programul la fel de bine. Si la care solutie te referi ca e mai rapida decat O(n)? cea cu heap? v[1]=poz[2]=poz[3]=poz[5]=1; pt i->2,n executa v[i]=minim(v[poz[2]]*2,v[poz[3]]]*3,v[poz[5]]*5); if(v[poz[2]]*2==v[i])poz[2]++; if(v[poz[3]]*3==v[i])poz[3]++; if(v[poz[5]]*5==v[i])poz[5]++; sfarsit;
Sa il explic: initial p2=p3=p5=v[1]=1; v[2]=minim(1*2,1*3,1*5)=2; p2=2; v[3]=minim(2*2,1*3,1*5)=3;p3=2; v[4]=minim(2*2,2*3,1*5)=4;p2=3; v[5]=minim(3*2,2*3,1*5)=5;p5=2; v[6]=minim(3*2,2*3,2*5)=6;p2=4;p3=3; v[7]=minim(4*2,3*3,2*5)=8;p2=5; v[8]=minim(5*2,3*3,2*5)=9;p3=4; v[9]=minim(5*2,4*3,2*5)=10;p2=6;p5=3; v[10]=minim(6*2,4*3,3*5)=12;p2=7;p3=5; v[11]=minim(7*2,5*3,3*5)=15;p3=6;p5=4; etc... de asemenea am m-as putea baza decat pe p2 si p3 si la p5 sa adaug decat puterile lui 5, dar n-are rost pt ca n e mic. PS: tinand cont ca esti moderator ar trebui sa fi mai prietenos :p
|
|
« Ultima modificare: Martie 19, 2009, 13:49:44 de către dinu sorin »
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #21 : Martie 19, 2009, 14:05:26 » |
|
Pe vremuri parca n-aveam voie sa discutam pe infoarena teme de casa.
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•devilkind
|
|
« Răspunde #22 : Martie 19, 2009, 16:38:18 » |
|
Da ai dreptate nu am fost destul de atent cand am citit programul, my bad Ma refeream la solutia cu cautare binara descrisa mai sus tot de mine (deci tot nu ai citit topicul cu atentie)
|
|
|
Memorat
|
|
|
|
•warangel
Strain
Karma: -5
Deconectat
Mesaje: 19
|
|
« Răspunde #23 : Martie 19, 2009, 17:06:22 » |
|
Da ai dreptate nu am fost destul de atent cand am citit programul, my bad Ma refeream la solutia cu cautare binara descrisa mai sus tot de mine (deci tot nu ai citit topicul cu atentie) Inca l-am citit tu ai zis asa: Astfel am ajuns la o complexitate de log2(MAX) * log3(MAX) * log5(MAX), unde MAX este o valoare mai mare decat al 1500-lea nr de forma 2^x * 3^y * 5^z, cred ca 2 miliarde ar fi de ajuns. log2(MAX) * log3(MAX) * log5(MAX),MAX=2.000.000.000 > n. La un calcul rapid ar iesi in jur de 8000. Adica mai mare chiar decat N logN Scuza-ma daca gresesc, logaritmii nu mi-au placut niciodata
|
|
|
Memorat
|
|
|
|
•mihai.maruseac
Strain
Karma: 3
Deconectat
Mesaje: 3
|
|
« Răspunde #24 : Martie 19, 2009, 17:06:41 » |
|
Pe vremuri parca n-aveam voie sa discutam pe infoarena teme de casa. Adevărul e că, uneori e cam greu să observi dacă e temă sau nu. Oricum, dacă apar două probleme sau dacă cel care le propune nu știe deloc cum s-ar putea rezolva, e clar că e vorba de un assignment. M-am ferit să zic că e temă pentru că nu vroiam să mai pornesc un flame anti-me și aici Știi tu la ce mă refer...
|
|
|
Memorat
|
|
|
|
|