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:

Se invece usi Pascal, dovrai usare il seguente prototipo:

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


Se vuoi provare la funzione


Soluzione tradizionale

Notice: This work is licensed under a BY-NC-SA. Permalink: Secchi di noccioline

Lascia un commento