10393 - The One-Handed Typist

[yahoo]

How can the answer be 0 for the test case

Code: Select all

5 5 
6 
7 8 
9 10 
the 
stewardesses 
have 
funny 
hair 

Will anybody please explain. I always get wrong answer in this problem

[Dmytro Chernysh]

The answer for your input is just 0

[yahoo]

The input is same as the sample input in the problem excepte the finger number are given on different line. So, how the result can be different if the finger number are on different line. Will you please kindly how the output of this input is 0?

[Joseph Kurniawan]

[c]#include<stdio.h>
#include<string.h>
int f,n,finger[15],cur,l,sum,count,i,j,k,a[130];
char word[1100][60],out[1100][60],temp[60];
void main(){
while(1){
if(scanf("%i %i",&f,&n)==EOF) break;
for(i=0;i<f;i++) scanf("%i",&finger);

//Checks the letter Jimmy can't type
for(i=0;i<f;i++){
switch(finger){
case 1:a[113]=a[97]=a[122]=1;break;
case 2:a[119]=a[120]=a[115]=1;break;
case 3:a[100]=a[99]=a[101]=1;break;
case 4:a[114]=a[102]=a[118]=a[116]=a[103]=a[98]=1;break;
case 7:a[121]=a[110]=a[104]=a[117]=a[106]=a[109]=1;break;
case 8:a[105]=a[107]=1;break;
case 9:a[111]=a[108]=1;break;
case 10:a[112]=1;break;
}
}


for(i=0;i<n;i++) scanf("%s",&word);

//Checks if Jimmy can type the word
for(i=0,cur=0,count=0;i<n;i++){
l=strlen(word);
if(l>=cur){
for(j=0;j<l;j++){
if(a[word[j]]) break;
}
if(j==l){
if(l>cur){count=0;cur=l;}
else count++;
strcpy(out[count],word);
}
}
}

//Sorts the word Jimmy can type
for(i=0;i<count;i++){
j=i;
for(k=i+1;k<=count;k++){
if(strcmp(out[k],out[j])<0) j=k;
}
if(j!=i){
strcpy(temp,out);
strcpy(out,out[j]);
strcpy(out[j],temp);
}
}

memset(a,0,sizeof(a));

//Counts the total sum of words (excluding the same words)
for(i=0,sum=0;i<=count;i++){
while(strcmp(out,out[i+1])==0) i++;
sum++;
}
printf("%i\n",sum);

//Prints the words (excluding the same words)
for(i=0;i<=count;i++){
while(strcmp(out,out[i+1])==0) i++;
printf("%s\n",out[i]);
}
}
}
[/c]

What's could possibly be wrong with my code?
Any help plz???

[Joseph Kurniawan]

Is it true that for Input:
5 5
6
7 8
9 10
the
stewardesses
have
funny
hair

The output will zero?

[Per]

No. The output should be the same as in the first sample output.

[Joseph Kurniawan]

Well then, could you plz tell me the mistake in my code?

[Joseph Kurniawan]

Never mind it. Got it AC now.
What makes it a WA seems to be the method of excluding the duplicate words (the total number and the printing part).
So I tried to exlude the duplicate words first before sorting them and it worked.
But I'm still curious where's the 'bugginess' of the previous method :
[c]
while(strcmp(out,out[i+1])==0) i++;
[/c]

Can anybody give me a sample input that will show the 'bugginess' of the method I showed above?

Thanks a lot.

[SilVer DirectXer]

i got a WA too, i have checked if repeated words...why WA?
[cpp]
#include <stdio.h>
#include <string.h>
char words[1002][52];
char v[1002][52];
char tempch[52];
int i,j,k,l,m,n;
char dummy[100];
char cant[100];
int counter,vcounter;
int ok;
int maxlen;
void main()
{
while (1)
{
scanf("%d",&n);

if (feof(stdin))
break;

scanf("%d",&m);
gets(dummy);



counter=1;
ok=1;

for (i=1;i<=n;i++)
{
scanf("%d",&j);
if (j==1)
{
cant[counter++]='q';cant[counter++]='a';cant[counter++]='z';
}
if (j==2)
{
cant[counter++]='w';cant[counter++]='s';cant[counter++]='x';
}
if (j==3)
{
cant[counter++]='e';cant[counter++]='d';cant[counter++]='c';
}
if (j==4)
{
cant[counter++]='r';cant[counter++]='f';cant[counter++]='v';
cant[counter++]='t';cant[counter++]='g';cant[counter++]='b';
}
if (j==5 && ok==1)
{
cant[counter++]=' ';
ok=0;
}
if (j==6 && ok==1)
{
cant[counter++]=' ';
ok=0;
}
if (j==7)
{
cant[counter++]='y';cant[counter++]='h';cant[counter++]='n';
cant[counter++]='u';cant[counter++]='j';cant[counter++]='m';

}
if (j==8)
{
cant[counter++]='i';cant[counter++]='k';cant[counter++]=',';
}
if (j==9)
{
cant[counter++]='o';cant[counter++]='l';cant[counter++]='.';

}
if (j==10)
{
cant[counter++]='p';cant[counter++]=';';cant[counter++]='/';
}


}
gets(dummy);
counter--;
vcounter=1;



for (i=1;i<=m;i++)
{
gets(words);
}


maxlen=0;
vcounter=0;
for (i=1;i<=m;i++)
{
ok=1;
for (j=0;j<(int)strlen(words);j++)
{

for (k=1;k<=counter;k++)
{
if (words[j]==cant[k])
{
ok=0;
break;
}
}
if (ok==0)
break;
}
if (ok==1)
{
if ((int)strlen(words)>=maxlen)
{
if ((int)strlen(words)>maxlen)
{
maxlen=(int)strlen(words);
vcounter=0;
}


strcpy(v[++vcounter],words);
for (k=1;k<vcounter;k++)
{
if (strcmp(v[k],v[vcounter])==0)
vcounter--;
}
}
}
}



if (vcounter==1)
{
printf("1\n");
puts(v[1]);
}
else
{

for (i=2;i<=vcounter;i++)
{
for (j=1;j<i;j++)
{
if (strcmp(v,v[j])<0)
{
strcpy(tempch,v);
for (k=i;k>j;k--)
{
strcpy(v[k],v[k-1]);
}
strcpy(v[j],tempch);
}
}
}


printf("%d\n",vcounter);

for (i=1;i<=vcounter;i++)
puts(v);
}

}

}
[/cpp]

[UFP2161]

SilVer DirectXer:

Check your "check for duplicates" code again. It's not entirely correct.

[SilVer DirectXer]

SilVer DirectXer:

Check your "check for duplicates" code again. It's not entirely correct.

thanks UFP2161 , i have updated the code and checked repeated before putting to v[].(see above)
however. seems i am still WA....
why?

[UFP2161]

SilVer DirectXer:

The only possible problem I see would relate to the following from the problem description:

Each description begins with two numbers, F, the number of fingers that Jimmy cannot use, and N<= 1000, the number of big words to consider.

Following are F numbers listing the fingers Jimmy cannot use.

Also, remember that gets() reads to end of current line. Hope that helps!

[SilVer DirectXer]

thanks anyway!
i got a AC now

[madelman]

Anybody knows why this code gives WA? It seems to work in every case I thought, it counts the words without repetition, the output is sorted...

Any help or any test case where this fails?

[cpp]
#include <iostream>
#include <string>
#include <sstream>
#include <set>

bool letras[128];

bool correcta(string t) {
for (int i=0; i < t.length(); i++)
if (letras[t] == false) return false;

return true;
}

void main() {

int F, N, dedo;
string tmp;
set<string> pal;
int maxlon, num;

while (true) {

if(!getline(cin, tmp)) break;

stringstream ss(tmp);
ss >> F >> N;

for (int i=0; i < 128; i++)
letras = true;

// marquem quines tecles no pot pulsar
for (int i=0; i < F; i++) {
cin >> dedo;
switch(dedo) {
case 1:
letras['q'] = letras['a'] = letras['z'] = false;
break;
case 2:
letras['w'] = letras['s'] = letras['x'] = false;
break;
case 3:
letras['e'] = letras['d'] = letras['c'] = false;
break;
case 4:
letras['r'] = letras['f'] = letras['v'] = letras['t'] = letras['g'] = letras['b'] = false;
break;
case 5:
letras[' '] = false;
break;
case 6:
letras[' '] = false;
break;
case 7:
letras['y'] = letras['h'] = letras['n'] = letras['u'] = letras['j'] = letras['m'] = false;
break;
case 8:
letras['i'] = letras['k'] = letras[','] = false;
break;
case 9:
letras['o'] = letras['l'] = letras['.'] = false;
break;
case 10:
letras['p'] = letras[';'] = letras['/'] = false;
break;
}
}
getline(cin, tmp);

pal.clear();
maxlon = 0;
// llegim cada paraula i comprobem si la pot escriure
// si pot, la guardem per mostrar-la despres
for (int i=0; i < N; i++) {
getline(cin, tmp);
if (correcta(tmp)) {
if (tmp.length() > maxlon) maxlon = tmp.length();
pal.insert(tmp);
}
}

set<string>::const_iterator itm;

num = 0;
for (itm=pal.begin(); itm!=pal.end(); itm++)
if ((*itm).length() == maxlon)
num++;

cout << num << endl;

for (itm=pal.begin(); itm!=pal.end(); itm++)
if ((*itm).length() == maxlon)
cout << *itm << endl;

}
}
[/cpp]

[oulongbin]

i don't know why!
[cpp]
#include <iostream>
using namespace std;
#include <cstring>
#include <cstdio>

int main()
{
int ff,n;
int x;
bool f[200];
int i,j;
int len;
int count;
int num;
char word[60];
char w[1010][60];
char output[1010][60];
while(cin>>ff>>n)
{
for(i=0;i<200;i++)
{
f=true;
}
while(ff--)
{
cin>>x;
switch(x)
{
case 1:f[int('q')]=f[int('a')]=f[int('z')]=false;break;
case 2:f[int('w')]=f[int('s')]=f[int('x')]=false;break;
case 3:f[int('e')]=f[int('d')]=f[int('c')]=false;break;
case 4:f[int('r')]=f[int('f')]=f[int('v')]=f[int('t')]=f[int('g')]=f[int('b')]=false;break;
case 5:f[int(' ')]=false;break;
case 6:f[int(' ')]=false;break;
case 7:f[int('y')]=f[int('h')]=f[int('n')]=f[int('u')]=f[int('j')]=f[int('m')]=false;break;
case 8:f[int('i')]=f[int('k')]=f[int(',')]=false;break;
case 9:f[int('o')]=f[int('l')]=f[int('.')]=false;break;
case 10:f[int('p')]=f[int('/')]=f[int(';')]=false;break;
}
}
count=0;
num=0;
cin.get();
while(n--)
{
cin.getline(word,60);
//gets(word);
//cin>>word;
len=strlen(word);
for(i=0;i<len;i++)
{
if(f[int(word)]==false)
break;
}
if(i==len)
{
for(i=0;i<len;i++)
{
w[count]=word;
}
w[count]='\0';
count++;
}
}
len=strlen(w[0]);
for(i=1;i<count;i++)
{
if(len<strlen(w))
len=strlen(w);
}
for(i=0;i<count;i++)
{
if(len==strlen(w))
{
strcpy(output[num++],w);
}
}

for(i=0;i<num-1;i++)
{
for(j=0;j<num-1-i;j++)
{
if(strcmp(output[j],output[j+1])>0)
{
strcpy(word,output[j]);
strcpy(output[j],output[j+1]);
strcpy(output[j+1],word);
}
}
}
cout<<num<<endl;
for(i=0;i<num;i++)
cout<<output<<endl;
}
return 0;
}
[/cpp]