026 Energii

[•Marius]

Pentru ca la OJI ne este servit un Borland C++ cred ca ar fi bine sa faci si acasa programe cat mai optimizate din punct de vedere al memoriei. Nu cred ca o sa vrei vreodata sa te gandesti cum iti "incadrezi" ideea in memorie, si in cel mai rau caz sa nu "incapa".

La problemele astea tip rucsac poti sa faci totul cu un vector .

[•cip]

am si eu o problema ... iau TLE folosind o dinamica pe matrice cu 2 linii as putea macar sa primesc un test mai dificil decat cel propus sa vad macar dak am gandit bine dinamica PLS...  

[•gogu]

Uite un test mai mare care sper sa te ajute:

Cod:

15
100
11 12
15 17
13 18
11 17
9 13
13 8
9 6
18 2
20 6
8 10
16 17
11 10
12 8
19 17
2 7

Raspunsul e 57 (sper ca e bine).

[•cip]

la testul

Cod:

 
15
100
11 12
15 17
13 18
11 17
9 13
13 8
9 6
18 2
20 6
8 10
16 17
11 10
12 8
19 17
2 7 

raspunsul e 30 nu ?[/code]

Later Edit: oh stiu unde gresesc ms

[Editat de bogdan2412: Nu mai posta de 3 ori consecutiv... editeaza-ti posturile precedente   ]

[•vlad_popa]

Salut la toti...
Ma chinue problema asta d ceva timp...si nu stiu unde am putut sa gresesc...Daca ma poate ajuta cineva sa imi explice unde gresesc i-as ramane recunoscator...

Eu folosesc la aceasta problema programarea dinamica...si anume: construesc o matrice m[p][j]=costul minim care depaseste cantitatea de energie j, folosind exact p generatoare.
Astfel obtin formula: m[p][j]=min ( m[p-1][j-EG[p]]+CG[p] , m[p-1][j ] ).
Desi obtzin numai 10 Pcte la problema asta nu intzeleg unde am gresit

[•alexthero]

Eu fac asa

Cod:

                        energie:=i-e[j];
                        if energie<=0 then begin
                                if j=1 then s1[i]:=cost[j]
                                else s1[i]:=min(s2[i],cost[j]);
                        end
                        else begin
                                if j=1 then s1[i]:=maxlongint div 2
                                else s1[i]:=min(s2[i],cost[j]+s2[energie]);
                        end;

[•vlad_popa]

Interesant... Mersi ptr idee...

[•cosminstefanxp]

As avea si eu o intrebare? Se poate ca un cost sa fie 0? Conform cerintei nu se poate. Dar daca initializez vectorul costurilor cu -1, si fac modificarile de rigoare pentru a fi inclus si cazul in care un cost este 0, iau 100 puncte. Daca initializez cu 0 si exclud cazul acesta iau 90. Care e explicatia?

[•cos_min]

Cmin - costul minim necesar repornirii centralei sau -1 daca nu este suficienta energie pentru repornire

Deci daca initializezi cu 0 ratezi cazu cu -1. 

[•cosminstefanxp]

fals...
1. Exista un singur test cu acest caz;(stiu pentru ca initial nu am facut 2.  )
2. M-am asigurat de asta. Pur si simplu daca nu s-a trecut peste w in generarea vectorului de costuri inseamna ca nu se poate atinge.

Deci nu asta e problema....

[•Marius]

As avea si eu o intrebare? Se poate ca un cost sa fie 0? Conform cerintei nu se poate. Dar daca initializez vectorul costurilor cu -1, si fac modificarile de rigoare pentru a fi inclus si cazul in care un cost este 0, iau 100 puncte. Daca initializez cu 0 si exclud cazul acesta iau 90. Care e explicatia?

Mie mi se pare mai normal sa initializezi cu un "infinit". Pe 8 teste exista energii cu costul 0. Probabil testele au fost create cu o functie random() si rezultatul luat modulo 10001.

Poti sa te convingi singur:

Cod:

if (cost[i] == 0)
     for (;;) ;

Si va fi TLE pe testele unde intalnesti un cost 0.

[•gabitzish1]

Uite un test mai mare care sper sa te ajute:

Cod:

15
100
11 12
15 17
13 18
11 17
9 13
13 8
9 6
18 2
20 6
8 10
16 17
11 10
12 8
19 17
2 7

Raspunsul e 57 (sper ca e bine).

mie imi da 62 cu o sursa cu care iau 90p+2 wa... e gresit raspunsul meu???

[•blasterz]

Uite un test mai mare care sper sa te ajute:

Cod:

15
100
11 12
15 17
13 18
11 17
9 13
13 8
9 6
18 2
20 6
8 10
16 17
11 10
12 8
19 17
2 7

Raspunsul e 57 (sper ca e bine).

mie imi da 62 cu o sursa cu care iau 45p(primele 9 teste)+tle... e gresit raspunsul meu???

Si mie imi da 57 cu sursa de 100 ...

[•pirosl]

Stie cineva care este testul 9 pentru aceasta problema?

[•gabitzish1]

Testele nu se fac publice...

[•pirosl]

Testele nu se fac publice...

Si care a fi motivul pentru acest lucru? Cum poti (sa te pregatesti) daca nu vezi pe ce set de date generezi un raspuns gresit?  (eg. vezi usaco unde la primul test care pica ti se spune care este setul de date pe care problema ta a picat)
Daca nu se fac publice macar sa se dea un set de date apropiat

[•gabitzish1]

Ce intelegi printr'un set de date apropiat?

[•pirosl]

Ce intelegi printr'un set de date apropiat?

Hai sa nu incepem cu polemicile......asta nu ma ajuta sa detectez eroarea care o am in implimentare.
Stie cineva datele folosite pentru testul 9? Careva dintre admini? Iau 95 la problema asta cu toate testelor rulate sub 5 ms ... mai putin testul 9 (dupa aprox 120 ms - ciudat  )....insa nu resusesc sa-mi dau seama ce anume gresesc. Poate daca vad testul 9 reusesc sa ma prind.

[•Dastas]

Nu cred ca un admin iti va da testul 9. Mai bine spui cum te-ai gandit sa rezolvi problema si o sa incercam sa te ajutam, eventual cu un contraexemplu.

[•pirosl]

Nu cred ca un admin iti va da testul 9. Mai bine spui cum te-ai gandit sa rezolvi problema si o sa incercam sa te ajutam, eventual cu un contraexemplu.

Imi convine si asa.
Ideea e simpla: calculez cantitatea maxima de energie care se poate obtine cu costuri 1, 2, 3,.... (salvez intr-un vector a)  (vectorul a e simplu de calculat: a = max { vj + a[i-j], cj<= i}, unde vj e energia produsa de generatorul j si cj e costul .... evident am grija sa nu aleg de mai multe ori acelasi generator)
Raspunsul e primul i pentru care a(i) >=w
Pentru cazul -1: initial adun toate energiile - daca suma e mai mica decat w raspunsul e -1;

Astept contraexemple.

[•stef2n]

Nu cred ca un admin iti va da testul 9. Mai bine spui cum te-ai gandit sa rezolvi problema si o sa incercam sa te ajutam, eventual cu un contraexemplu.

@Dastas: Nu cred ca ai pus bine problema. Daca ia 95 nu pare o eroare la cum a gandit rezolvarea. Pare o eroare la implemetare.

@pirosl: Mi s-a intamplat si mie de multe ori sa iau 95 de puncte si e foarte greu sa gasesti buba. Incearca sa rescrii sursa de la 0. Poate esti un pic mai atent cand regandesti problema.

[•pirosl]

Nu cred ca un admin iti va da testul 9. Mai bine spui cum te-ai gandit sa rezolvi problema si o sa incercam sa te ajutam, eventual cu un contraexemplu.

Nu cred ca ai pus bine problema. Daca ia 95 nu pare o eroare la cum a gandit rezolvarea. Pare o eroare la implemetare.

Mi s-a intamplat si mie de multe ori sa iau 95 de puncte si e foarte greu sa gasesti buba. Incearca sa rescrii sursa de la 0. Poate esti un pic mai atent cand regandesti problema.

Pai tocmai ca am scris de 2 ori sursa de la zero (cu aceasi idee)....si nu reusesc sa trec de acest fatidic 95. Am incercat si alte idei (ies mai rau la punctaj...insa testul 9 tot nu-l trec)
Eu ma gandeam ca testul 9 contine un caz particular sau o kestie care mie imi scapa complet....sau whatever...ideea este ca nu resusesc sa-mi dau seama daca am gresit la implementare, daca am scapat ceva la implementarea ideii.....in consecinta iacatama-s pe forum cu intrebarea...insa se pare ca nici asta nu prea imi e de mare ajutor (iar daca rescriu acum de la zero....probabil o sa fac din nou aceasi greseala )

[•DITzoneC]

Si cat de mare este vectorul acela a, pe care il calulezi?
Rezultatul poate fi destul de mare.

Incearca sa faci ceva de genul H = costul minim ca sa produci i energie, raspunsul va fi minim din H cu i > W.

[•pirosl]

Si cat de mare este vectorul acela a, pe care il calulezi?
Rezultatul poate fi destul de mare.

Incearca sa faci ceva de genul H = costul minim ca sa produci i energie, raspunsul va fi minim din H cu i > W.

Rezultatul nu poate fi mai mare de 10001*1001, sau gresesc?

[•DITzoneC]

Nu gresesti, dar nu ti se pare suficient de mare 10 000 * 1000, cum calculezi valorile ca sa iti intre in timp ?