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:

Cod:

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.

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.

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

[Problema 1]

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