Treno di container

Fase Territoriale 2009

Al porto sono arrivati N container della sostanza chimica di tipo A e N container della sostanza chimica di tipo B.
I container sono stati caricati, uno dietro l’altro, su di un treno che ne può contenere 2N+2.
Le posizioni dei container sul treno sono numerate da 1 a 2N+2.
Il carico è stato fatto in modo che gli N container di tipo A occupino le posizioni da 1 a N, mentre quelli di tipo B da N+1 a 2N; le rimanenti due posizioni 2N+1 e 2N+2 sono vuote.
Per motivi connessi all’utilizzo delle sostanze chimiche nella fabbrica alla quale sono destinate, i container vanno distribuiti sul treno a coppie: ciascun container per la sostanza di tipo A deve essere seguito da uno di tipo B.
Occorre quindi che nelle posizioni dispari (1, 3, 5, …, 2N-1) vadano sistemati esclusivamente i container di tipo A mentre in quelle pari (2, 4, 6, …, 2N) quelli di tipo B, lasciando libere le ultime due posizioni 2N+1 e 2N+2.
A tal fine, viene impiegata una grossa gru, che preleva due container alla volta, in posizioni consecutive i, i+1, e li sposta nelle uniche due posizioni consecutive j, j+1 libere nel treno (inizialmente, j=2N+1).
Tale operazione è univocamente identificata dalla coppia (i, j), dove entrambe le posizioni i e i+1 devono essere occupate da container mentre j e j+1 devono essere entrambe vuote.

Per esempio, con N=4, abbiamo inizialmente la configurazione AAAABBBB**, dove le due posizioni vuote sono indicate da un asterisco *:

	1	2	3	4	5	6	7	8	9	10
	A	A	A	A	B	B	B	B	*	*
4 -> 9	A	A	A	*	*	B	B	B	A	B
6 -> 4	A	A	A	B	B	*	*	B	A	B
2 -> 6	A	*	*	B	B	A	A	B	A	B
5 -> 2	A	B	A	B	*	*	A	B	A	B
9 -> 5	A	B	A	B	A	B	A	B	*	*

I 5 spostamenti, indicati nella 1° colonna, portano alla configurazione desiderata.

Notare che per N=4 è possibile, con 5 spostamenti, sistemare i 2N container nell’ordine giusto.

Scrivere quindi un programma che determini la successione degli spostamenti eseguiti dalla gru per ottenere un analogo risultato nel caso in cui 3 ≤ N ≤ 1000.
Si richiede inoltre che il numero K di tali spostamenti non superi il valore 3N.

Dati di input

Il file input.txt è composto da una sola riga, contenente l’intero N che rappresenta il numero di container per ciascuna delle due sostanze.

Dati di output

Il file output.txt è composto da K+1 righe.

• La prima riga contiene due interi positivi separati da uno spazio, rispettivamente il numero K di spostamenti operati dalla gru e il numero N di container per ciascuna delle due sostanze.
• Le righe successive contengono la sequenza di K spostamenti del tipo (i, j), tali che partendo dalla sequenza AAA…ABBB…B**, si arrivi alla sequenza ABABAB…AB** con le regole descritte sopra.
  Ciascuna delle righe contiene una coppia di interi positivi i e j separati da uno spazio a rappresentare lo spostamento (i, j).

Assunzioni

• 3 ≤ N ≤ 1000
• 1 ≤ i, j ≤ 2N+1
• K ≤ 3N.

Esempi di input/output

input.txt	output.txt
3	4 3 2 7 6 2 4 6 7 4
4	5 4 4 9 6 4 2 6 5 2 9 5
5	6 5 5 11 2 5 9 2 6 9 3 6 11 3

Il correttore online (correttore.olimpiadi-informatica.it) si aspetta una soluzione con K=2(N-2)+1 mosse, altrimenti dà errore.

Questa soluzione, con K=2N-1 mosse, supera il test del portale di allenamento.
Con 10 container per ogni sostanza esegue i 19 passi nella figura a destra.

/*
	www.valcon.it
	OII 2009 - Treno di container
*/
#include

FILE* fin;
FILE* fout;
int   N;

void sposta(int a, int b)
{		
	fprintf(fout, "%d %d\n", a, b);
}

void risolvi(int n)
{
	for(int k=n; k > 3; k--)
	{
		sposta(k,2*k+1);
		sposta(2*k-1,k);		
	}
	sposta(2,7);
	sposta(6,2);
	sposta(4,6);
	sposta(7,4);
	if(n > 3)
	   sposta(2*n+1,7);
}

int main()
{
	fin =fopen( "input.txt","r");
	fout=fopen("output.txt","w");
	
	fscanf(fin,"%d", &N);	
	if(N == 3)	fprintf(fout, "%d %d\n", 4, N);
	else        fprintf(fout, "%d %d\n", 2*N-1, N);
	risolvi(N);		
	return 0;
}