Pinocchio

Pinocchio vi chiede di indovinare un numero N compreso tra 1 e 30000.
Per aiutarvi, vi fornisce una sequenza di M altri numeri interi, dicendovi se ciascuno di essi è più grande o più piccolo di N.
Data però la sua innata predisposizione alla menzogna, Pinocchio per uno solo di questi numeri vi dà una informazione errata.
Ad esempio, potrebbe dirvi che N è minore di 300, mentre ciò non è vero.
Purtroppo, però, non sapete quale delle M informazioni è falsa.

Dovete scrivere un programma che elenchi tutti i numeri che Pinocchio potrebbe aver pensato.

Dati in input

Il file input.txt contiene sulla prima riga un numero intero positivo M.
Ciascuna delle successive M righe contiene un numero intero X, preceduto dal simbolo < se Pinocchio vuole suggerirvi che N è minore di X, o dal simbolo >, se invece Pinocchio afferma che N è maggiore di X.
X è un intero compreso tra 0 e 30001.

Dati in output

Il programma, dopo aver letto il file di input, deve scrivere sul file output.txt un elenco dei numeri che Pinocchio potrebbe aver pensato.
Più precisamente, il file output.txt deve essere costituito da una serie di righe, ciascuna delle quali contiene un unico numero intero in formato testo.
I numeri devono apparire in ordine crescente e senza ripetizioni.
Il file output.txt deve contenere tutti i numeri interi compresi tra 1 e 30000 compatibili con le informazioni fornite da Pinocchio (cioè, che soddisfino esattamente M-1 delle M diseguaglianze fornite).

Assunzioni

  1. La prima riga del file input.txt contiene un intero M compreso tra 1 e 20000, in formato testo;
  2. le successive M righe del file contengono il carattere < oppure il carattere >, seguito da uno spazio e da un numero intero (in formato testo) compreso fra 0 e 30001.

Esempi di input/output

input.txt output.txt
7
> 4
> 7
> 9
< 10
> 3
< 15
< 13
8
9
10
11
12
10
> 4
> 7
> 9
< 30
> 3
< 50
< 37
< 27
> 3
> 4
8
9
27
28
29

/*
    www.valcon.it    
    OOI 2001 - Fase nazionale - PINOCCHIO
*/  
#include
#include

#define NMIN 1				    // numeri
#define NMAX 30000              

using namespace std;

int numeri[NMAX+1];				// n. suggerimenti per ogni numero

int main()
{   
   int  M;						// n. suggerimenti
   char min_mag;				// input suggerimenti
   int  num;
   
   ifstream fin ( "input.txt");   
   ofstream fout("output.txt");
      
   fin >> M;   
   for(int i=1; i <= M; i++)
   {
       fin >> min_mag >> num;       
       
            if(min_mag == '<')	for(int j=NMIN ; j <  num ; j++) numeri[j]++;
       else if(min_mag == '>')	for(int j=num+1; j <= NMAX; j++) numeri[j]++;               
   }   
       
   for(num=NMIN; num <= NMAX; num++)
       if(numeri[num] == M-1)
           fout << num << endl;
           
   return 0;
}