OJ Board

Code: Select all

  
16
aabaabbaababbbba
aaab
aaba
abab
abba
baaa
babb
bbab
bbba
2000000000

Code: Select all

aabbbbbbabbbbbbb

Code: Select all

/*UVa 517.- Word*/
/*Javier Alvarez Morales*/
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int M=0;

unsigned int Pow2[17]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}; /*I don`t have calculated every time :)*/
char Past[65537][17]; /*Past configurations*/
unsigned int Top;
long  int Whereis[131073]; /*Where is saved the array*/
long int CycleR;   /*Every ? the numbers repited*/
long int Since; /*Since every permutation start the CycleR*/
char Word[17],WordR[17];
char *W,*WR;
char Rules[8][6]; /*Rules of L-System*/
int n;   /*Max lenght of string*/
unsigned long int s;
/*Function that calculate the position in a dictionary lexicographycally ordened*/
unsigned long int CalculaPos(int ini){
    unsigned int Pos=0;
    register int i;
    for( i=0 ; i<n ; i++ )
       if( WR[ (ini+i)%n ] == 'b' )
          Pos += Pow2[ (n-i-1) ];
    return Pos;
}
void Desplaza(int d){
     int i;
     for( i=0; i<n ; i++ )
        W[i] = WR[ (d+i)%n ];
     W[n] = '\0';
}
void Best_Lexico(){
     int i;
     unsigned long int nRule;
     unsigned int Min,D;
     nRule=0;
     Min=32768;
     for( i=0 ; i<n ; i++){
        nRule = CalculaPos(i);
        if( nRule < Min ){
           Min=nRule;
           D=i;
        }
     }
     Desplaza(D);
     if( Whereis[ Min ] != -1 ){ /*Already exist this permutation*/
        CycleR = Top - Whereis[ Min ];
        Since = Whereis[ Min ];
     }else{
         /*Save result*/
         strcpy( Past[Top], W );
         Whereis[ Min ] = Top;
         ++Top; 
     }
}
void Transform(){
     register int i;
     unsigned int nRule;
     char *aux;
     for( i=0 ; i<n ; i++ ){
          nRule=0;
          if( W[ (i-2+n)%n ] == 'b' )
              nRule += 4;
          if( W[ i ] == 'b' )
              nRule += 2;
          if( W[ (i+1)%n ] == 'b' )
              nRule += 1;
          WR[i] = Rules[nRule][3];
     }
     WR[n] = '\0';
     Best_Lexico();
     /*Interchange the strings*/
     aux = W;
     W = WR;
     WR = aux;
}
void ReiniciaVars(){
     Top=0;
     CycleR = -1;
     Since = 0;
     memset( Whereis, -1 ,Pow2[n]*sizeof(unsigned int) );
}
int main(){
  unsigned long int i;  
  W = Word;
  WR = WordR;
  char *aux;
  unsigned int WhichOne;
  while( 0 < scanf("%d ",&n) ){
     ReiniciaVars();
     scanf("%s ",W);
     for( i=0 ; i<8 ; i++ )
        scanf("%s ",Rules[i]);
     scanf("%lu ",&s);
     if( !s ){ /*In case of don't need to aply any transformation, only choise the least lexicographically*/
        aux = W;
        W = WR;
        WR = aux;
        Best_Lexico();  
        /*Interchange the strings*/
        aux = W;
        W = WR;
        WR = aux;
     }
     for( i=0 ; i<s ; i++ ){
        if( CycleR > 0 ) break;
        Transform();
        M?printf(">%s\n",WR):1;
     }
     if( CycleR > 0 ){
         WhichOne = Since  + ( (s - Since -1)%CycleR );
         M?printf("since=%d,CycleR=%lu\n",Since,CycleR):1;
         printf("%s\n",Past[WhichOne]);  
     }else
        printf("%s\n",WR);  
  }
  return 0;
}

Code: Select all

2 < n < 16 the length of the input

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    string rule[8] = {"aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"};
    
    for (int c = 1; c <= 100; c++)
    {
        int n = rand() % 16;
        if (n <= 3) n = 3;
        
        cout << n << '\n';
        for (int i = 1; i <= n; i++)
            cout << (char)('a' + rand() % 2);
        cout << '\n';
        
        for (int i = 0; i < 8; i++)
        {
            cout << rule[i] << (char)('a' + rand() % 2) << '\n';
        }
        
        cout << rand() % 2000000000 << '\n';
    }
    
    return 0;
}