infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:32:53



Titlul: 026 Energii
Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:32:53
Aici puteţi discuta despre problema Energii (http://infoarena.ro/problema/energii).


Titlul: 026 Energii
Scris de: Hlihor Sergiu din August 29, 2004, 23:31:26
Imi poate da careva unul din testele 10-19 (sau macar unul asemanator),  pt ca nu gasesc niciunde greseala, si am verificat sursa de zeci de ori. Iar ideea de rezolvare zic ca-i buna, pt. ca pot stoarce 50 pct.


Titlul: 026 Energii
Scris de: Rus Cristian din Martie 12, 2005, 14:38:14
Salut, eu am facut problema dinamic, adica am incercat sa o fac si nu stiu ce am gresit, ideea e ca am format un 2 vectori, en care retine true daca se poate pune in functie i unitati de energie si falsa in caz contrar, si cmin care retine costul minim pentru a restaura i unitati de energie...ce am gresit?... :roll:


Titlul: 026 Energii
Scris de: Sergiu din Martie 12, 2005, 15:05:11
Problema asta e cea mai ciudata problema intalnita vreodata. In algoritm  am avut o structura
IF conditie1 then executa a:=b
ELSE IF conditie2 then executa a:=b    si am luat 15pct.

Dupa ce am inlocuit structura de mai sus cu:
  IF onditie1 or conditie2 then a:=b    am luat 90pct.

Si in acest algoritm foloseam acelasi vect pe post de vect boolean si imi murea pe testele 14 si 19. Am folosit acelasi algoritm cu vect boolean separat si culmea lua tot 90 pct dar imi murea pe testele 10 si 13. Dar cum o mana spala pe cealalta, in final am stors suta de pct  :mrgreen:


Titlul: 026 Energii
Scris de: Constantin Cristian din Martie 21, 2005, 23:31:28
A rezolvat cineva problema asta cu programare dinamica?


Titlul: 026 Energii
Scris de: Cosmin Negruseri din Martie 21, 2005, 23:55:04
Pai altfel mi se pare cam greu ... E problema standard de knapsack (problema rucsacului).


Titlul: 026 Energii
Scris de: Rus Cristian din Martie 22, 2005, 18:12:57
Si poate sa imi spuna si mie cineva ce am gresit? ca doar calculam toate energiile care se puteau obtine si retineam costurile minime pentru a obtine acea energie...e tinea minte costul minim pentru a se obtine energia , deci ce nu e bine?...in final calculam minimul dintre e, i>=energia minima ceruta...ce nu e bine?


Titlul: 026 Energii
Scris de: Constantin Cristian din Martie 23, 2005, 15:18:20
Unde gasesc informatii despre probleme standard de knapsack (problema rucsacului)? Un link mi-ar fi de mare ajutor!!! va multumesc


Titlul: 026 Energii
Scris de: Cosmin Negruseri din Martie 23, 2005, 18:35:39
Problema rucsacului e in majoritatea manualelor de a 10-a, si daca dai un search pe google cu "knapsack problem" sigur gasesti ceva linkuri utile ... invata sa te descurci si singur nu sa ti se dea mura in gura ca daca nu cauti si te documentezi singur nu ajungi departe mai ales ca e o problema clasica ... documentatie despre knapsack gasesti in tutorialele de pe topcoder in Cormen (pe care il gasesti la resurse web pe pagina noastra) la tutorialele de pe USACO, numai daca nu vrei sa gasesti nu o sa gasesti.


Titlul: 026 Energii
Scris de: tudor george cristian din Martie 23, 2005, 20:38:50
mie imi da WA la testele 5 si 9. la celelalte merge ... are cineva vreo idee de ce ?


Titlul: 026 Energii
Scris de: Gogu Marian din Martie 23, 2005, 20:58:00
probabil alea sunt testele cu raspuns -1 (nu ai solutie)


Titlul: 026 Energii
Scris de: tudor george cristian din Martie 23, 2005, 21:08:54
nu...am verificat.


Titlul: 026 Energii
Scris de: Mihai Moraru din Martie 23, 2005, 22:13:01
Imi poate spune cineva daca este vreun caz mai ciudat (in afara de cel cu -1), ca nu imi merge pe testul 7.


Titlul: 026 Energii
Scris de: Voicu Octavian din Aprilie 03, 2005, 13:27:44
Eu cred ca e o problema cu evaluatorul... iau 0 la toate testele si am incercat si cu un printf("-1\n"); si tot 0.


Titlul: 026 Energii
Scris de: VladS din Aprilie 03, 2005, 14:05:13
Nu cred ca sunt gresite testele. Sigur gresiti la implementare. Si eu m-am chinuit mult pana sa imi iasa.

Faceti mai intai solutia usoara in M*N cu memorie M*N si apoi daca nu luati nici un WA liniarizati matricea.


Titlul: 026 Energii
Scris de: cristi8 din Aprilie 03, 2005, 14:09:53
Citat
Eu cred ca e o problema cu evaluatorul

dap.. e o problema cu evaluatorul... sa speram ca se rezolva in curand..


Titlul: 026 Energii
Scris de: Bogdan-Cristian Tataroiu din Mai 15, 2005, 09:59:43
Pentru testul
2
8
8 2
10 1
raspunsul e 1 (se foloseste generatorul care face energie 10 > necesarul de 8 ) sau e 2?


Titlul: 026 Energii
Scris de: Rus Cristian din Mai 15, 2005, 10:56:03
raspunsul e 1...se foloseste cel care produce 10 energie...


Titlul: 026 Energii
Scris de: Mihai Pantis din Iunie 09, 2005, 09:42:29
In enunt este specificat ca datele de intrare vor fi in asa fel incat solutia sa fie unica. Simplifica problema in vreun fel aceasta restrictie?


Titlul: 026 Energii
Scris de: Mircea Pasoi din Iunie 09, 2005, 10:21:52
Citat din mesajul lui: supernova
In enunt este specificat ca datele de intrare vor fi in asa fel incat solutia sa fie unica. Simplifica problema in vreun fel aceasta restrictie?


Nu.


Titlul: 026 Energii
Scris de: Tandrau Alexandru din Martie 04, 2006, 15:39:35
Eu am facut programare dinamica in W*G si iau 40 de puncte restu TLE ... Ce complexitate ati facut voi? se poate face mai repede de atat?

Multumesc


Titlul: 026 Energii
Scris de: Gogu Marian din Martie 04, 2006, 16:51:14
O solutie de complexitate O(W*G) trebuie sa ia 100 de puncte fara probleme. Vezi daca mai poti sa mai optimizezi la ea ceva si in primul rand ai grija sa nu folosesti O(W*G) memorie.
Daca faci dinamica pe matrice vezi ca se poate cu memorie liniara.


Titlul: 026 Energii
Scris de: Tandrau Alexandru din Martie 04, 2006, 18:45:34
Mersi

Am transformat in O(2*W) memorie si merge am luat 100. Tot nu inteleg de ce merge mai repede asa decat pe matrice de W*G (care intra in memorie)... dar.. asa o fi. Ms


Titlul: 026 Energii
Scris de: Filip Cristian Buruiana din Martie 04, 2006, 21:34:19
Ca sa declare memorie, programul tau consuma timp... Si de aici e mai eficient cu vectori.


Titlul: 026 Energii
Scris de: Daniel Pasaila din Martie 05, 2006, 11:52:42
Cand accesezi un element dintr-o matrice mare, timpul nu este tocmai neglijabil. La multe probleme de pe infoarena trebuie sa optimizezi destul de mult algoritmul pentru ca sa iei punctaj maxim:)


Titlul: 026 Energii
Scris de: Marius Stroe din Martie 05, 2006, 18:21:06
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 :P.


Titlul: 026 Energii
Scris de: Paduraru Ciprian - Ionut din Martie 17, 2006, 23:31:40
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...  [-o<


Titlul: 026 Energii
Scris de: Gogu Marian din Martie 17, 2006, 23:54:56
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).


Titlul: 026 Energii
Scris de: Paduraru Ciprian - Ionut din Martie 18, 2006, 15:52:04
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 :D ?[/code]

Later Edit: oh stiu unde gresesc :) ms :P

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


Titlul: Raspuns: 026 Energii
Scris de: Vlad Popa din Aprilie 04, 2006, 18:45:18
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 ](*,)



Titlul: Raspuns: 026 Energii
Scris de: Tandrau Alexandru din Aprilie 04, 2006, 18:54:06
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;


Titlul: Raspuns: 026 Energii
Scris de: Vlad Popa din Aprilie 04, 2006, 19:02:50
Interesant... Mersi ptr idee... :)


Titlul: Raspuns: 026 Energii
Scris de: Stefan Dobrin Cosmin din Ianuarie 02, 2007, 18:49:35
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? :readthis:


Titlul: Raspuns: 026 Energii
Scris de: Bondane Cosmin din Ianuarie 02, 2007, 20:36:46
Cmin - costul minim necesar repornirii centralei sau -1 daca nu este suficienta energie pentru repornire

Deci daca initializezi cu 0 ratezi cazu cu -1.  :)


Titlul: Raspuns: 026 Energii
Scris de: Stefan Dobrin Cosmin din Ianuarie 02, 2007, 23:36:15
fals...
1. Exista un singur test cu acest caz;(stiu pentru ca initial nu am facut 2.  :harhar:)
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....


Titlul: Raspuns: 026 Energii
Scris de: Marius Stroe din Ianuarie 03, 2007, 00:03:16
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? :readthis:

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.


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Septembrie 29, 2007, 21:36:19
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???


Titlul: Răspuns: 026 Energii
Scris de: Mircea Dima din Septembrie 29, 2007, 22:03:47
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 ...


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 27, 2007, 02:44:53
Stie cineva care este testul 9 pentru aceasta problema?


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Octombrie 27, 2007, 10:03:10
Testele nu se fac publice...


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 27, 2007, 16:22:34
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


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Octombrie 27, 2007, 17:50:17
Ce intelegi printr'un set de date apropiat?


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 27, 2007, 19:23:51
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.


Titlul: Răspuns: 026 Energii
Scris de: Ionescu Vlad din Octombrie 27, 2007, 19:26:15
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.


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 27, 2007, 19:33:18
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.


Titlul: Răspuns: 026 Energii
Scris de: Stefan Istrate din Octombrie 27, 2007, 19:51:05
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. :thumbup:


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 27, 2007, 19:54:11
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. :thumbup:

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


Titlul: Răspuns: 026 Energii
Scris de: Adrian Diaconu din Octombrie 28, 2007, 17:10:14
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.


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 28, 2007, 17:13:42
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?


Titlul: Răspuns: 026 Energii
Scris de: Adrian Diaconu din Octombrie 30, 2007, 21:04:01
Nu gresesti, dar nu ti se pare suficient de mare 10 000 * 1000, cum calculezi valorile ca sa iti intre in timp ?


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 31, 2007, 12:54:41
Nu gresesti, dar nu ti se pare suficient de mare 10 000 * 1000, cum calculezi valorile ca sa iti intre in timp ?

Am scris mai sus cum calculez. Mi se pare ciudat ca 19 teste trec cu timpi sub 5 ms si unul pica dupa 100 si ceva de ms. In plus conditia din enuntul problemei (1< eg,gg < 10001) e falsa, pentru ca se pare ca sunt teste pt care gg e 0 (!?!?).
Sa inteleg ca exista un singur test cu valori mari?


Titlul: Răspuns: 026 Energii
Scris de: Andrei Grigorean din Octombrie 31, 2007, 13:17:39
Pentru urmatorul test, ce face programul tau?

Cod:
2
10
7 10000
8 10000

M-am uitat in codul tau si eroarea vine de la faptul ca declari maxsize prea mic. Ar trebui sa fie 10.000.000, nu 1000. Dupa cum a spus si Adi mai sus, incerca sa regandesti problema, pentru ca solutia ta nu merge pentru costuri mari. Faptul ca ai luat 95 de pct nu inseamna ca ai un mic bug in implementare, ci ca testele sunt proaste. Cu maxsize = 10.000.000 (atat cat ar trebui sa fie), primesti Killed by signal 11, pentru ca declari prea multa memorie. Daca il pun 1.000.000, desi iti intra in memorie, primesti TLE. Pentru a verifica daca o solutie e buna, incearca sa iti dai teste maxime. Un exemplu pentru problema aceasta ar fi:

Cod:
1000
1000
1 10000
1 10000
.............
1 10000

G = 1000, W = 1000, si fiecare generator are EG = 1, si EC = 10000. Raspunsul corect este 10.000.000


Titlul: Răspuns: 026 Energii
Scris de: Piros Lucian din Octombrie 31, 2007, 13:42:55
Pentru urmatorul test, ce face programul tau?

Cod:
2
10
7 10000
8 10000

M-am uitat in codul tau si eroarea vine de la faptul ca declari maxsize prea mic. Ar trebui sa fie 10.000.000, nu 1000. Dupa cum a spus si Adi mai sus, incerca sa regandesti problema, pentru ca solutia ta nu merge pentru costuri mari. Faptul ca ai luat 95 de pct nu inseamna ca ai un mic bug in implementare, ci ca testele sunt proaste. Cu maxsize = 10.000.000 (atat cat ar trebui sa fie), primesti Killed by signal 11, pentru ca declari prea multa memorie. Daca il pun 1.000.000, desi iti intra in memorie, primesti TLE. Pentru a verifica daca o solutie e buna, incearca sa iti dai teste maxime. Un exemplu pentru problema aceasta ar fi:

Cod:
1000
1000
1 10000
1 10000
.............
1 10000

G = 1000, W = 1000, si fiecare generator are EG = 1, si EC = 10000. Raspunsul corect este 10.000.000

Great...multam de tip....am incercat sa ma joc cu acel maxsize pt a intelege ce e cu acel test care pica (si probabil ca ultima sursa e cu maxsize prea mic).


Titlul: Răspuns: 026 Energii
Scris de: nash mit din Ianuarie 15, 2008, 10:47:57
 E o chestie care nu o intaleg ...
      Problema cere "o solutie de cost minim, pentru a produce o cantitate de energie egala sau mai mare cu cea necesara repornirii centralei"  , adica daca eu tebuie sa fac rost de G - energie cu cost min ... si observ ca nu se poate forma cantitatea acesta de energie atunci incep sa caut in G+1 , G+1 ... etc .. energie care se poate forma de cost min .

 Eu fac ceva in genul urmator ...
Cod:
for(i=1;i<=N;i++)
         for(j=1;j<=2*G;j++) {
             Energie[i%2][j] = max( verifica((i-1)%2,j-reactor[i]) , Energie[(i-1)%2][j] );
             cost_min[i%2][j]=MAXINT;
             if(Energie[i%2][j]) {
                if(verifica((i-1)%2,j-reactor[i])) cost_min[i%2][j]=min(cost_min[(i-1)%2][j-reactor[i]]+cost[i] , cost_min[i%2][j]);
                cost_min[i%2][j]= min(cost_min[i%2][j],cost_min[(i-1)%2][j]);
             }
         }

E logic ca trebuie sa iasa din timp ( fac pana la 2*G ) dar nu e logic de ce pe cele care intra .. da raspuns gresit ..


Titlul: Răspuns: 026 Energii
Scris de: nash mit din Ianuarie 15, 2008, 23:58:43
Nu are nimeni nici o idee ?


Titlul: Răspuns: 026 Energii
Scris de: Barsan Paul din Ianuarie 16, 2008, 10:12:44
pai nu inteleg dece mergi pana la 2*G, G ii numarul de generatoare, poate fi un singur generator care produce 10 000 "1 < EGi,CGi < 10001 "
problema ii un knapsack, prima data trebuie sa o rezolvi cu o matrice c[nr_gen][en]-costul minim cu care poti obtine energia en cu nr_gen generatoare, si mergi cu en pana la WMAX .Dupa ce ai rezolvat-o cu matrice incerci sa reduci memoria la 2 linii , sau mai mult poti folosi un singur vector :)
LE: sau stai, ca la tine N ii nr de generatoare, atunci cand incerci sa introduci un generator nou verifici starea c[nr_gen-1][en-generator[nr_gen]] si nu (i-1)*2 si 2*i , s-a discutat mult la problema asta si poti gasi detalii in paginile anterioare...


Titlul: Răspuns: 026 Energii
Scris de: nash mit din Ianuarie 16, 2008, 23:56:07
daca ai citi bine rezolvarea mea .. ti-ai da seama ca am folosit problema rucsacului .. etc ... chestia cu liniic ...ca e nevioe decat de doua .. daca te-ai utia .. chiar cu 2 linii lucrez ... :P .. lucrez  " % 2"  ...


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Ianuarie 17, 2008, 00:21:28
Eu am facut asa:
Am facut un rucsac pt a gasi energiile ce se pot obtine si daca gaseam o valoare mai mare decat G si cu costul < minim, actualizam minimul (initializat initial cu o valoare destul de mare). Mi'am creat o structura in care retin costul si energia unui generator si 2 vectori pe care ii construiesc la rucsac: E[ i ] == 1 => energia se poate obtine folosind generatoarele altfel E[ i ] == 0 si C[ i ] - costul necesar obtinerii energiei i ...


Titlul: Răspuns: 026 Energii
Scris de: mircea balta din Ianuarie 19, 2008, 15:27:47
eu trimis o problema( energii),merge,dar evaluatorul imi da doar 0p imi apare eroare de compliare 


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Ianuarie 19, 2008, 15:31:03
Nu e un bug ci sursa ta e de vina.. daca citeai putina documentatie, stiai ca in loc de void main() tre sa pui int main() si functia sa returneze 0.


Titlul: Răspuns: 026 Energii
Scris de: mircea balta din Ianuarie 19, 2008, 15:56:05
ms :aha:


Titlul: Răspuns: 026 Energii
Scris de: Lazar Vlad din Ianuarie 28, 2008, 21:04:07
am incercat cu greedy si imi da 45 puncte pe sursa


Titlul: Răspuns: 026 Energii
Scris de: Bondane Cosmin din Ianuarie 28, 2008, 21:32:00
Incearca dinamica si o sa iei 100.  :)
Daca nu reusesti sa te prinzi, sfaturi gasesti in pag anterioare ale acestui subiect sau vezi ca sursele la pb asta sunt publice. Spor!


Titlul: Răspuns: 026 Energii
Scris de: Posea Elena din Aprilie 24, 2008, 19:28:26
Imi cer scuze ca scriu aici...am mai multe manuale si carti de C++ (cum ar fi "Algoritmi fundamentali in C++" de Doina Logofatu), si lucrez de aproximativ 2 saptamani, dar tot nu reusesc sa inteleg programarea dinamica.... :?, puteti sa-mi recomandati vreo carte care sa trateze mai clar subiectul?(am cautat linkuri, dar nu am gasit cine stie ce)Multumesc!


Titlul: Răspuns: 026 Energii
Scris de: Andrei Grigorean din Aprilie 24, 2008, 19:31:18
Din cormen ai citit? Este un capitol intreg despre dinamica acolo...


Titlul: Răspuns: 026 Energii
Scris de: Posea Elena din Aprilie 24, 2008, 19:34:33
nu stiu... cormen e carte sau problema?  :-s


Titlul: Răspuns: 026 Energii
Scris de: Andrei Grigorean din Aprilie 24, 2008, 19:36:17
cormen, CLR sau biblia... se refera la cartea "Introducere in algoritmi". O poti cumpara de pe net in limba romana, sau ai o varianta in engleza, online, aici (http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm).


Titlul: Răspuns: 026 Energii
Scris de: Posea Elena din Aprilie 24, 2008, 19:37:03
Multumesc mult! :D
Pentru cine nu a inteles programarea dinamica, eu m-am lamurit din cartea Emanuelei Cerchez,"Culegere de probleme pentru liceu", editura Polirom. \:D/


Titlul: Răspuns: 026 Energii
Scris de: Irina Grosu din Iulie 27, 2008, 16:42:11
tinand cont ca nu stiu programare dinamica am incercat sa fac aceasta problema cu un greedy, dar iau doar 45 pct. La toate cele 11 teste pe care iau 0 primesc WA.
Este din cauza ca gresesc eu ceva, sau pe aceasta problema nu pot lua 100 cu greedy?


Titlul: Răspuns: 026 Energii
Scris de: Paul-Dan Baltescu din Iulie 27, 2008, 19:30:40
Nu, nu ar trebui sa poti lua 100 cu greedy, deoarece nu este o rezolvare corecta (presupun ca iti poti gasi exemple usor, pentru care nu ar trebui sa mearga rezolvarea ta). Ar fi bine sa inveti programare dinamica, nu cred ca o sa te descurci la concursuri fara.


Titlul: Răspuns: 026 Energii
Scris de: George Popoiu din Ianuarie 10, 2010, 20:38:25
Fac dinamica si tin o matrice Cost(i,j) = costul minim necesar pentru a da o energie >=j, folosind primele i generatoare si iau 0 puncte.

intr-un vector sum(i) retin suma energiilor primelor i generatoare.

Uitati cum fac.

Cod:
for(int i=1;i<=W;i++)Cost[0][j]=INF;
for(int i=1;i<=G;i++)
    {
   for(int j=1;j<=W;j++)
       {
       if( j-E[i]>=0 && sum[i-1]>=j-E[i] && Cost[i-1][j-E[i]]+C[i]<Cost[i-1][j] ) Cost[i][j]=Cost[i-1][j-E[i]]+C[i];
       else Cost[i][j]=Cost[i-1][j];
       }
    }

Am citit in topic ca au mai incercat si altii asa si nu le-a iesit si vreau sa stiu ce e gresit in judecata, ca sa inteleg mai bine dinamica. Imi puteti explica, va rog?  :sad:


Titlul: Răspuns: 026 Energii
Scris de: Vlad Tarniceru din Martie 26, 2010, 17:19:16
am si eu 2 intrebari :?
un generator poate fi pornit o data sau de mai multe ori?
si daca am :
  3
  4
  100 2
  200 3
  300 4
 
afisez -1?(pentru ca am dat prea multa energie?)

sau -1 afisez in cazul

  2
  1000
  1 2
  2 3

(pentru ca fol generatorul decat o singura data)


Titlul: Răspuns: 026 Energii
Scris de: George Popoiu din Martie 26, 2010, 18:18:46
O data.


Titlul: Răspuns: 026 Energii
Scris de: speedzeal din Octombrie 11, 2010, 13:26:38
Testele nu corepund cu restrictiile din enunt:
1 < EGi,CGi < 10001
Am verificat cu assert.
http://infoarena.ro/job_detail/491459


Titlul: Răspuns: 026 Energii
Scris de: Simoiu Robert din Octombrie 11, 2010, 13:38:41
Da, trebuie corectat asa : 0 <= EGi, CGi < 10001 . ( http://infoarena.ro/job_detail/491472?action=view-source )


Titlul: Răspuns: 026 Energii
Scris de: Cosmin Poieana din Decembrie 29, 2010, 01:49:52
Am doua surse cu o foarte mica diferenta:
Prima sursa good (http://"http://infoarena.ro/job_detail/517537?action=view-source")
A doua sursa bad (http://"http://infoarena.ro/job_detail/517533?action=view-source")

Diferenta intre good si bad este ca am dat swap la dimensiuni intr-o matrice, adica am inversat liniile cu coloanele schimband de asemenea si rolul indicilor pentru a avea aceleasi rezultate, insa la a doua sursa primesc TLE (time limit exceeded) si nu inteleg de ce fiindca atat ordinul de complexitate, numarul cat si resursele alocate instructiunilor raman aceleasi.
Mai exact din O(g*w) am facut O(w*g).


Titlul: Răspuns: 026 Energii
Scris de: Pripoae Teodor Anton din Decembrie 29, 2010, 03:59:29
Spargi cache-ul.


Titlul: Răspuns: 026 Energii
Scris de: Cosmin Poieana din Decembrie 29, 2010, 15:11:02
Spargi cache-ul.
Asa si in romana :D ?


Titlul: Răspuns: 026 Energii
Scris de: Simoiu Robert din Decembrie 29, 2010, 15:34:37
Adica faci ceva de genul : A[ j ][ i ] in loc de A[ i ][ j ] ( adica primul for e j si al doilea e i ) .
[LE] : http://infoarena.ro/12-ponturi-pentru-programatorii-cc , Pont #3


Titlul: Răspuns: 026 Energii
Scris de: Vlad Schnakovszki din Martie 10, 2011, 12:37:34
Am pierdut un pariu :D

Uitati-va aici:
http://infoarena.ro/job_detail/551091?action=view-source


Titlul: Răspuns: 026 Energii
Scris de: Mardare Rares din Martie 10, 2011, 15:05:13
Am pierdut un pariu :D

Uitati-va aici:
http://infoarena.ro/job_detail/551091?action=view-source
=))))))))))))))))))))))

incredibil hahahahah. mai vazusem un hello world cu zeci de constante, dar asta intrece orice chestie =))


Titlul: Răspuns: 026 Energii
Scris de: Walter Bruce Willis din Martie 10, 2011, 21:34:27
Am pierdut un pariu :D

Uitati-va aici:
http://infoarena.ro/job_detail/551091?action=view-source
la ce te ajuta?


Titlul: Răspuns: 026 Energii
Scris de: Vlad Schnakovszki din Martie 11, 2011, 11:25:36
Am pierdut un pariu, logic e sa nu trebuiasca sa fac ceva bun pentru mine  :)


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Martie 11, 2011, 11:53:02
Cam off-topic discutia asta... Reveniti la subiect.


Titlul: Răspuns: 026 Energii
Scris de: UAIC.VlasCatalin din Iulie 10, 2011, 01:29:14
Spunetimi va rog ce nu e bine in logica mea:
1. Calculez eficienta fiecarui generator, si sortez descrescator generatoarele dupa eficienta;
2. Adun energia generatoarelor in s1 si costul lor in s2 pina cind s1>=energia necesara, sau i=g;
3. Daca s1= energia necesara, atunci solutia etse s2, daca s1<w si i=g atunci nu avem solutie,
 daca i<g si s1<w atunci caut urmatorul generator care poate sa compenseze neajunsul de energie si care are un cost minim,
costul pentru valoarea respectiva il adun cu s2 si scriu solutia s2;
-----Spunetimi ce nu e corect in logica mea, toate testele de pe forum, si testul exemplu merge bine, dar obtin numai 50p cu WA
pe celelalte 50% din teste, iar daca logica e corecta, poate se uita cieva pe sursa mea si sugereaza niste neajunsuri pls, as fi foarte recunoscator, ms.


Titlul: Răspuns: 026 Energii
Scris de: Cristian Lambru din Iulie 10, 2011, 01:46:48
Rezolvarea ta este greedy :) !

Aceasta problema se face cu programare dinamica. Incearca sa te uiti de knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem) (problema rucsacului) pe internet.


Titlul: Răspuns: 026 Energii
Scris de: UAIC.VlasCatalin din Iulie 10, 2011, 12:56:53
ms pentru sfat (Lambru Andrei Cristian) am folosit formula de recurenta, de pe wiki, numai ca in loc de max, am pus min si am luat 100 :ok:, dar totusi ceva e straniu in rezolvarea dinamica, sau poate eu am gresit ceva, dar sursa pe care am luat 100 nu merge deloc pe teste mici, chiar nisi testul exemplu nu se executa corect ??? ???


Titlul: Răspuns: 026 Energii
Scris de: Razvan din Decembrie 01, 2011, 12:42:30
pentru toti !
Problema nu prea este formulata bine
1. Se poate intelege ca trb sa iei un generator care are energia mai mare sau egala cu w ( dat ) si apoi verifici costurile .
2. Se poate intelege ca trb sa aduni costurile si sa le verifici e complicat oricum
:| am stat si am incercat sa rezolv (1) si am reusit ...  dar cu adevarat problema se rezolva cu (2);


Titlul: Răspuns: 026 Energii
Scris de: Gabriel Bitis din Decembrie 01, 2011, 13:12:40
E formulat bine enuntul. Probabil trebuie sa mai exersezi cu intelegerea problemelor. De 7 ani de cand e publica problema au fost sute de utilizatori care au reusit sa inteleaga enuntul si sa rezolve bine problema.


Titlul: Răspuns: 026 Energii
Scris de: CHIRILA ADRIAN din Ianuarie 26, 2013, 14:52:12
#include <fstream.h>
#include <iostream.h>
  int main()
  { ifstream f("energii.in");
    ofstream gf("energii.out");
    short int g,w,i,c,e,s;
    float ef[1001],v[1001],u[1001],aux;
    f>>g;
    f>>w;
    for(i=1;i<=g;i++)
    {f>>v>>u;}
    f.close();
     for(i=1;i<=g;i++)
     {  ef=v/u;}
       do
       {
         c=1;
       for(i=1;i<=g-1;i++)
       { if (ef<ef[i+1])
           {aux=v;
        v=v[i+1];
        v[i+1]=aux;
        aux=u;
        u=u[i+1];
        u[i+1]=aux;
        aux=ef;
        ef=ef[i+1];
        ef[i+1]=aux;
        c=0;
        } } }
    while (c==0);
         s=0;
         i=1;
         e=0;
     do
       { e=e+v;
         s=s+u;
         i++; }
     while((i<=g) && (e<w));
     gf<<s;
         return 0;
      }
Cand trimit sursa,apar o gramada de erori la compilare si nu stiu de ce.. ](*,)


Titlul: Răspuns: 026 Energii
Scris de: Pirtoaca George Sebastian din Ianuarie 26, 2013, 15:30:42
In loc de
Cod:
#include <fstream.h>
#include <iostream.h>

Scrie:
Cod:
#include <fstream.h>
#include <iostream.h>
using namespace std;

si o sa mearga. Succes!  :ok:



Titlul: Răspuns: 026 Energii
Scris de: CHIRILA ADRIAN din Ianuarie 26, 2013, 15:45:07
Multumesc!


Titlul: Răspuns: 026 Energii
Scris de: Alexandru Valeanu din Februarie 16, 2013, 21:03:50
Imi poate spune si mie cineva daca e ceva special cu testul 14. Iau 95p cu WA pe 14 si nu inteleg de ce...


Titlul: Răspuns: 026 Energii
Scris de: Mercea Otniel din Decembrie 24, 2013, 16:34:23
de ce nu iau 100 cu problema rucsacului implementata cu greedy?


Titlul: Răspuns: 026 Energii
Scris de: patrutoiu andrei din Septembrie 18, 2014, 11:15:16
gigel ar trebui sa porneasca centrala cat mai repede ca sa faca cat mai multi bani...nu ar trebui sa piarda vremea pe infoarena asteptand solutii de la noi. lenesu-le!! ](*,) ](*,) ](*,)


Titlul: Răspuns: 026 Energii
Scris de: Gafton Mihnea Alexandru din Noiembrie 27, 2014, 18:05:09
Buna ! Am luat 85 cu knapsack pe doua linii si am 3 WA(printre care si testul 9 de care am auzit + T14, T19)
Ce fac eu este exact knapsack considerand greutatea maxima W maxim de la limite. dupaia merg liniar pe linia de final si caut prima valoare mai mare sau egala cu W din input(initial am facut  cautarea binara dar am avut niste probleme la implementare si probabil ca o sa revin la idee dupa ce rezolv WA - urile).
Daca aveti vreo idee care e problema as aprecia orice ajutor, Multam!


Titlul: Răspuns: 026 Energii
Scris de: Mercea Otniel din Decembrie 05, 2014, 22:09:52
de ce i-au TLE pe sursa asta?


#include<iostream>
using namespace std;
int greu[10001],pierd[10001],castig[1000000],i,n,s=999999999,cautat,smax,j;
#include<fstream>
ifstream f("energii.in");
ofstream g("energii.out");
int main()
{
   f>>n>>cautat;
    for(i=1;i<=n;i++)
    {f>>greu>>pierd;
        smax=smax+greu;
    }
 for(i=1;i<=smax;i++)
    castig=999999999;
    for(i=1;i<=n;i++)
        for(j=smax-greu;j>=0;j--)
            if(castig[j+greu]>castig[j]+pierd)
        {
            castig[j+greu]=castig[j]+pierd;
        }
        int maximul=999999999;
        for(i=cautat;i<=smax;i++)
            if(maximul>castig)
                maximul=castig;
      if(maximul!=999999999)
      g<<maximul;
      else
        g<<"-1";
}


Titlul: Răspuns: 026 Energii
Scris de: Ionut Redox din Decembrie 07, 2014, 09:57:03
100% merge.

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f("energii.in");
    ofstream s("energii.out");
    int w,g,eg[30],cg[30],i,aux,n=0;
    f>>g>>w;
    for(i=1;i<=g;i++)
        f>>eg>>cg;

    for(i=1;i<g;i++)
        for(int j=i+1;j<=g;j++)
        if(cg>cg[j])
        {
            aux=cg;
            cg=cg[j];
            cg[j]=aux;
            aux=eg;
            eg=eg[j];
            eg[j]=aux;
        }

    for(i=1;i<=g;i++){
        if(eg>=w)
        {
            s<<cg;
            break;
        }
        else if(eg<w)
            n++;
    }
    if(n)
        s<<-1;



    }



Titlul: Răspuns: 026 Energii
Scris de: Laszlo Janos din Martie 14, 2015, 17:41:14
programul nu afiseaza solutia corecta pentru datele:
3
8
3 3
4 5
6 7


Titlul: Răspuns: 026 Energii
Scris de: Laszlo Janos din Martie 14, 2015, 17:43:42
programul nu afiseaza solutia corecta pentru datele:
3
8
3 3
4 5
6 7


Titlul: Răspuns: 026 Energii
Scris de: Neghina Dragos din Martie 26, 2017, 15:27:23
Buna ziua!
ideea mea este simpla: o dinamica in care a[ i ] [ j ] reprezinta costul minim pentru a produce j energie folosind cel mult i generatoare.  iau WA pe testele 14 si 19 de care s-a mai intrebat, dar nu am gasit nimic sa ma ajute, asa ca rog pe cineva sa imi dea un indiciu sau un exemplu contradictoriu.


Titlul: Răspuns: 026 Energii
Scris de: Alex S Hill din August 05, 2017, 17:08:00
M-am tot chinuit ca i-au 90 de pt pana cand am trecut prin comentarii doar ca sa aflu ca costurile pot fi si 0.
De ce nu a fost modificata cerinta?
Am schimbat si am luat 100.