Cod sursa(job #2095991)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 28 decembrie 2017 14:11:11
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
using namespace std;
#define DIM 10000
char buff[DIM];
int poz=0;
void citeste(double &numar)
{
     numar = 0;
     char semn='+';
     //caut inceputul numarului
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     //citesc partea de dinainte de virgula
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     //daca are virgula citesc si partea de dupa
     if (buff[poz] == '.')
     {
          double tmp,cnt;
          tmp = 0;
          cnt = 1;
          ++poz;
          while ('0'<=buff[poz] && buff[poz]<='9')
          {
               cnt = cnt/10;
               tmp = tmp + cnt*(double(buff[poz]-'0'));
               if (++poz == DIM)
                    fread(buff,1,DIM,stdin),poz=0;
          }
          numar += tmp;
     }
     //daca are semnul minus il fac negativ
     if (semn == '-')
          numar = - numar;
}
const int nmax=1e5+3;
double v[nmax],p,r,a,b,sum,act,n;
int sol;
priority_queue < pair <double,double> > q;
int main()
{
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    citeste(n);
    for(int i=1;i<=n;++i) citeste(v[i]);
    citeste(a);
    citeste(b);
    citeste(sum);
    for(int i=1;i<=n;++i)
    {
        act+=v[i];
        p=v[i]-v[i]*a;
        q.push({p,v[i]});
    }
    while(act>sum)
    {
        ++sol;
        p=q.top().first;
        r=q.top().second;
        q.pop();
        act-=p;
        r-=p;
        p=r-r*b;
        q.push({p,r});
    }
    printf("%d",sol);
    return 0;
}