026 Energii

[•cmiN]

Am doua surse cu o foarte mica diferenta:
Prima sursa good
A doua sursa bad

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

[•toni2007]

Spargi cache-ul.

[•cmiN]

Spargi cache-ul.

Asa si in romana ?

[•SpiderMan]

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

[•shnako]

Am pierdut un pariu

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

[•mrares]

Am pierdut un pariu

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

[•brucewillis]

Am pierdut un pariu

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

la ce te ajuta?

[•shnako]

Am pierdut un pariu, logic e sa nu trebuiasca sa fac ceva bun pentru mine 

[•gabitzish1]

Cam off-topic discutia asta... Reveniti la subiect.

[•ctlin04]

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.

[•maritim]

Rezolvarea ta este greedy !

Aceasta problema se face cu programare dinamica. Incearca sa te uiti de knapsack problem (problema rucsacului) pe internet.

[•ctlin04]

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 , 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

[•span7a]

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

[•gabitzish1]

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.

[•Sapientia]

#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..

[•SebiSebi]

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! 

[•Sapientia]

Multumesc!

[•AlexandruValeanu]

Imi poate spune si mie cineva daca e ceva special cu testul 14. Iau 95p cu WA pe 14 si nu inteleg de ce...

[•otniel]

de ce nu iau 100 cu problema rucsacului implementata cu greedy?

[•patrutoiuandrei]

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!!

[•fluture.godlike]

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!

[•otniel]

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";
}

[•RedoxGFXx]

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;



    }

[•janoslaszlo]

programul nu afiseaza solutia corecta pentru datele:
3
8
3 3
4 5
6 7

[•janoslaszlo]

programul nu afiseaza solutia corecta pentru datele:
3
8
3 3
4 5
6 7