Cod sursa(job #2253670)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 4 octombrie 2018 11:31:00
Problema Minim2 Scor 40
Compilator cpp Status done
Runda shimulare_fara_shim Marime 1.09 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

const double eps = 1.e-6;

double a, b, rec;

struct Structulet {
  double val;
  bool usedA;
  
  bool operator <(const Structulet &other) const {
    double x, y;
    if (!this->usedA)
      x = this->val * a;
    else
      x = this->val * b;
    if (!other.usedA)
      y = other.val * a;
    else
      y = other.val * b;
    return this->val - x < other.val - y;
  }
};

int main() {
  freopen("minim2.in", "r", stdin);
  freopen("minim2.out", "w", stdout);
  
  int n;
  scanf("%d", &n);
  priority_queue<Structulet> pq;
  double S = 0;
  for (int i = 1; i <= n; i++) {
    double x;
    scanf("%lf", &x);
    pq.push({x, false});
    S += x;
  }
  scanf("%lf%lf%lf", &a, &b, &rec);
  int ans = 0;
  while (!(rec - S >= -eps)) {
    Structulet t = pq.top();
    pq.pop();
    if (!t.usedA) {
      S -= t.val;
      t.val *= a;
      S += t.val;
      t.usedA = true;
    } else {
      S -= t.val;
      t.val *= b;
      S += t.val;
    }
    pq.push(t);
    ans++;
  }
  printf("%d\n", ans);
  return 0;
}