Pseudocod:

Cod:

m = n;
s = 0;
while n >= 1 {
   m = m * 2;
   for i = 1 ... m {
      s = s + i;
   }
   n = [n/2];
}

Trebuie determinat timpul de executie in functie de n(notatie-theta).
Am avut problema asta la tema si au aparut fel si fel de capete luminate cu fel si fel de pareri(solutiile variand in special intre theta(n²) si theta(n²log n)). Voi ce parere aveti?

Imi puteti spune va rog unde pot da RUN SYSTEM TESTS? Nu am gasit nicaieri

Cand esti in Practice Room: Practice Options -> Run System Test.

*Banuiesc ca totusi pentru a intelege programarea dinamica, e nevoie de ceva cunostiinte bogate in domeniul claselor.

Programarea dinamica nu are legatura cu clasele.

si acum doar cand ma gandesc la antichitatea de C imi face greata

Cum poti sa spui asa ceva? Dai impresia ca java ar fi un limbaj net superior C-ului.

Postase cineva la un moment dat aceste puncte de reper:

O(1-2 milioane) -> 0.1 s
O(20-40 milioane) -> 1 s

Eu m-am orientat de multe ori dupa ele si mi-au fost de folos. Bineinteles ca timpul de rulare depinde de operatiile pe care le faci la fiecare pas, de modul de implementare...

Calculand complexitatea algoritmului, iti dai seama de cele mai multe ori daca-ti intra rezolvarea in timp.

Eu as face asa: best[ i ] = cel mai lung subsir care se incheie la pozitia i(include cuvantul de pe pozitia i). Problema este foarte asemenatoare cu cea a subsirului crescator maximal.

Succes!

Daca vrei eficienta poti sa faci liniar, desi e mult mai frumos cu dinamica.

Cod:

int main ()
{
    int N, rez = 1;
    cin >> N;
    while ( N )
    {
        if ( N >= 3 && N != 4) { rez *= 3; N -= 3; }
        if ( N == 4 ) { rez *= 4; N -= 4; }
        if ( N == 2 ) { rez *= 2; N -= 2; }
        if ( N == 1 ) { rez = 1; N--; }
    }
    cout << rez;
    return 0;
}

Sau verifici direct restul impartirii lui N la 3 si ridici la putere in timp logaritmic si devine si mai eficient.

Eu 9.40 la info. Habar n-am ce am gresit, dar asta e.

Sunt exact in aceeasi situatie. Cum sa ai pretentii sa fie corectori buni cand nici macar pe barem n-au fost in stare sa puna un algoritm corect...

In cazul in care graful nu trebuie sa fie neaparat conex eu am zis asa: in total pot fi N(N-1)/2 muchii, tu trebuie sa alegi M dintre acestea, astfel rezultatul devine combinari de N(N-1)/2 luate cate M.

Foloseste F10, iar in momentul in care esti pe un subprogram si vrei sa intri in el poti utiliza F11.

Eu l-am trecut cu un backtracking putin optimizat.

Ai putea folosi pair<> daca ai doar 2 variabile in structura si poti face push cu make_pair. Altcumva nu cred ca ai cum, cel putin eu nu stiu. Cat despre heap, nici acolo n-am alta idee, da' nu vad un mare efort sa faci cmp-ul, oricum face STL-ul destule. 

Cod:

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]<cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

Ce motive ai sa nu folosesti o variabila de tip nod?

Solutia nu este unica, iar rezultatul care-ti da tie pe exemplu este bun.

Poti vedea aici evaluarile.

Tipul de date long long merge pana la 2^64, deci 500000500000 incape lejer. Nu cred ca sunt astfel de teste, ar fi culmea. 

Da, chiar el. 

Ciudat, ar trebui sa-ti intre in memorie 2 tablouri 3D.

Am fost acum sa vad rezultatul si nu mi-a venit sa cred. Am luat 18p pe a 2a problema(cls X, buc) desi am facut-o complet. Ati gasit pe undeva evaluatoarele oficiale ca mi-am rescris problema acasa si merge!

http://infoarena.ro/downloads

Cod:

bool muchii_crescatoare(mchie m1, mchie m2)
{
	return m1.cost <= m2.cost;
}

Cred ca daca lasi doar "<" merge.

Nu poti ajunge la aceleasi coordonate cu un numar diferit de comenzi.

Nu e nevoie de numere mari. Suma intra in long long.

http://infoarena.ro/fmi-no-stress-2010

Se poate construi in ambele cazuri.

Nu-ti putem vedea sursa si oricum nu cred ca are cineva timp sa faca debugging. Ar fi mai bine daca ne-ai spune ideea ta de rezolvare.