Cod sursa(job #2076104)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 26 noiembrie 2017 10:47:32
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("buget.in");
ofstream out("buget.out");

int n, p[100003];
long long b;
long long suma (long long m) {
    long long s = 0;
    for(int i = 1; i <= n; i++) {
        if(p[i] < m) s += p[i];
        else s += m;
    }
    return s;
}

int cautaBinar(int s, int d) {
    int mij = (s+d)/2;
    if(suma(mij) >= b) return cautaBinar(s, mij-1);
    else {
        if(suma(mij+1) <= b) return cautaBinar(mij+1, d);
        else return mij;
    }
}
int main()
{
    in >> n >> b;
    for(int i = 1; i <= n; i++) {
        in >> p[i];
    }

    out << cautaBinar(0, 2000000000);
    return 0;
}