630 - Anagrams (II)

Subeen · Post by **Subeen** » Fri Mar 29, 2002 4:55 pm

i can't find why my prog. got W.A.
pls help me.

/* @JUDGE_ID: 13487FC 630 C++ */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int sort_fun(const void *a,const void*b)
{
   return( strcmp((char *)a,(char *)b) );
}

void main()
{
   char dic[1000][20];
   char temp[1000][20];
   char test[20], in[10];
   int letter1[26];
   int letter2[26];
   int n, i, j, flag, a, b;

   int N, I;

   gets(in);
   N = atoi(in);
   for(I=0; I<N; I++)
   {
   for(i=0; i<26; i++)
   {
	letter1[i] = 0;
	  letter2[i] = 0;
   }

   gets(in);
   gets(in);
 	n = atoi(in);

   for(i=0; i<n; i++)
		gets(dic[i]);

   for(;;)
   {
     gets(test);
	  test[strlen(test)] = 0;
	if(!strcmp(test, "END")) break;
	for(i=0; i<26; i++)
		letter1[i] = 0;
	  for(i=0; i<strlen(test); i++)
	  {
		letter1[test[i]-'a']++;
	  }
	  b = 0;
	  printf("Anagrams for: %sn", test);
		for(i=0; i<n; i++)
	  {
		 flag = 1;
	if(strlen(test)==strlen(dic[i]))
		 {
	for(j=0; j<strlen(dic[i]); j++)
			{
	letter2[dic[i][j]-'a']++;
			}

			for(j=0; j<26; j++)
			{
	if(letter1[j]!=letter2[j])
			   {
				flag = 0;
				  break;
			   }
			}
			if(flag)
			{
	strcpy(temp[b++], dic[i]);
			}
	for(j=0; j<26; j++)
		letter2[j] = 0;
		 }
	  }
	  if(b)
		{
qsort((void *)temp, b, sizeof(temp[0]), sort_fun);
for(a=0; a<b; a++)
printf("%3d) %sn", a+1, temp[a]);
}
else
		{
printf("No anagrams for: %sn", test);
		}
   }
   printf("n");
   }
}
/* @END_OF_SOURCE_CODE */

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Feb 26, 2003 4:51 pm

My accepted source produce:

Code: Select all

Anagrams for: atra
  1) rata
  2) atar
  3) tara
  4) rtaa
  5) aart

and it's multiply input problem ....

Dominik Michniewski

anupam · Post by **anupam** » Thu Feb 27, 2003 10:45 pm

hello dominik,,
i have solved the touph part of anagram i think,
but now i am in trouble with anagram II
will you let me know what is the case very special here to be treated seperately,,
if there is none, then i will post my code or send it to U for help,
will you mind?
thanks--
--anupam

Dominik Michniewski · Post by **Dominik Michniewski** » Fri Feb 28, 2003 9:15 am

There is no special case ....
Only one thing is important - I don't know, but if you sort words (easier search) you must output it in order from input ...

Dominik

PS. If you want send me your code via PM or mail from my stats page. But I give you answer not earlier than in monday - I have a lot of job this weekend

jeff1999 · Post by **jeff1999** » Sat Oct 04, 2003 1:50 am

I am getting a "Wrong Answer" for this solution. I realize that this is a multiple input problem, and I assume that I'm handling that correctly. Does anyone have some sample I/O that could possibly break this code?

[cpp]
// 630 - Anagrams (II)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <map>

struct Word
{
char val[21];
char sor[21];
};

int c_cmp(const void * a, const void * b)
{
return ((int)(*((char*)a))) - ((int)(*((char*)b)));
}

int w_cmp(const void * a, const void * b)
{
Word * w1 = (Word*)a, * w2 = (Word*)b;
return strcmp(w1->val, w2->val);
}

int main(int argc, char ** argv)
{
Word s[2][1000];
char msg[1000];
int i, j, k, n, nw, cn;
std::map<std::string, std::string> mymap;

scanf("%i", &cn);
while (cn > 0)
{
--cn;
scanf("%i", &n);
nw = 0;
mymap.clear();
for (i = 0; i < n; ++i)
{
scanf("%s", s[0][i].val);
if (mymap.find(s[0][i].val) != mymap.end())
{
--i;
--n;
}
else
{
mymap[s[0][i].val] = s[0][i].val;
strcpy(s[0][i].sor, s[0][i].val);
qsort(s[0][i].sor, strlen(s[0][i].sor), sizeof(char), c_cmp);
}
}
qsort(s[0], n, sizeof(Word), w_cmp);
while (scanf("%s", s[1][nw].val) == 1 && strcmp(s[1][nw].val, "END") != 0)
{
strcpy(s[1][nw].sor, s[1][nw].val);
qsort(s[1][nw].sor, strlen(s[1][nw].sor), sizeof(char), c_cmp);
++nw;
}
for (i = 0; i < nw; ++i)
{
printf("Anagrams for: %s\n", s[1][i].val);
k = 0;
for (j = 0; j < n; ++j)
{
if (strcmp(s[1][i].sor, s[0][j].sor) == 0)
{
printf("%3i) %s\n", ++k, s[0][j].val);
}
}
if (k == 0)
{
printf("No anagrams for: %s\n", s[1][i].val);
}
}
printf("\n");
}

return 0;
}
[/cpp]

nikhil · Post by **nikhil** » Wed Oct 08, 2003 2:18 pm

I am getting "WA"
for the following code
some body please help me???????????

#include<stdio.h>
#include<string.h>
#include<assert.h>

int i, a,b, len,l1,l2, intP[30], tr[30], h[30], hh, in, found ;
char voca[1000][23], test[30];

int main(void)
{
/* freopen("c:\\a\\630.txt","rb",stdin); */

int dummy;

dummy=scanf("%d", &a);
assert(dummy==1);
b = a;
while(a--)
scanf("%s", &voca[in++]);

while( scanf("%s", test) && strcmp(test,"END") ){

for(i=0; test; i++)
intP[ (test-'a') ]++;

printf("Anagrams for: %s\n", test );

found=0;
l2 = strlen(test);

a=-1;
int f=1;

while( ++a<b ){
l1 = strlen(voca[a]);

if( l2 != l1 )continue;

for(hh=i=0; voca[a]; i++)
tr[ h[hh]=(voca[a]-'a') ]++, hh++;

i = hh;

while(hh--)
if(tr[ h[hh] ]!=intP[ h[hh] ])break;

if(hh==-1)
printf("%3d) %s\n", f++, voca[a]) ,found++;

for(hh=0; hh<i; hh++) h[hh]=tr[ h[hh] ] = 0;
}
for(i=0; i<30; i++) intP = 0;

if( !found )
printf("No anagrams for: %s\n", test );
}
return 0;
}

_.B._ · Post by **_.B._** » Sun Aug 29, 2004 9:41 pm

Greetings!
I think I've got enough WAs with this one already

What's the critical input for this problem?
How long is the vocabulary going to be?
Is the statement

All words are lowercase (word END means end of data - it is NOT a test word). You can assume all words are not longer than 20 characters.

true?
Is this the correct format?:

Code: Select all

Anagrams for: tola
  1) atol
  2) lato
  3) tola
...
102) tlao

Is this a goo I/O?
Input:

Code: Select all

8
lato
atol
microphotographics
rata
rola
tara
tola
pies
tola
kola
aatr
photomicrographics
END
2
xxx
kola
tola
kola
aatr
photomicrographics
xxx
END

Output:

Code: Select all

Anagrams for: tola
  1) atol
  2) lato
  3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
  1) rata
  2) tara
Anagrams for: photomicrographics
  1) microphotographics
Anagrams for: tola
  1) atol
  2) lato
  3) tola
Anagrams for: kola
  1) kola
Anagrams for: aatr
  1) rata
  2) tara
Anagrams for: photomicrographics
  1) microphotographics
Anagrams for: xxx
  1) xxx

ANY help or tips for this problem will be really appreciated

Thanks in advance!

Ryan Pai · Post by **Ryan Pai** » Mon Aug 30, 2004 2:47 am

a) Don't sort the words
b) clear the dictionary after each case
c) Do you know it's a multiple input problem?

_.B._ · Post by **_.B._** » Mon Aug 30, 2004 4:54 am

Greetings Ryan Pai!
Thanks for the prompt answer!

I'll consider all that now

Wasn't sure if it was Multiple Input or not

Thanks!, and keep posting!

Edited: ACed now

Thanks for the help!
Freaking lack of description in the problems...

Keep posting!

wolf · Post by **wolf** » Fri Sep 03, 2004 1:14 am

Hi !

So, the I/O should be sth like that ?

Input:

Code: Select all

8 
lato 
atol 
microphotographics 
rata 
rola 
tara 
tola 
pies 
tola 
kola 
aatr 
photomicrographics 
END 
2 
xxx 
kola 
tola 
kola 
aatr 
photomicrographics 
xxx 
END

Output:

Code: Select all

Anagrams for: tola
  1) lato
  2) atol
  3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
  1) rata
  2) tara
Anagrams for: photomicrographics
  1) microphotographics
Anagrams for: tola
No anagrams for: tola
Anagrams for: kola
  1) kola
Anagrams for: aatr
No anagrams for: aatr
Anagrams for: photomicrographics
No anagrams for: photomicrographics
Anagrams for: xxx
  1) xxx

Help me please !

_.B._ · Post by **_.B._** » Fri Sep 03, 2004 4:20 pm

Greetings!
More like this:

/* See I/O in post below */

Hope it helps

Thanks to Daveon too!

Keep posting!

wolf · Post by **wolf** » Fri Sep 03, 2004 5:45 pm

Hi _.B._ !

Are you sure that the "3" in the begining of your sampe input is correct ?
It is not mentioned in the problem specification about counting test cases ?

_.B._ · Post by **_.B._** » Fri Sep 03, 2004 7:03 pm

Hello Wolf!
Indeed it is, and I bet that's why there are SO many WAs for this problem.
It just says in one of the Problemsets that it's a MI problem, but in the description it doesn't mention neither that it has a number of cases in the beginning of the problem, nor that you have to output a blank line between output for each case, nor it is indeed a MI problem

The description of this problem is pretty poor regarding the input it has.
You may try to read the number of cases, then use the FOR, or read the number of cases, ignore it, and then work untill EOF.
I made it both ways

Hope it helps.

Keep posting!

wolf · Post by **wolf** » Fri Sep 03, 2004 10:36 pm

Hi !
Thanx for helping _.B._ but I still have WA (I don't know why). Can you look up my code for some stupid mistakes. My output for input behind is identicaly like yours (I hope

), or maybe you have another test cases ?

Here's the code:

[cpp]
/*remove cause of AC*/
[/cpp]

_.B._ · Post by **_.B._** » Sat Sep 04, 2004 1:16 am

Greetings!
Well, so far, you could change this:

[cpp] if (strcmp(word.txt,word2.txt)==0)
{
czy++;
cout.width(3);
cout << czy;
cout << ") " << word.original << endl;
}
[/cpp]

To avoid the printing of " ".
But still can't find a critical input for your program.
Will post later.

OJ Board

630 - Anagrams (II)

630 - Anagrams (II)

630 - Wrong Answer

630 WA

630 -> Anagrams (II)

Thanks!

More like this...

Indeed :)

Well, so far...