Cod sursa(job #342779)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 23 august 2009 16:24:41
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
# include <stdio.h>
# include <string.h>

const long int MAXN=1000000;

typedef struct NOD
        {
        long int reps;
        char val;
        };
        
NOD table[MAXN+1];

long int sol,len,tablelen;

void scrie()
{
     FILE *g=fopen("pscpld.out","w");
     fprintf(g,"%ld\n",sol);
     fclose(g);
}

void citire()
{
     char buff[MAXN+10],*s;
     FILE *f=fopen("pscpld.in","r");
     fread(buff+1,1,MAXN,f);
     fclose(f);
     //conversia in table
     s=strtok(buff+1," \n");
     len=strlen(s);
     long int i;
     for (i=1;i<=len;i++)
         if (i==1||buff[i]!=buff[i-1])
            {
            tablelen++;
            table[tablelen].val=buff[i];
            table[tablelen].reps=1;
            }
         else
            table[tablelen].reps++;
}     

long int min(long int a, long int b) {if (a<b) return a; return b;}

long int maxpal(long int li, long int lf)
{
     long int solloc=0;
     while (li>=1 && lf<=tablelen && table[li].val == table[lf].val)
           {
           solloc+=min(table[li].reps,table[lf].reps);
           if (table[li].reps!=table[lf].reps) break;
           else
               {
               li--;
               lf++;
               }
           }
     return solloc;
}

void calculeaza()
{
     long int i;
     for (i=1;i<=tablelen;i++)
         {
         //consideram toate palindroamele care exista doar cu repetitii in interior!
         sol+=table[i].reps*(table[i].reps+1)/2;
         //consideram toate palindroamele care contin in mijloc segm si se extind in afara
         sol+=maxpal(i-1,i+1);
         }
}

int main()
{
    citire();
    calculeaza();
    scrie();
    return 0;
}