Cod sursa(job #1413030)

Utilizator delia_99Delia Draghici delia_99 Data 1 aprilie 2015 18:12:38
Problema Progresii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>

using namespace std;
long long n,m,k,l,Min[100010],Max[100010],sol[100010],pos,i,pi[100010],s=0;
bool ok;
int main()
{
    freopen("progresii.in","r",stdin);
    freopen("progresii.out","w",stdout);
    scanf("%lld %lld %lld %lld\n",&n,&m,&k,&l);
    for(i=1; i<=n; ++i)
    {
        scanf("%lld\n",&pi[i]);
        Min[i]=Min[i-1]+l-pi[i]+1;
        Max[i]=(int)((l-pi[i]+1)/m);
        if(l-pi[i]+1-(Max[i]*m)>0)
            ++Max[i];
        s+=Max[i];
    }
    if(s>k)
    {
        printf("-1\n");
        return 0;
    }
    ok=false;
    for(i=n; i>=2 && !ok; --i)
    {
        if(k==Min[i])
        {
            ok=true;
            pos=i;
        }
        else
        {
            if(k-Min[i-1]>Min[i])
            {
                sol[i]=(int)(l-pi[i]+1)/Min[i];
                if(sol[i]*Min[i]<l-pi[i]+1)
                  ++sol[i];
                k-=Min[i];
            }
            else
            {
                sol[i]=(int)(l-pi[i]+1)/(k-Min[i-1]);
                if(sol[i]*(Min[i]-Min[i-1])<l-pi[i]+1)
                  ++sol[i];
                k-=(k-Min[i-1]);
            }
        }

    }
    if(ok)
    {
        for(i=1; i<=pos; ++i)
            printf("1\n");
        for(i=pos+1; i<=n; ++i)
            printf("%lld\n",sol[i]);
    }
    else
    {
        sol[1]=(l-pi[1]+1)/k;
        for(i=1; i<=n; ++i)
            printf("%lld\n",sol[i]);
    }

    return 0;
}