Cod sursa(job #165038)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 25 martie 2008 10:30:24
Problema Progresii Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#define FIN "progresii.in"
#define FOUT "progresii.out"
#define MAX_N 100000
using namespace std;
int speed[MAX_N+1],pz[MAX_N+1];
int n,m,k,l,total=0;

int decilitri(int leng,int viteza){
        return (leng/viteza)+1;
}


void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        scanf("%d%d%d%d",&n,&m,&k,&l);
        for (int i=1;i<=n;i++){
                scanf("%d",&pz[i]);
                speed[i]=m;
                total+=decilitri(l-pz[i],m);
        }
        fclose(stdin);
        return ;
}
void binary_search(int p,int u,int poz){
        if (p<=u) {
                int mij=(p+u)/2;
                if (total-decilitri(l-pz[poz],speed[poz])+
                        decilitri(l-pz[poz],mij)<=k){
                        total=total-decilitri(l-pz[poz],speed[poz])+
                        decilitri(l-pz[poz],mij);
                        speed[poz]=mij;
                                binary_search(p,mij-1,poz);} else
                          {binary_search(mij+1,u,poz);}
        }
}


void solve(void){
        for (int i=1;i<=n;i++){
                binary_search(1,m,i);
        }
        if (total<=k){
                for (int i=1;i<=n;i++){
                        printf("%d\n",speed[i]);
                }
        } else {printf("%d\n",-1);}
        fclose(stdout);
        return ;
}


int main(void){
        iofile();
        solve();
        return 0;
}