494 Scara 2

[•DITzoneC]

Aici puteţi discuta despre problema Scara 2.

[•Marius]

Daca generez toate partitiile cu back iau 4 TLE. Daca fac o dinamica mai intai in O(N * H * M^2), dupa care caut toate partitiile cu ajutorul matricei din dinamica, nici o partitie in plus, iau tot 4 TLE.

Cum ati reusit sa fiti sub 0.1 s ?

[•domino]

Incearca o rezolvare O(3^M) (este foarte rapida in cazul asta).

[•Marius]

Nu imi dau seama de O(3^M). Tot la O(Comb(M, N) * N!) ajung.

Inca putin ajutor, te rog ?

[•fireatmyself]

in primul rand trebuie sa generezi toate partitionarile lui H in N termeni distincti.
pentru fiecare partitie (in cadrul back-ului) calculezi E[t] = efortul minim pentru a urca primele t trepte

o sa fie ceva gen:

Cod:

void bkt()
{
             if (Nr_termeni == N)
                   calculeaza_E();
             else mai_pune_un_termen_la_partitie;
}

Spor

[•domino]

Trebuie sa calculezi pentru fiecare submultime a numerelor {1,2...M} care este efortul minim care se poate obtine construind o scara cu valorile din submultime.
Ca sa calculezi asta pentru o submultime S, alegi o alta submultime S' de valori inclusa in S si calculezi efort(S) in functie de efort(S-S') si costul ca sa parcurga toate valorile din submultimea S' (media aritmetica + P), presupunand ca valorile din S' se afla la inceputul scarii. Partea mai dificila este reconstituirea solutiei.

[•Marius]

E tare tare rezolvarea. domino rulz.

[•marin]

Are ceva special testul 1? E singurul pe care iau incorect

[•Szabi]

in enunt scrie ca treptele sunt "de inaltimi distincte doua cate doua". se refera la faptul ca doua trepte consecutive au inaltimi diferite sau oricare doua inaltimi difera?
mersi

[•0000]

Daca sunt "de inaltimi distincte doua cate doua" insemna ca orcum ai alege 2 au inaltimi distincte.

[•Anamaria20]

  Poate cineva sa-mi trimita un mesaj personal cu o sursa de 100 sau cu solutia problemei? Nu imi vine nici o idee care sa mearga in 0.1 secunde si chiar as vrea sa aflu cum se face. Multumesc anticipat.

[•toni2007]

Gasesti la Downloads arhiva de la oji 2005 si iei de acolo sursa.

[•thesilverhand13]

Am si eu o nelamurire .Am rezolvat in c aceasta problema cu ideea de rezolvare din solutia oficiala.Aceasta se bazeaza pe aranjamentele primelor inaltimi<=h(distanta de la sosea la vila) cu determinarea efortului prin metoda programarii dinamice.Ceea ce ma intriga este faptul ca imi iese din timp pe 5 dintre teste.As ruga sa imi explicati cateva idei de optimizare pentru care as putea sa reduc timpul de executie,daca nu este prea mare efortul.Multumesc anticipat!

[•pauldb]

Pe infoarena, limita de timp a fost redusa ca sa se obtina 100 de puncte doar cu solutii mai destepte. Solutia ceruta aici depaseste cu mult nivelul de OJI. Daca totusi esti interesat, este un comentariu al lui Mircea mai sus care explica destul de bine ideea de rezolvare.

[•VisuianMihai]

de ce nu imi afiseaza zecimalele? am declarat <iomanip>, iar rezultatul e de tip double

Cod:

void Afisare()
{
	int i;
	fout<<setprecision(2)<<efmin<<'\n';
	for (i=1; i<N; i++)
		fout<<solmin[i]<<' ';
	fout<<solmin[N];

[•SpiderMan]

Trebuie sa pui si fixed, adica sa faci fout << setprecision (2) << fixed .

[•VisuianMihai]

Trebuie sa pui si fixed, adica sa faci fout << setprecision (2) << fixed .

Of, doamne...  mersi.
Fixed e pentru rotunjire?

[•SpiderMan]

Nup, deci daca nu pui fixed, daca ai 8,23000, o sa ai 8,23 (fara zerouri), in schimb, daca pui fixed, ii zici la PC : ba, tu imi scrii cu X zecimale, si nu stergi cate au muschii tai chef , adica daca ai nr. ala, si vreau sa afiseze cu 10 zecimale, face 8,230000.... (si pune automat cate zerouri vreau eu).

[•balakraz94]

Cum as putea lua si eu 100p la problema asta, deoarece primesc doar WA .

 P.S. Am rezolvat-o in O(3^m) si pe campion iau 100p.

 L.E. S-a rezolvat, nu am mers decat atunci cand am folosit afisarea din C++ cu setprecision fixed.