Ritrovo a Brambillia

Nell’isola di Brambillia, vi sono N città numerate da 1 a N e collegate attraverso una ferrovia circolare, le cui tratte sono anch’esse numerate da 1 a N e possono essere percorse in entrambe le direzioni:

• la tratta ferroviaria j collega direttamente la città j alla città j+1 (e, percorsa nella direzione opposta, collega j+1 a j) dove j=1, 2, …, N-1;
• la tratta N collega la città N alla città 1 (e, percorsa nella direzione opposta, collega 1 a N).

Il biglietto ferroviario per ciascuna tratta ha un costo prestabilito.

Date due qualunque città p e q, è possibile andare da p a q attraverso due percorsi ferroviari alternativi (ipotizzando che 1 ≤ p < q ≤ N, un percorso attraversa le tratte p, p+1, …, q-1 mentre l’altro attraversa, nella direzione opposta, le tratte p-1, p-2, …, 1, N, N-1, …, q; per andare da q a p, attraversiamo tali percorsi ma in direzione opposta).
Il biglietto ferroviario per ciascuno dei percorsi ha un costo pari alla somma dei costi delle singole tratte che lo compongono.

Gli abitanti di Brambillia intendono utilizzare la ferrovia circolare per ritrovarsi in occasione della sagra annuale dell’isola e devono scegliere la città presso cui organizzare tale sagra minimizzando il costo totale dei biglietti.
Per questo motivo hanno contato, per ogni città, quante persone vogliono parteciparvi, visto che è necessario acquistare un biglietto ferroviario per persona al costo descritto sopra (per gli abitanti della città che verrà scelta, il costo sarà nullo perché non dovranno prendere il treno).
In base a tale conteggio, individuate la città in cui organizzare la sagra, tenendo presente che le persone possono giungervi attraverso uno dei due percorsi a loro disposizione nella ferrovia circolare.

Dati di input

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

• La prima riga contiene un intero positivo che rappresenta il numero N delle città.
• Le successive N righe contengono ciascuna un intero positivo: quello nella j-esima di tali righe rappresenta il costo del biglietto ferroviario per la tratta j, dove 1 ≤ j ≤ N.
• Le ulteriori N righe contengono ciascuna un intero positivo o nullo: quello nella j-esima di tali righe è il numero delle persone della città j che intendono partecipare alla sagra, per 1 ≤ j ≤ N.

Dati di output

Il file output.txt è composto da una riga contenente un solo intero j che rappresenta la città j presso cui organizzare la sagra.
Come osservato in precedenza, tale città rende minimo il costo totale, ottenuto sommando i costi dei biglietti ferroviari di tutti i partecipanti.

Assunzioni

• 1 < N < 100
• I dati in input.txt garantiscono che la soluzione è unica (esiste una sola città in cui organizzare la sagra).

Esempio

/*
    www.valcon.it
	OII 2006 - Fase territoriale - Ritrovo a Brambillia
*/
#include 
#include 

using namespace std;

int  N;
long costo_citta[100];

void avanti  (int& c) { c++; if(c == N+1)  c=1; }
void indietro(int& c) {	c--; if(c == 0  )  c=N; }

int main() 
{	
	int costo_tratta[100];
	int passeggeri[100];
		
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	fin >> N;	                                                
	for(int i=1; i <= N; i++) fin >> costo_tratta[i];
	for(int i=1; i <= N; i++) fin >> passeggeri[i];
	
	int citta, 
	    costoD, costoS;	
	
	for(int dest=1;  dest  <= N; dest++)
	for(int parte=1; parte <= N; parte++)
	    if(parte != dest)
	    {
	    	costoD=0;
			citta=parte;
			while(citta != dest)
			{
				costoD += costo_tratta[citta];
				avanti(citta);
			}
			costoS=0;
			citta=parte;
			indietro(citta);
			while(true)
			{
				costoS += costo_tratta[citta];
				if(citta == dest) break;
				indietro(citta);
			}			
			costo_citta[dest] += min(costoD,costoS)*passeggeri[parte];
	    }
	    
	long min_costo=costo_citta[1];            // la città con costi minimi
	int  min_citta=1;
	for(int dest=2; dest <= N; dest++)
	    if(costo_citta[dest] < min_costo) 
	    {
	    	min_costo=costo_citta[dest];
	    	min_citta=dest;
		}
		
	fout << min_citta;	
	return 0;
}