Nanga Parbat

di

Fase Territoriale 2011

Durante la lunga scalata delle cime attorno al Nanga Parbat, Reinhold Messner riesce a trasmettere al campo base, a intervalli regolari, solo il dislivello percorso rispetto all’ultima trasmissione.
Se invia un numero positivo P, allora è salito di P metri rispetto alla precedente trasmissione; se invia un numero negativo P, allora è sceso di P metri rispetto alla precedente trasmissione; se infine invia P=0, non ha cambiato altitudine.
Messner parte dal campo base a 5000 metri.
I suoi collaboratori al campo base ricevono tali rilevamenti: aiutali a identificare l’altitudine che risulta più frequentemente rilevata in questo modo.

Dati di input

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

  • La prima riga contiene l’intero positivo N, il numero dei rilevamenti trasmessi da Messner.
  • Ciascuna delle successive N righe contiene un intero che rappresenta il dislivello percorso rispetto alla precedente trasmissione.

Dati di output

Il file output.txt è composto da una sola riga contenente l’altitudine che risulta più frequentemente rilevata in questo modo dal campo base.

Assunzioni

  • 2 ≤ N ≤ 1000.
  • -100 ≤ P ≤ 100.

Esempi di input/output

input.txt output.txt
8
3
-1
6
-7
1
4
0
-4		 5002

Note

  1. L’altitudine iniziale viene rilevata a fini della risposta.
  2. Viene garantito nei dati di input che l’altitudine più frequentemente rilevata è unica.

Utilizzo un array ordinato rispetto alle altitudini

/*
	www.valcon.it
	OII 2011 - Fase territoriale - Nanga Parbat
*/
#include 
#include 
#define START 5000
#define NMAX  1000

using namespace std;

struct INFO { long altitudine; long frequenza; };

INFO STAT[NMAX];
long NUM=0;

void aggiungi(long x)
{
	long start=0,
	     stop =NUM-1;
	while(start <= stop)
	{
		long mezzo=(start+stop)/2;
		
		     if(x < STAT[mezzo].altitudine)  stop =mezzo-1;
		else if(x > STAT[mezzo].altitudine)  start=mezzo+1;
		else                               { STAT[mezzo].frequenza++; break; }
    }
    if(start > stop)
    {
    	for(long i=NUM; i > start; i--)
    		STAT[i]=STAT[i-1];
    	STAT[start].altitudine=x;
    	STAT[start].frequenza =1;
    	NUM++;
	}	
}

int main ()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
		
	long altitudine=START;			aggiungi(altitudine);
	long N,
	     dislivello;
	fin >> N;
	for(long i=0; i < N; i++)
	{
		fin >> dislivello;		
		altitudine += dislivello;	aggiungi(altitudine);
	}
	
	long max_alt =STAT[0].altitudine;
	long max_freq=STAT[0].frequenza;
	for(long i=0; i < NUM; i++)
	{
    	if(STAT[i].frequenza > max_freq)
    	{
			max_alt =STAT[i].altitudine;
		    max_freq=STAT[i].frequenza;
	    }
  	}

	fout << max_alt;
    return 0;
}

Utilizzo map

/*
	www.valcon.it
	OII 2011 - Fase territoriale - Nanga Parbat
*/
#include 
#include 
#include 
#define START 5000

using namespace std;

map           STAT;
map::iterator ITER;

void aggiungi(long x)
{
	long r=STAT[x];
	if(r == 0)	STAT[x]=1;
	else        STAT[x]=r+1;
}

int main ()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
		
	long altitudine=START;			aggiungi(altitudine);	
	long N,
	     dislivello;
	fin >> N;
	for(long i=0; i < N; i++)
	{
		fin >> dislivello;		
		altitudine += dislivello;	aggiungi(altitudine);
	}
	
	long max_alt =START;
	long max_freq=1;	
	for(ITER=STAT.begin(); ITER != STAT.end(); ITER++)
	{
    	if(ITER->second > max_freq)
    	{
			max_alt =ITER->first;
		    max_freq=ITER->second;
	    }
  	}

	fout << max_alt;
    return 0;
}