Cod sursa(job #42889)

Utilizator devilkindSavin Tiberiu devilkind Data 29 martie 2007 16:45:25
Problema Bool Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.1 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LMAX 10000
#define NMAX 1000
#define SIGMA 300

FILE *f = fopen("bool.in","rt"), *g = fopen("bool.out","wt");

char s[LMAX];
long int val[SIGMA],n,i,j,k,l,a[NMAX],rez,b[NMAX];
long int pr[NMAX],ord[NMAX];

void citire()
{
fgets(s,LMAX,f);    
n=strlen(s)-2;
i=0;
k=1;
while (i<=n)
      {
      while (s[i]==' ') i++;
      if (s[i]=='A'&&s[i+1]=='N') {a[k++]=30;
                                i+=3;
                                }
         else if (s[i]=='O'&&s[i+1]=='R') {   
                                          a[k++]=31;
                                          i+=2;
                                          }
         else if (s[i]=='N'&&s[i+1]=='O') {
                                          a[k++]=32;
                                          i+=3;
                                          }
         else if (s[i]=='(') {
                             a[k++]=40;
                             i+=1;
                             }
         else if (s[i]==')') {
                             a[k++]=41;
                             i+=1;
                             }
         else if (s[i]=='T'&&s[i+1]=='R') {a[k++]=28;
                                          i+=4;
                                          }
         else if (s[i]=='F'&&s[i+1]=='A') {
                                          a[k++]=29;
                                          i+=5;
                                          }
	 else {a[k++]=(long int) (s[i] - 'A')+1;
              i+=1;
              }
      }
}

int cmp(const void *x, const void *y)
{
return pr[ * (long int *) x] - pr[ * (long int *) y];
}

long int stanga(long int x)
{
long int st;
st=x-1;
while (b[st]==0) st--;
return st;
}

long int dreapta(long int x)
{
long int dr;
dr=x+1;
while (b[dr]==0) dr++;
return dr;
}

void eval()
{
long int dpth,i,st,dr,v;
dpth=1;
for (i=1;i<=k;i++)
    {
    if (b[i]==40) dpth+=1;
    if (b[i]==41) dpth-=1;
    if (b[i]==30) pr[i]=dpth*3+1;
    if (b[i]==31) pr[i]=dpth*3;
    if (b[i]==32) pr[i]=dpth*3+2;
    }
for (i=1;i<=k;i++)
    ord[i]=i;

qsort(ord,k+1, sizeof(long int), cmp);
for (i=k;i>=1;i--)     
    if (pr[ord[i]]!=0) {
		       st=stanga(ord[i]);
		       dr=dreapta(ord[i]);
		       if (b[ord[i]]==30) {v=val[b[st]]&&val[b[dr]];
				     rez=v;
				     v=29-v;
				     b[st]=0;
				     b[dr]=0;
				     b[ord[i]]=v;
				     st=stanga(ord[i]);
				     dr=dreapta(ord[i]);
				     while (b[st]==40&&b[dr]==41)
					   {
					   b[st]=0;
					   b[dr]=0;
					   st=stanga(ord[i]);
					   dr=dreapta(ord[i]);
					   }
				     }
		       if (b[ord[i]]==31) {v=val[b[st]]||val[b[dr]];
				     rez=v;
				     v=29-v;
				     b[st]=0;
				     b[dr]=0;
				     b[ord[i]]=v;
				     st=stanga(ord[i]);
				     dr=dreapta(ord[i]);
				     while (b[st]==40&&b[dr]==41)
					   {
					   b[st]=0;
					   b[dr]=0;
					   st=stanga(ord[i]);
					   dr=dreapta(ord[i]);
					   }
				     }
		       if (b[ord[i]]==32) {v=!(val[b[dr]]);
				     rez=v;
				     v=29-v;
				     b[dr]=0;
				     b[ord[i]]=v;
				     st=stanga(ord[i]);
				     dr=dreapta(ord[i]);
				     while (b[st]==40&&b[dr]==41)
					   {
                                           b[st]=0;
                                           b[dr]=0;
                                           st=stanga(ord[i]);
                                           dr=dreapta(ord[i]);
                                           }
                                     }
                       }
fprintf(g,"%ld",rez);
}

void solve()
{
long int st,dr;
char c;
long int x,ok,cnt;
fscanf(f,"%ld",&n);
k--;
i=1;
while (i<=k)
      {
    if (a[i]==32) {st=i;
                  j=i;
                  while (a[j]==32)
                        j++;
                  j--;
		  dr=j;
		  if ((dr-st+1)%2==1) {a[st]=32;
				      for (j=st+1, cnt=dr+1 ;cnt<=k; cnt++ , j++)
					  a[j]=a[cnt];
				      k-=(st-dr);
				      }
				      else
				      {
				      for (j=st, cnt=dr+1;cnt<=k; cnt++,j++)
                                          a[j]=a[cnt];
                                      k-=(st-dr+1);
                                      }
                  } 
    i++;
    }                        
   
i=1;
while (i<=k)
    {
    if (a[i]==41) {j=i;
                  ok=0;
                  while (a[j]!=40) {j--;
				   if ((a[j]==30)||(a[j]==31)||(a[j]==32)) ok=1;
				   }
		  if (!ok)
		     {
                     for (cnt=j;cnt<=k;cnt++)
                         a[cnt]=a[cnt+1];
		     for (cnt=i-1;cnt<=k;cnt++)
                         a[cnt]=a[cnt+1];
		     i-=2;
		     k-=2;
                     }
		  }
    i++;
    }
c=fgetc(f);
for (i=1;i<=n;i++)
{
c=fgetc(f);
x=(long int) (c - 'A')+1;
if (val[x]==1) val[x]=0; else val[x]=1;
for (j=1;j<=k;j++)
    b[j]=a[j];
eval();
}

}

int main()
{
for (i=1;i<=29;i++)
    val[i]=0;
citire();
val[28]=1;
val[29]=0;
solve();
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}