Per un pugno di baht

L’incredibile Hulk si trova in Tailandia e purtroppo ha un carattere irascibile: ha rotto diverse macchine automatiche per distribuire le merendine perché non erano in grado di fornirgli il resto.
Per prevenire l’ira di Hulk in tali situazioni, la ditta costruttrice ha deciso di predisporre un sistema centrale che sia in grado di calcolare, per ciascuna di tali macchine, il minimo resto che la macchina stessa non è in grado di fornire.
Le monete tailandesi (i baht) che sono presenti nelle macchine possono essere di qualsiasi taglia (1 baht, 2 baht, 3 baht, ecc.) e quantità.

Possono essere combinate in qualsiasi modo: ad esempio, il resto di 5 baht non può essere dato se la macchina contiene una moneta da 1 baht e 2 monete da 3 baht (in questo caso il più piccolo resto che non può essere dato è 2).

Con 6 monete da 1 baht e 2 monete da 2 baht, è invece possibile fornire il resto di 5 baht in vari modi (in questo caso il resto più piccolo resto che non può essere dato è 11).

Il tuo compito è di aiutare la ditta a calcolare, per un certo numero di macchine, qual è il minimo resto che ciascuna macchina non è in grado di fornire.

Dati di input

Il file input.txt è composto da 2P+1 righe, dove P è il numero di macchine su cui valutare il resto.
Per ogni macchina, la ditta presenta la corrispondente sequenza di monete e chiede il minimo resto che la macchina non è in grado di fornire.
Sulla prima riga si trova P, il numero di macchine.
Le rimanenti righe sono così composte.
Per 1 ≤ i ≤ P, le righe 2i e 2i+1 contengono le informazioni per la i-esima macchina distributrice: la riga 2i contiene N_i, il numero di monete presenti nella macchina; la riga successiva (2i+1), contiene la sequenza di valori M₁, M₂, …, M_Ni delle monete presenti nella macchina, separati l’un l’altro da uno spazio.
I valori delle monete sono interi positivi.

Per esempio, se la seconda riga del file contiene il numero 7 e la terza riga i numeri 10 2 14 1 13 2 3, questo significa che nella prima macchina sono presenti 7 monete.
Siccome le monete vanno inserite una alla volta, risulta una moneta da 10 bath, poi una da 2 bath, poi una da 14 baht, una da 1 bath, una da 13 bath, ancora una da 2 bath e, infine, una da 3 bath.
In tal caso, il minimo resto che la macchina non riesce a restituire è di 9 baht.

Dati di output

Il file output.txt è composto da P righe.
Sulla i-esima riga (con 1 ≤ i ≤ P) si deve trovare il minimo resto che la i-esima macchina non può fornire.

Assunzioni

• 1 ≤ P ≤ 1000
• 1 ≤ N_i ≤ 10000 per ogni i
• 1 ≤ M_j < 2²⁰ per ogni j
• Per ciascuna macchina, la somma delle monete nella rispettiva sequenza è sempre inferiore a 2³¹

Esempi di input/output

/*
	www.valcon.it
	OII 2011 - Fase nazionale - Per un pugno di bath
*/
#include
#include
#include

using namespace std;

#define NMAX 10000

int       N;
long long resto;
long long minimo;
long long monete[NMAX];

void controlla()
{	
    minimo=0;
    for(int m=0; m < N; m++)
    	if(monete[m]> minimo+1)    		
    		break;
		else
		    minimo += monete[m];
	resto=minimo+1;
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	int P;
	fin >> P;
	for(int i=1; i <= P; i++)		// per ogni macchina
	{
		fin >> N;					// n. monete 
		for(int j=0; j < N; j++)
			fin >> monete[j];       // le n. monete
	    sort(monete, monete+N);			    
		controlla();
		fout << resto << endl;
	}	
	return 0;
}