Secchi di noccioline

Portale di allenamento delle Olimpiadi Italiane di Informatica

La Pinats S.p.A. è uno dei principali esportatori galattici di deliziose noccioline.
Il processo di produzione prevede che le noccioline vengano prelevate dal grande deposito, e poi inscatolate nei secchi di noccioline destinate alla vendita.
Ogni confezione prodotta contiene esattamente K preziose noccioline, tostate e salate con rarissimo sale dell’Himalaya.
Purtroppo la macchina che versa le noccioline nelle confezioni si è guastata, e N secchi sono stati riempiti con un numero casuale di noccioline.
Per risolvere il problema è stata assunta una squadra di 150 ingegneri, che hanno prima di tutto contato, per ogni secchio, il numero di noccioline contenute.
È stata installata poi una macchina robotizzata in grado di prelevare una singola nocciolina da un secchio e lasciarla delicatamente cadere in un altro secchio.
A richiesta la macchina può anche prelevare o scaricare una nocciolina nel grande deposito.
Tuttavia la macchina richiede di essere programmata da un tecnico, e si pone ora il problema di come risolvere il problema nel minor tempo possibile.
Dato il numero di secchi e le quantità di noccioline in essi contenute, scrivi un programma che determini il numero minimo di operazioni che il robot deve compiere affinché alla fine tutti i secchi contengano K noccioline ciascuno.

Un’indagine di mercato ha determinato che vendere le noccioline a secchi non solo beneficia i volumi delle vendite, ma riduce anche sensibilmente il numero di suicidi collegati al tragico e improvviso esaurimento di noccioline, spesso dovuto alle piccole dimensioni della confezione.

Implementazione

Dovrai sottoporre esattamente un file con estensione .c, .cpp o .pas.
Tra gli allegati a questo task troverai un template (noccioline.c, noccioline.cpp, noccioline.pas) con un esempio di implementazione.

Se usi C/C++, dovrai implementare la funzione ContaOperazioni utilizzando il seguente prototipo:

int ContaOperazioni(int N, int K, int* secchi);

Se invece usi Pascal, dovrai usare il seguente prototipo:

function ContaOperazioni(N: longint; K: longint; var secchi: array of longint): longint;

N è il numero di secchi, mentre secchi[i] contiene, per ogni 0 ≤ i < N, il numero di noccioline contenute nel secchio i.
La funzione deve restituire il numero minimo di operazioni che la macchina dovrà effettuare affinché alla fine del processo tutti i secchi contengano K noccioline ciascuno.

Assunzioni

• 1 ≤ N ≤ 10000
• 1 ≤ K ≤ 100000
• Ogni secchio contiene inizialmente un numero di noccioline non superiore a 100000
• Il grande deposito è in grado di fornire e ricevere un numero infinito di noccioline.

Assegnazione del punteggio
Grader di prova

…

Esempi di input/output

input.txt	output.txt
5 4 1 0 7 9 5	9
3 3 1 2 1	5

int ContaOperazioni(int N, int K, int* secchi)
{
	int mancano =0;
	int eccedono=0;
	int Ni;
	
	for(int i=0; i < N; i++)
	{					
		Ni=secchi[i];
		
		     if(Ni < K) mancano  += (K-Ni);
		else if(Ni > K)	eccedono += (Ni-K);
	}
		
	if(mancano <= eccedono) return eccedono;
	else                    return mancano;
}

Se vuoi provare la funzione

/*
 www.valcon.it
 Portale di allenamento delle Olimpiadi Italiane di Informatica
 Secchi di noccioline
*/

#include
#include
#define NMAX 10000

using namespace std;

int ContaOperazioni(int N, int K, int* secchi)
{
	int mancano =0;
	int eccedono=0;
	int Ni;
	
	for(int i=0; i < N; i++)
	{					
		Ni=secchi[i];
		
		     if(Ni < K) mancano  += (K-Ni);
		else if(Ni > K)	eccedono += (Ni-K);
	}
		
	if(mancano <= eccedono) return eccedono;
	else 					return mancano;
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
		
	int N,				// n. di secchi
	    K,				// n. finale di noccioline per ogni secchio		    
	    secchi[NMAX];	// n. di noccioline nei secchi
	
	fin >> N >> K;
	for(int i=0; i < N; i++)
		fin >> secchi[i];
			
	fout << ContaOperazioni(N, K, secchi);
	return 0;
}

Soluzione tradizionale

/*
 www.valcon.it
 Portale di allenamento delle Olimpiadi Italiane di Informatica
 Secchi di noccioline
*/

#include
#include
using namespace std;

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
		
	long N,				// n. di secchi
	     K,				// n. finale di noccioline per ogni secchio	
	     Ni,			// n. di noccioline ne secchio i-esimo
	     mancano=0,
	     eccedono=0,
	     risposta=0;
	
	fin >> N >> K;
	for(int i=1; i <= N; i++)
	{
		fin >> Ni;	
			
		     if(Ni < K) mancano  += (K-Ni);
		else if(Ni > K)	eccedono += (Ni-K);
	}
		
	if(mancano <= eccedono) risposta=eccedono;
	else 					risposta=mancano;
	
	fout << risposta;
	return 0;
}