Petali di margherita

di

Giada è un’appassionata di fiori e, ispirata dalla regolarità dei petali, ha inventato un gioco.
Per lei, sua madre genetista ha creato una varietà di margherite multicolori.
Il gioco di Giada prevede che, eliminando certi petali, i petali restanti abbiano cadenza regolare e siano dello stesso colore, formando così una corolla monocolore.

Per esempio, supponendo che i colori siano numerati a partire da 1 in poi, la seguente è una corolla monocolore perché i petali restanti (messi in evidenza dalla linea continua) hanno colore 2 e cadenza regolare (uno ogni tre viene mantenuto):

oii_2007_petali1

Il gioco di Giada consiste nel contare quante corolle monocolore diverse possono essere ottenute da una stessa margherita multicolore.
Il fiore è rappresentato mediante la sequenza S dei colori dei suoi petali.
Scrivete un programma che realizza il gioco di Giada: per esempio, con il fiore S = 2 2 3 1 2 3 2 2 2 1 2 1, il programma deve restituire il numero 6 come risposta in quanto il fiore contiene le seguenti 6 corolle monocolore:

oii_2007_petali2

Dati in Input

Il file input.txt è composto da due righe.

  • La prima riga contiene un intero positivo che rappresenta il numero N di elementi nella sequenza S in ingresso (il numero di petali nella margherita multicolore).
  • La successiva riga contiene N interi (i colori), separati da uno spazio, che formano la sequenza S.

Dati in Output

Il file output.txt è composto da una sola riga che contiene un intero, il quale rappresenta il numero di corolle monocolore contenute nella sequenza S in ingresso.

Assunzioni

  • 2 ≤ N ≤ 8000000
  • I colori contenuti nella sequenza S sono numerati da 1 a 32.

Esempi

input.txt output.txt
1 12
2 2 3 1 2 3 2 2 2 1 2 1		 6
2 11
2 2 3 1 2 3 2 2 2 1 2		 0
3 8
1 2 3 4 4 3 2 1		 0 
#include 
#include 

#define COLORI 32          // numero di colori diversi
int  N;                    // numero di petali
int *petali;               // tutti i petali della margherita
int *collane[COLORI+1];    // le posizioni dei petali per ogni colore
int quanti[COLORI+1];      // quanti per ogni colore

int controlla(int colore, int inizio, int passo)
{
//  printf("%d %d %d\n", colore, inizio, passo);       
    int prima=inizio;
    int seconda=(prima+passo)%N;
    for(int i=1; i <= N/passo; i++)    
    {    
        if(petali[prima] != petali[seconda])
            return 0;
        prima=seconda;
        seconda=(seconda+passo)%N;
    }
//  printf("\n"); 
    return 1;
}

int main()
{
   FILE *file;                              
   file=fopen("input.txt", "r");               // I N P U T
   fscanf(file, "%d", &N);
   petali=(int *)malloc(N*sizeof(int));     
   for(int pet=0; pet < N; pet++)
   {
       int col;
       fscanf(file, "%d", &col);     
       petali[pet]=col;
       quanti[col]++;
   }
   fclose(file);
   
   for(int col=1; col <= COLORI; col++)
       collane[col]=(int *)malloc(quanti[col]*sizeof(int));

   int posizione[COLORI+1];
   for(int col=1; col <= COLORI; col++)
       posizione[col]=0;
   for(int pet=0; pet < N; pet++)
   {
       int col=petali[pet];
       collane[col][posizione[col]]=pet;
       posizione[col]++;
   }
/*
   for(int col=1; col <= COLORI; col++)
   {
      if(quanti[col] != 0)
      {
          printf("%2d: ", col);
          for(int pet=0; pet < quanti[col]; pet++)
             printf("%d ", collane[col][pet]);   
          printf("\n");   
      }
   }
*/  
   int risposta=0;                             // ELABORAZIONE
   for(int col=1; col <= COLORI; col++)
   {
      int quanti_c=quanti[col];
      if(quanti_c != 0)
      {
        for(int passo_c=N/quanti_c; passo_c <= N/2; passo_c++)
        {             
           if(N%passo_c == 0)
           {
               for(int comincia_da=0; comincia_da <= N/passo_c; comincia_da++)  
                  if(collane[col][comincia_da] < passo_c)
                      risposta += controlla(col, collane[col][comincia_da], passo_c);
           }
        }   
      }
   }

   file=fopen("output.txt", "w");              // OUTPUT
   fprintf(file, "%d", risposta);
   fclose(file);
   
// getchar();
   return 0;
}