Gita a Gardaland

Fase territoriale 2013

Nel 2012 le Olimpiadi Internazionali di Informatica (IOI) si sono svolte, per la prima volta, in Italia, a Sirmione.
Come da tradizione, nella giornata tra le due gare i concorrenti sono andati a divertirsi in un parco giochi, in questo caso, Gardaland.
La mattina di quel giorno decine di pullman hanno prelevato i quattro ragazzi che costituiscono la squadra olimpica di ciascuna nazione dal Garda Village, dove erano stati alloggiati, e li hanno portati a Gardaland.
Come sempre negli spostamenti, le varie nazioni erano state ripartite a blocco unico tra i pullman, ossia tutti gli atleti di una stessa nazione trovavano posto su uno stesso pullman.
Per esempio, sul pullman dell’Italia viaggiavano anche Giappone, Israele e Irlanda.
Al ritorno però, come sempre succede alle IOI, dopo una giornata in un parco giochi i ragazzi hanno fatto amicizia tra di loro, e al momento di tornare sui pullman sono saliti alla rinfusa.
Grazie al lavoro delle guide, per ogni pullman è stata stilata una lista contenente, per ogni nazione, il numero di ragazzi a bordo.
Il vostro compito è quello di aiutare Monica, responsabile dell’organizzazione, a capire se i pullman possono partire, ovvero se tutti i quattro ragazzi di ogni nazione che sono arrivati a Gardaland sono saliti sui pullman.
In caso contrario, dovete segnalare a Monica in quanti mancano all’appello, divisi per nazioni.

Dati di input

Il file input.txt è composto da 1+N+L righe.

• La prima riga contiene due interi positivi separati da uno spazio: il numero N delle nazioni e il numero L di righe contenenti informazioni su chi è attualmente già salito sui pullman.
  (Ciascuna nazione verrà qui rappresentata con un intero compreso tra 0 e N­-1).
• Ognuna delle successive N righe contiene un intero positivo: nella riga i+1 (con i ≥ 1) troviamo il numero totale di ragazzi della nazione i­-1.
• Ciascuna delle rimanenti L righe contiene due interi positivi: un intero compreso tra 0 e N-­1 che rappresenta la nazione, e un intero positivo che specifica quanti ragazzi di quella nazione sono su un certo pullman.
  Ovviamente una stessa nazione può comparire diverse volte nelle L righe, e più precisamente compare su tante righe quanti sono i pullman ospitanti atleti di quella nazione.

Dati di output

Il file output.txt è composto da una sola riga contenente l’intero 0 (zero) se non manca alcun ragazzo.

Altrimenti, il file contiene 1+C righe:

• La prima riga contiene un intero C, ovvero il numero di nazioni che hanno ragazzi ancora a Gardaland.
• Le restanti C righe contengono due interi: l’identificativo della nazione e il numero di ragazzi di quella nazione che non sono ancora saliti su alcun pullman.
• È necessario stampare le nazioni nell’ordine in cui sono state lette, ovvero in ordine crescente in base all’identificativo.

Assunzioni

• 2 ≤ N ≤ 100
• N ≤ L ≤ 1000
• Contrariamente alle olimpiadi di informatica reali, dove gareggiano (massimo) 4 ragazzi per ogni nazione, nei casi di input si assume che ogni nazione abbia al massimo 100 ragazzi, e almeno 1 ragazzo.
  Quindi, indicando con R_i il numero di ragazzi della i-­esima nazione, vale sempre 1 ≤ R_i ≤ 100.

Esempi di input/output

input.txt	output.txt
3 5 4 4 3 0 2 1 3 0 1 2 2 1 1	2 0 1 2 1
3 6 4 4 4 0 2 1 3 2 1 0 2 2 3 1 1	0

//------------------------------------------------------
//	www.valcon.it
//	OII 2013 - Fase territoriale - Gita a Gardaland
//------------------------------------------------------
#include 
#include  
using namespace std;
//------------------------------------------------------
#define NMAX 100
//------------------------------------------------------
int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
    //-------------------------------------------------	
	int N,            // num. nazioni
	    L;            // num. informazioni
	int quanti[NMAX]; // quanti per nazione
	int nazione,      // le coppie: nazione
	    numero;       //          : num. presenti
    //-------------------------------------------------
	fin >> N;		
	fin >> L;       
	for(int i=0; i < N; i++)
		fin >> quanti[i];		
	for(int i=0; i < L; i++)
	{
		fin >> nazione;
		fin >> numero;
		quanti[nazione] -= numero;
    }
    //-------------------------------------------------
    int conta=0;
	for(int i=0; i < N; i++)
    	if(quanti[i] > 0)
    	    conta++;
    fout << conta << endl;
    //-------------------------------------------------
    if(conta > 0)
        for(int i=0; i < N; i++)
    	    if(quanti[i] > 0)
    	        fout << i << ' ' << quanti[i] << endl;    	
	return 0;
}