Cod sursa(job #490336)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 6 octombrie 2010 08:02:05
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;

const cha08 Input[] = "minim2.in";
const cha08 Output[] = "minim2.out";

const int32 Dim = 100001;

int01 f[Dim];
int32 N, XXX;
rea64 A, B, R, S;
rea64 l[Dim];

struct cmp {

    rea64 X, Y;

    int01 operator()( const int32 &x, const int32 &y ) {

        X = f[x] == false ? A : B;
        Y = f[y] == false ? A : B;

        return l[x] - l[x] * X < l[y] - l[y] * Y;
    }
};
priority_queue <int32, vector <int32>, cmp> h;

int32 main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int32 i, x;

    fin >> N;
    for( i = 0; i < N; ++i ) {

        fin >> l[i];
        h.push( i );
        S += l[i];
    }
    fin >> A >> B >> R;

    while( S >= R ) {

        x = h.top();
        h.pop();
        S -= l[x];

        if( f[x] == false ) {

            l[x] *= A;
            f[x] = true;
        }
        else
            l[x] *= B;

        h.push( x );
        S += l[x];
        ++XXX;
    }

    fout << XXX;

    fin.close();
    fout.close();

    return 0;
}