Essenza per profumi

Fase Territoriale 2009

L’essenza di un fiore raro è molto ricercata tra i profumieri.
Il prezzo di mercato viene fissato giornalmente dal CGE, il Consorzio dei Grossisti di Essenze.
Inoltre, essendo di natura organica, l’essenza acquistata da un profumiere deperisce dopo un certo periodo e quindi può essere rivenduta soltanto entro K giorni dall’acquisto (data di scadenza).

Un profumiere è venuto a conoscenza del prezzo di mercato dell’essenza che il CGE prevede per i prossimi N giorni (N ≥ K), per semplicità numerati da 1 a N.
Ritenendo molto affidabili le previsioni del CGE, il profumiere intende comprare una certa quantità di essenza il giorno i per rivenderla il giorno j, tenendo presente però che non può andare oltre la data di scadenza (quindi deve essere i ≤ j ≤ i+K).
Il profumiere intende fare un solo acquisto e una sola vendita successiva all’acquisto.

Aiutate il profumiere a calcolare il massimo guadagno che può ottenere, calcolato come la differenza tra il prezzo dell’essenza al giorno j e quello al giorno i.
Notate che è permesso scegliere j = i: in questo modo, anche se il prezzo di mercato dell’essenza fosse in discesa per tutto il periodo considerato, sarebbe possibile evitare perdite.

Dati di input

Il file input.txt è composto da due righe.

• La prima riga contiene due interi positivi separati da uno spazio, rispettivamente il numero K di giorni per la data di scadenza e il numero N di prossimi giorni.
• La seconda riga contiene N interi positivi separati da uno spazio, i quali rappresentano il prezzo di vendita dell’essenza nei prossimi N giorni.

Dati di output

Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo guadagno del profumiere, con le regole descritte sopra.

Assunzioni

• 1 ≤ K ≤ N
• 1 ≤ N ≤ 1000

Esempio

input.txt	output.txt
2 6 3 6 2 6 9 6	7

/*
    www.valcon.it
	OII 2009 - Fase territoriale - Essenza per profumi
*/

#include

int prezzi[1001];

int main()
{
	int K, N;
    int i, j, 
	    max_guadagno, guadagno;
    
	FILE* fin =fopen( "input.txt","r");
	FILE* fout=fopen("output.txt","w");
	
	fscanf(fin, "%d %d", &K, &N);
	for(i=1; i <= N; i++)
	    fscanf(fin, "%d", &(prezzi[i]));
	
	max_guadagno=0;
	for(i=1; i <= N; i++)
	for(j=i; j <= i+K && j <= N; j++)
	{
	   	guadagno=prezzi[j]-prezzi[i];
	    if(guadagno > max_guadagno)
	        max_guadagno=guadagno;
    }
    
	fprintf(fout, "%d", max_guadagno);
	return 0;
}