Cod sursa(job #104895)

Utilizator swift90Ionut Bogdanescu swift90 Data 16 noiembrie 2007 19:47:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.34 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int cuv[50100],prop[10000000],put[25],cuvinte;
int main(){
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	int nrc,i,n,a,b,c,pr,ul,mij,s;
	char aux;
	put[0]=1;
	for(i=1;i<22;++i)
		put[i]=put[i-1]*3;
	a='a';
	b='b';
	c='c';
	scanf("%c",&aux);
	n=0;
	while(aux==a || aux==b || aux==c){
		if(a==aux){
			prop[n]=1;
			++n;
		}
		else{
			if(b==aux){
				prop[n]=2;
				++n;
			}
			else{
				prop[n]=3;
				++n;
			}
		}
		scanf("%c",&aux);
	}
	
	nrc=0;
	i=0;
	while((scanf("%c",&aux))!=EOF){
		if(aux==10){
			++nrc;
			i=0;
		}
		else{
			if(a==aux){
				cuv[nrc]+=put[i];
				++i;
			}
			else{
				if(b==aux){
					cuv[nrc]+=put[i]+put[i];
					++i;
				}
				else{
					cuv[nrc]+=put[i]+put[i]+put[i];
					++i;
				}
			}
		}
	}
	sort(cuv,cuv+nrc);
	for(i=1;i<nrc;++i){
		if(cuv[i-1]==cuv[i])
			cuv[i-1]=0;
	}
	sort(cuv,cuv+nrc);
	for(i=0;!cuv[i];++i)
		;
	c=i;
	i=0;
	s=0;
	--nrc;
	for(a=0;a<n;++a){
		while(i<=20 && a+i<n){
			s+=prop[a+i]*put[i];
			pr=c;
			ul=nrc;
			while(pr!=ul){
				mij=(pr+ul)>>1;
				if(s<=cuv[mij])
					ul=mij;
				else
					pr=mij+1;
			}
			if(cuv[pr]==s)
				++cuvinte;
			++i;
		}
		s=i=0;
	}
	printf("%d\n",cuvinte);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}