10393 - The One-Handed Typist

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo »

How can the answer be 0 :roll: :roll: :roll: 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 :oops: :oops: :oops: :oops:

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh »

The answer for your input is just 0

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by 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? :cry: :cry: :cry:

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

10393 - The one handed typist WA???

Post by 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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

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

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

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

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by 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
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by 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]
Last edited by SilVer DirectXer on Sun Aug 03, 2003 6:13 pm, edited 1 time in total.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

SilVer DirectXer:

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

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer »

UFP2161 wrote: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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer »

thanks anyway!
i got a AC now

madelman
New poster
Posts: 2
Joined: Tue Mar 30, 2004 11:35 am

10393 - The one-handed typist

Post by 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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

10393 always WA

Post by 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]

Post Reply

Return to “Volume 103 (10300-10399)”