Cod sursa(job #984496)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 14 august 2013 17:11:35
Problema Progresii Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>

#define maxdim 100005

FILE*f=fopen("progresii.in","r");
FILE*g=fopen("progresii.out","w");

int n,m;
int p[maxdim];
long long k,l;
long long needed[maxdim];

int main () {
	
	fscanf(f,"%d %d %lld %lld",&n,&m,&k,&l);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&p[i]);
	}
	
	for ( int i = n ; i >= 1 ; --i ){
		needed[i] = needed[i+1] + (l-p[i])/m + 1;
	}
	
	if ( needed[1] > k ){
		fprintf(g,"-1\n");
		fclose(f); fclose(g);
		return 0;
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		
		long long sol = 0;
		if ( k-needed[i+1]-1 == 0 ){
			sol = l-p[i]+1;
		}
		else{
			
			sol = (l-p[i])/(k-needed[i+1]-1);
			
			for ( long long x = sol-20 ; x <= sol+20 ; ++x ){
				if ( x < 1 || x > m )	continue ;
				if ( k - ((l-p[i])/x + 1) >= needed[i+1] ){
					sol = x;
					break ;
				}
			}
		}
		
		fprintf(g,"%d\n",sol);
		
		k -= ((l-p[i])/sol + 1);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}