Cod sursa(job #465886)

Utilizator marius21Marius Petcu marius21 Data 25 iunie 2010 13:48:17
Problema Minim2 Scor 0
Compilator c Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.86 kb
#include <stdio.h>
#include <stdlib.h>

float a[100000];
int hp[100000];
char ad[100000];
int n;
float crc=0,rec;
int nr=0;
float na,nb;

inline void lwr(int i, float f)
{
    float tmp=a[i];
    a[i]*=f;
    crc-=tmp-a[i];
    nr++;
}

inline int right()
{
    return (crc<=rec);
}

inline float cst(int i)
{
    return (a[hp[i]]-(ad[hp[i]]?(a[hp[i]]*na):(a[hp[i]]*nb)));
}

void heap_up(int i)
{
    int pos=i,npos;
    while ((pos)&&(cst(pos)>cst(npos=((pos-1)>>1))))
    {
        hp[pos]=hp[pos]^hp[npos];
        hp[npos]=hp[pos]^hp[npos];
        hp[pos]=hp[pos]^hp[npos];
        pos=npos;
    }
}

void heap_down(int i)
{
    int pos=i;
    while (1)
    {
        int np1,np2;
        np2=(pos+1)<<1;
        np1=np2-1;
        if (np1>=n)
            break;
        if (np2!=n)
        {
            if (cst(np2)>cst(np1))
                np1=np2;
        }
        if (cst(np1)<cst(pos))
            break;
        hp[pos]=hp[pos]^hp[np1];
        hp[np1]=hp[pos]^hp[np1];
        hp[pos]=hp[pos]^hp[np1];
        pos=np1;
    }
}

int main()
{
    FILE *fin,*fout;
    fin=fopen("minim2.in","r");
    fout=fopen("minim2.out","w");

    fscanf(fin,"%d",&n);
    int i;

    for (i=0; i<n; i++)
    {
        fscanf(fin,"%f",&a[i]);
        crc+=a[i];
        ad[i]=1;
    }

    fscanf(fin,"%f %f %f",&na,&nb,&rec);

    for (i=0; i<n; i++)
    {
        hp[i]=i;
        heap_up(i);
    }

    while (!right())
    {
        if (ad[hp[0]])
        {
            ad[hp[0]]=0;
            lwr(hp[0],na);
        }
        float max=0;
        if ((n>=2)&&(cst(1)>max))
            max=cst(1);
        if ((n>=3)&&(cst(2)>max))
            max=cst(2);
        while ((!right())&&(cst(0)>=max))
        {
            lwr(hp[0],nb);
        }
        if (right())
            break;
        heap_down(0);
    }

    fprintf(fout,"%d\n",nr);

    fclose(fin);
    fclose(fout);
    return 0;
}