Stringhe strane

di

Fase Territoriale 2002

Dato un insieme di stringhe di lunghezza 6 formate dai caratteri ‘A’, ‘B’, ‘C’ o ‘D’ bisogna distinguere le stringhe buone da quelle cattive.
Una stringa è buona se soddisfa tutti i seguenti requisiti:

  • Non contiene una sequenza di 3 o più caratteri che sono uguali (ad esempio le stringhe contenenti AAA o BBBB sono cattive)
  • Non contiene una sequenza di 3 o più caratteri consecutivi che sono in ordine crescente (ad esempio le stringhe che contengono ABC o ACD sono cattive)
  • Se una stringa non rispetta anche uno solo dei due requisiti precedenti è cattiva.

File di Input

Il file di input di nome input.txt ha il seguente formato:

  • la prima riga contiene un numero intero N, che rappresenta il numero di stringhe;
  • le successive N righe contengono ciascuna una stringa di lunghezza 6 formata dai caratteri ‘A’, ‘B’, ‘C’ o ‘D’.

Il primo carattere della riga contiene il primo carattere della stringa e i caratteri della stringa sono consecutivi (cioè non sono separati da spazi).

File di Output

Il file di output di nome output.txt è costituito da N righe, una riga per ciascuna stringa data in input; l’ultima riga termina con un a-capo.
Ogni riga è costituita esattamente da 1 carattere.
In particolare, l’i-esimo carattere è

  • ‘C’ se la stringa i-esima è cattiva
  • ‘B’ se la stringa i-esima è buona

Assunzioni

  • Il file di input non contiene altri caratteri oltre a quelli indicati nel testo.
  • Il file di output non deve contenere altri caratteri oltre a quelli contenuti nel testo; in particolare non ci devono essere linee di separazione fra le linee di output.
  • Il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output.
  • I file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un’istruzione tipo
    fr = fopen( “input.txt”, “r” );
    fw = fopen( “output.txt”, “w” );

    e in Pascal con un’istruzione tipo

    assign( fr, ‘input.txt’ );
    reset( fr );
    assign( fw, ‘output.txt’ );
    rewrite( fw );

Esempio di input/output

Nell’esempio sono date in input 8 stringhe

input.txt output.txt
8
AABBCC
ABABAC
AAABBD
AABBBB
ABBABC
DCBDAB
ADDBBA
AABAAB		 B
B
C
C
C
B
B
B

Osserva

  1. Utilizzo la funzione C per le stringhe: strstr().
  2. Non è necessario individuare un algoritmo intelligente perché le stringhe cattive sono relativamente poche…
#include 
#include 
       
#define LUNGHE   6
#define NCATTIVE 8
#define BUONA   'B'
#define CATTIVA 'C'
     
char *CATTIVE[NCATTIVE]={"AAA","BBB","CCC","DDD","ABC","ABD","ACD","BCD"};

char valuta(char *s)
{
    for(int i=0; i < NCATTIVE; i++)
        if(strstr(s, CATTIVE[i]) != NULL)
            return CATTIVA;
    return BUONA;
}

int main()
{                                                                              
    int  N;                                                    
    char stringa[LUNGHE+1];
   
    FILE *fin =fopen( "input.txt", "r");                      
    FILE *fout=fopen("output.txt", "w");                    
   
    fscanf(fin, "%d", &N);
    for(int i=0; i < N; i++)
    {
        fscanf (fin , "%s"  , stringa        );
        fprintf(fout, "%c\n", valuta(stringa));
    }              
    return 0;
}