003 Bursa

[•wefgef]

Aici puteţi discuta despre problema Bursa.

[•a_h1926]

As vrea sa va rog, daca ma poate ajuta cineva la problema Bursa. Am gasit o solutie cu programare dinamica, dar care obtine numai 80 de puncte. Am incercat si solutia greedy si obtin numai 30 de puncte. Va rog sa va uitati peste sursa mea, sa vedeti ce greseti, pentru ca nu imi dau seama. Va multumesc.

Cod:

#include <cstdio>

#define LL long long
#define NMax 100005
#define Infinity 1000000000

using namespace std;

int N;
LL P[NMax], S, InitS, A;

void Solve ()
{
    P[0]=Infinity; // Prima zi dar nu poate fi maxim local, dar poate fi minim local
    P[N+1]=0; // Ultima zi nu poate fi minim local, dar poate fi maxim local
    for (int i=1; i<=N; ++i)
    {
        if (P[i-1]>P[i] and P[i]<P[i+1]) // Ziua i este minim local
        {
            A+=(S/P[i]); S%=P[i]; // Cumpar cat de multe actiuni pot, si imi ramane o parte din suma detinuta initial
        }
        if (P[i-1]<P[i] and P[i]>P[i+1]) // Ziua i este maxim local
        {
            S+=(A*P[i]); A=0; // Vand toate actiunile pe care le detin
        }
    }
}

void Read ()
{
    freopen ("bursa.in", "r", stdin);
    scanf ("%d %lld", &N, &InitS); S=InitS; // Pornesc cu suma initiala de bani
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lld", &P[i]); // Citesc preturile fiecare actiuni
    }
}

void Print ()
{
    freopen ("bursa.out", "w", stdout);
    printf ("%lld\n", S-InitS); // Afisez suma detinuta in ziua N-suma initiala (profitul)
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}

[•MciprianM]

Poate te ajuta daca te uiti la cazuri in care trebuie sa pui si egal in loc de mai mare sau mai mic strict.

[•flaviusc11]

Poate ma lamureste si pe mine cineva cu ce gresesc in algoritmul urmator. Merge pe 6 teste din cele 10. Ideea algoritmului este de a afla toate subsecventele crescatoare din sir. Daca gasesc o subsecventa crescatoare in sir, atunci cumpar cat pot de multe actiuni la inceputul subsirului crescator, si le vand pe toate (actiunile) la sfarsitul subsirului.

Cod:

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
    int i, x, n;
    long long s,s_init,s_rest=0;

    freopen( "bursa.in", "r", stdin );
    freopen( "bursa.out", "w", stdout );

    scanf("%d", &n );
    scanf("%lld",&s);
    s_init=s;
    vector<int>v;
    vector<int>::iterator it;
    for( i = 0; i < n; i++ )
        scanf("%d", &x), v.push_back( x );
    i=0;
    while(i<n)  
    {
        int p=i;                                //retin indicele subsecventei
            while( (i<n-1) && (v[i]<=v[i+1]))   //cat timp subsecventa este crescatoare inaintez in vector
            {
                i=i+1;
            }

        if(p!=i)                          //daca exista subsecventa crescatoare atunci cumpar cat pot de multe actiuni la inceputul subsecventei
          {                               // si le vand pe toate la sfarsitul subsecventei crescatoare
              int nr_act,val_act;
              s=s+s_rest;                  //suma totala
              nr_act=s/v[p];            //nr actiunilor cumparate
              s_rest=s-nr_act*v[p];  //determin restul din suma ramas dupa cumpararea actiunilor
              val_act=nr_act*v[i];   //determin valoarea actiunilor la sfarsitul subsecventei crescatoare adica dupa i-p zile
              s=val_act + s_rest;   //suma care o am la sfarsitul subsecventei crescatoare dupa vinderea actiunilor este val_act + restul ramas
              s_rest=0;               //restul l-am pus in suma mai inainte deci devine 0
          }
        i=i+1;                         //inaintez in vector
    }
    printf("%d\n", s-s_init);    //afisez profitul, adica suma modificata - suma initiala
    return 0;

}

[•gabitzish1]

Trebuie sa declari val_act ca variabila long long pe linia 30 si sa afisezi rezultatul cu %lld.

[•a_h1926]

Va multumesc mult, asta era problema, a iesit de 100 

[•flaviusc11]

Multumesc foarte mult. Asta era problema. Nu am fost atent si am luat 0 puncte in loc de 100. Altadata voi fi mai atent.

[•Tux2Nicolae]

EU CHEAR NU INTZELEG , imi pare ca ideia este corecta , cine ma poate ajuta va rog sami explicatzi ce nu e bine!

#include<stdio.h>
#define dim 100010
int n; long long s; int v[dim],c[dim];

Cod:

int main(){
    int i; long long max=0;
    freopen("bursa.in","r",stdin);
    freopen("bursa.out","w",stdout);
    scanf("%d %lld\n",&n,&s);
    for(i=1;i<=n;i++){ scanf("%d",&c[i]); v[i]=c[i]; }
    for(i=n;i>=1;i--){
        if (v[i]>=max) max=v[i];
        v[i]=max;
    }max=0;
    for(i=1;i<=n;i++){
        if(s/c[i]*v[i+1]-s+s%c[i]>max){
            max=s/c[i]*v[i+1]-s+s%c[i];
        }
    }
    printf("%lld\n",max);
}

[•PlayLikeNeverB4]

Poate ar fi mai util sa ne spui ideea ta. Oricum, vezi ca s-ar putea sa cumperi si sa vinzi de mai multe ori.

[•horatiu13]

Imi poate spune cineva daca au ceva special fata de celelalte testele 2 si 10?
La toate testele imi da OK, doar la cele doua imi da INCORECT si nu imi dau seama unde am gresit.

Multumesc.

[•PlayLikeNeverB4]

Citeste N+1 b-uri.

[•vladm98]

Ce inseamna Killed by signal?

[•Djok]

http://www.infoarena.ro/documentatie/evaluator
Citește aici despre mesajele care le poate da evaluatorul

[•Djok]

Nu sunt sigur ce e greșit și ce e coret, însă rezolvând problema, am hotărât să citesc și soluțiile oficiale, unde era folosit maxim/minim local.
Eu am rezolvato doar cu condiția a[ i ] > a[ i-1 ] adică în ziua i-1 cumpăram acțiuni, și în ziua i le vindeam, astfel am obținut 100 de puncte, îmi poate cineva zice dacă o astfel de abordare este corectă? sau testele sunt slabe?

[•RaduToporan]

Isi da cineva seama ce e gresit la:

#include <cstdio>

using namespace std;
int n,i,v[500005];
long long s,sinit,actiuni;

int main()
{
    freopen("bursa.in","r",stdin);
    freopen("bursa.out","w",stdout);
    scanf("%d%lld",&n,&s);
    for (i=1; i<=n; i++)
        scanf("%d",&v);
    sinit=s;
    v[0]=2000000000;
    v[n+1]=-2000000000;
    for (i=1; i<=n; i++)
        if (v[i-1]<v && v>v[i+1])
        {
            s=s+actiuni*v;
            actiuni=0;
        }
        else if (v[i-1]>v && v<v[i+1])
        {
            actiuni=actiuni+s/v;
            s=s%v;
        }
    printf("%lld\n",s-sinit);
    return 0;
}

[•sichetpaul]

Nu stiu de ce iau 0 puncte la pb. asta . I-am dat multe teste si cu toate merge. Va rog , daca se poate, sa ma ajutati.
Cod sursa:
#include <fstream>

using namespace std;
long long v[100002];
int main()
{ long long s,nr=0,n,i,Max=0;
    ifstream f("bursa.in");
    ofstream g("bursa.out");
    f>>n>>s;
    for (i=1;i<=n;++i) {
        f>>v;
        Max=max(Max,v);
    }
    v[0]=Max+1;
    for (i=1;i<=n;++i) {
        if (v>v[i-1] && v>v[i+1]) {
            s+=(v*nr);
            nr=0;
        }
       if (v<v[i+1] && v<v[i-1]) {
          nr=s/v;
          s-=(nr*v);
      }
    }
       g<<s<<'\n';
    return 0;
}

[•sichetpaul]

#include <fstream>

using namespace std;
long long v[100002];
int main()
{ long long s,nr=0,n,i,Max=0;
    ifstream f("bursa.in");
    ofstream g("bursa.out");
    f>>n>>s;
    for (i=1;i<=n;++i) {
        f>>v;
        Max=max(Max,v);
    }
    v[0]=Max+1;
    for (i=1;i<=n;++i) {
        if (v>v[i-1] && v>v[i+1]) {
            s+=(v*nr);
            nr=0;
        }
       if (v<v[i+1] && v<v[i-1]) {
          nr=s/v;
          s-=(nr*v);
      }
    }
       g<<s<<'\n';
    return 0;
}
Scuze.Am gresit putin la cod mai devreme