Cod sursa(job #161628)

Utilizator astronomyAirinei Adrian astronomy Data 18 martie 2008 17:03:36
Problema Progresii Scor Ascuns
Compilator cpp Status done
Runda Marime 1.05 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define llong long long
#define MAXN 100100

int N, M, A[MAXN], R[MAXN]; llong K, X, T[MAXN];

void solve(void)
{
    int i, j, k, st, dr, r, m; llong sum = 0;

    for(i = N; i >= 1; i--)
    {
        T[i] = T[i+1] + max((llong)0, (llong)(X-A[i])/M);
        if(T[i] > K) printf("-1\n"), exit(0);
    }

    for(i = 1; i <= N; i++)
    {
        for(r = 1; r <= M; r++)
         if( sum + T[i+1] + max((llong)0, (llong)(X-A[i])/r) <= K )
            break ;
        sum = sum + (X-A[i]) / (R[i] = r);
    }
}

void read_data(void)
{
    int i;

    scanf("%d %d %lld %lld\n", &N, &M, &K, &X);
    for(i = 1; i <= N; i++) scanf("%d ", &A[i]);
}

void write_data(void)
{
    int i;
    for(i = 1; i <= N; i++) printf("%d\n", R[i]);
}

int main(void)
{
    freopen("progresii.in", "rt", stdin);
    freopen("progresii.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}