Problem: Cellphone Typing
link: UVA 12526Problem:
We have to say average number of keystroke, we have to press while typing given words of dictionary.
Idea:
1.) Just store given words of dictionary in a trie.
2.) Then, for all of these words count , how many keystroke needed to type., at last avrg the sum.
Solution:
/************************************************************
* *
* ==>>BG_PeaceMind(BISHAL) @NEPAL *
*************************************************************/
///AC- rank-81
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define M 100005
#define S(a) scanf("%d",&a)
#define P(a) printf("%d\n",a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define clr(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define ff(a) memset(a,false,sizeof(a))
#define pb(x) push_back(x)
#define fs first
#define sc second
#define mpr(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define fr(i,a,n) for(i=a;i<=n;i++)
using namespace std;
typedef long long ll;
struct trie
{
int cnt,dis_cnt,len,next[27];
bool isend;
trie()
{
cnt=len=isend=dis_cnt=0;
SET(next);
}
};
trie T[M*15];
int tot;
void Ins(char *s)
{
int p=0;
T[p].cnt++;
for(int i=0;s[i];i++)
{
int k=s[i]-'a';
if(T[p].next[k]==-1)
{
T[p].next[k]=++tot;
T[tot]=trie();
}
p=T[p].next[k];
T[p].cnt++;
T[p].len=i+1;
}
T[p].isend=true;
T[p].dis_cnt++;
}
int countStroke( char *s)
{
int p=0,prev=0,cnt=0;
for(int i=0;s[i];i++)
{
int k=s[i]-'a';
if(i==0)
{
cnt++;
prev=T[p].next[k];
p=T[p].next[k];
continue;
}
p=T[p].next[k];
// if(p==-1)break;
if(T[prev].cnt!=T[p].cnt)cnt++;
prev=p;
}
return cnt;
}
char s[M][100];
int main()
{
int n,m,i,j,k;
while(S(n)==1)
{
// clr(T);
tot=0;
T[0]=trie();
getchar();
fr(i,1,n)
{
gets(s[i]);
Ins(s[i]);
}
ll ct=0,sm=0;
fr(i,1,n)
{
ct=countStroke(s[i]);
// cout<<ct<<endl;
sm+=ct;
}
// cout<<sm<<endl;
printf("%.2lf\n",(sm*1.0/(n*1.0)) );
}
return 0;
}
Comments
Post a Comment