[ALGORITMO] Problema di spostamento/scambi container

[fasterrr]

Non vi chiedo codice. Mi basta una pseudocodifica o una descrizione della soluzione.
L'ho risolto (bruteforce...) ma il tempo di esecuzione è altissimo

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 A A A A B B B B * *, dove le due posizioni vuote sono indicate da un asterisco *:

* Il primo spostamento della gru è (4,9) e porta alla configurazione:
A A A * * B B B A B
1 2 3 4 5 6 7 8 9 10
* Il secondo spostamento è (6, 4) e porta alla configurazione:
A A A B B * * B A B
1 2 3 4 5 6 7 8 9 10
* Il terzo spostamento è (2, 6) e porta alla configurazione:
A * * B B A A B A B
1 2 3 4 5 6 7 8 9 10
* Il quarto spostamento è (5,2) e porta alla configurazione:
A B A B * * A B A B
1 2 3 4 5 6 7 8 9 10
* Il quinto e ultimo spostamento è (9,5) e porta alla configurazione desiderata:
A B A B A B A B * *
1 2 3 4 5 6 7 8 9 10

Notare che per N=4 è possibile, con cinque 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 ≤ 3 N.

Esempi di input/output

File input.txt File output.txt

3



4 3
2 7
6 2
4 6
7 4


File input.txt File output.txt

4



5 4
4 9
6 4
2 6
5 2
9 5


File input.txt File output.txt

5



10 5
2 11
8 2
5 8
10 5
1 10
3 1
5 3
7 5
9 7
11 9

[alka]

Originariamente inviato da fasterrr
Non vi chiedo codice. Mi basta una pseudocodifica o una descrizione della soluzione.
L'ho risolto (bruteforce...) ma il tempo di esecuzione è altissimo

Posta il tuo codice.

[fasterrr]

eccolo
non vi fidavate?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<conio.h>
#include<time.h>
#define E 3000
int N;
int N3;

int inizio;

int sposta(int i1, int j1, char v[], int *spostamenti[2], int K)
{
    if(K+1>N3)
        return E;
    char *vet=(char *)malloc(N*2+2);
    int *spost[2];
    spost[0]=(int *)calloc(N*3, sizeof(int));
    spost[1]=(int *)calloc(N*3, sizeof(int));
    memcpy(vet, v, N*2+2);
    memcpy(spost[0], spostamenti[0], sizeof(int)*N*3);
    memcpy(spost[1], spostamenti[1], sizeof(int)*N*3);
    
    //sposta
    spost[0][K]=i1;
    spost[1][K]=j1;
    K++;
    vet[j1]=vet[i1];
    vet[j1+1]=vet[i1+1];
    vet[i1]='*';
    vet[i1+1]='*';
    //controlla ordine 
    int c=1;
    if(vet[N+N]!='*'||vet[N+N+1]!='*')
        c=0;
    if(c)
    for(int i=0;i<N+N;i+=2)
        if(vet[i]!='A')
        {
            c=0;
            break;
        }
    if(c)
    {
        FILE *fp;
        fp=fopen("output.txt", "w");
        fprintf(fp, "%d %d", N, K);
        for(int i=0;i<K;i++)
            fprintf(fp, "\n%d %d", spost[0][i]+1, spost[1][i]+1);
        fclose(fp);
        printf("%d", time(NULL)-inizio);
        getch();
        exit(1);
    }
    
    //sposta tt
    for(int i=0;i<=N+N;i++)
        if(vet[i]!='*'&&vet[i+1]!='*')
            if(K==0||i!=spost[1][K-1])
            sposta(i, i1, vet, spost, K);
            
    free(vet);
    free(spost[0]);
    free(spost[1]);
}


int main(void)
{
    inizio=time(NULL);
    char *vet;
    int *spost[2];
    int K=0;
    int i;
    FILE *fp;
    
    fp=fopen("input.txt", "r");
    fscanf(fp, "%d", &N);
    fclose(fp);
    
    N3=N*3;
    vet=(char *)malloc(N*2+2);
    spost[0]=(int *)calloc(N*3, sizeof(int));
    spost[1]=(int *)calloc(N*3, sizeof(int));
    for(i=0;i<N;i++)
        vet[i]='A';
    for(i=N;i<N+N;i++)
        vet[i]='B';
    vet[i++]='*';
    vet[i]='*';
    
    //for(i=0;i<N+N-1;i++)
        sposta(N-1, N+N, vet, spost, K);
    free(spost[0]);
    free(spost[1]);
    free(vet);
    return 0;
}

ma secondo me è da riscrivere da capo...

[alka]

Originariamente inviato da fasterrr
eccolo
non vi fidavate?

Serviva il codice per poterlo correggere o per suggerire le migliorie.
Non è un problema di fiducia.

Ciao!

[Hysoka]

ciao...
non ci crederai, ma mi sn applicato a questo problema ieri.
Selezioni regionali di olimpiadi di informatica, anno 2009, treni.
io sono arrivato a questa conclusione, ma potrebbe pure essere errata...
se n è pari, allora conviene partire dal mezzo (prima sequenza AB), altrimenti sembra che la scelta migliore sarebbe partire da un qualche AA opportuno che non sono ancora riuscito a trovare con certezza.
ora mi metto a lavoro, giusto per esercitarmi

[Hysoka]

ho fatto degli esempi,
adesso un algoritmo sia facile da estrapolare
non li ho verificati con gli input che forniscono loro

A[A A]B B B * * mi serve sequenza BA
A * * B B[B A]A trovata sequenza BA
A B A[B B]* * A mi serve sequenza BA
A B A * * B[B A] trovo sequenza BA
A B A B A B * *

A[A A]A A B B B B B * *
A * * A A B B B B[B A]A
A B A[A A]B B B B * * A
A B A * * B B B[B A]A A
A B A B A[B B]B * * A A
A B A B A * * B B[B A]A
A B A B A B A[B B]* * A
A B A B A B A * * B[B A]
A B A B A B A B A B * *


A A A A A[A B]B B B B B * * mi serve una sequenza B A
A A A A A * * B B B B[B A]B trovata sequenza B A
A A[A A]A B A B B B B * * B mi serve sequenza A B
A A * * A B A B B B B A[A B] trovata sequenza A B
A[A A]B A B A B B B B A * * mi serve sequenza B A
A * * B A B A B B B[B A]A A trovata sequenza B A
prima metà sistemata, ora passo alla seconda metà.
A B A B A B A[B B]B * * A A mi serve sequenza B A
A B A B A B A * * B B[B A]A trovata sequenza B A
A B A B A B A B A[B B]* * A mi serve B A
A B A B A B A B A * * B[B A] trovata B A
A B A B A B A B A B A B * *