infoarena

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   

Pentru  prima problema  poti  folosi Ciurul lui  eratostene (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)(implementari gasesti aici (http://infoarena.ro/problema/ciur) ),  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). :)

La a doua problema stiu ca trebuie sa folosesc programare dinamica dar ai putea sa detaliezi putin cum?

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

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.

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.

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

Daca tie iti intra in Borland un tablou char de 51 200 000, eu ma las de info.  :)

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.

Nu sunt foarte sigur, deci intreb: problema asta e un caz "particular" al problemei numar2 (http://infoarena.ro/problema/numar2)? Daca e asa, se poate scoate o rezolvare O(3*N) => O(n). O sa detaliez daca raspunsul la intrebare este "da".

Pai am  incercat  in Borland 5.01 si  a mers :D
Da, poti sa-l consideri  un caz  particular :D (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 ?

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.

Basme... Nu o sa poti folosi atata memorie.  :)

Daca  tot suntem la niste indicatii... La problema  Insule (http://tminfo.info/index.php?Pages=Concursuri&foodar=19) 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... :-s   

cand spui ca extrag minimul din heap la ce te referi?... pentru ca minimul e intotdeauna 1.

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:


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.

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

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.problema se poate generaliza pentru m numere, nu doar 2,3,5.

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?

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

Pe vremuri parca n-aveam voie sa discutam pe infoarena teme de casa. :)

Da ai dreptate nu am fost destul de atent cand am citit programul, my bad  :peacefingers:

Ma refeream la solutia cu cautare binara descrisa mai sus tot de mine (deci tot nu ai citit topicul cu atentie) :P

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  :-'

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 :D Știi tu la ce mă refer...

Se poate optimiza destul de mult acea solutie, mai ales ca inca sunt destul de convins ca merge o solutie cu includere excludere. Ma rog ai dreptate complexitatea aia e putin mai mare decat un O(N), insa nu decat un N log N.

Între timp am ajuns la concluzia că e ok sa discutăm şi teme - de aceea am creat o secţiune specială a forumului dedicată lor.

Daca ar fi o tema care ar fi problema? Nu se dau rezolvari complete la probleme... de la cateva indicatii nu se poate intampla nimic :)

Pentru ca temele pe care le primesti de la profesorul tau le primesti cu un scop. Ca sa te gandesti singur la ele. Daca un profesor ti-a dat o tema inseamna ca ai toate cunostintele necesare pentru a o rezolva. Nu trebuie decat sa stai sa te gandesti.