Page 1 of 2

630 - Anagrams (II)

Posted: Fri Mar 29, 2002 4:55 pm
by Subeen
i can't find why my prog. got W.A.
pls help me.

Code: Select all

/* @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 */

Posted: Wed Feb 26, 2003 4:51 pm
by Dominik Michniewski
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

Posted: Thu Feb 27, 2003 10:45 pm
by anupam
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 :oops: :oops: :oops:

Posted: Fri Feb 28, 2003 9:15 am
by Dominik Michniewski
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 :(

630 - Wrong Answer

Posted: Sat Oct 04, 2003 1:50 am
by jeff1999
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]

630 WA

Posted: Wed Oct 08, 2003 2:18 pm
by nikhil
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;
}

630 -> Anagrams (II)

Posted: Sun Aug 29, 2004 9:41 pm
by _.B._
Greetings!
I think I've got enough WAs with this one already :o
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 :D
Thanks in advance!

Posted: Mon Aug 30, 2004 2:47 am
by Ryan Pai
a) Don't sort the words
b) clear the dictionary after each case
c) Do you know it's a multiple input problem?

Thanks!

Posted: Mon Aug 30, 2004 4:54 am
by _.B._
Greetings Ryan Pai!
Thanks for the prompt answer! 8)
I'll consider all that now :)
Wasn't sure if it was Multiple Input or not :o

Thanks!, and keep posting!

Edited: ACed now 8) Thanks for the help!
Freaking lack of description in the problems...

Keep posting!

Posted: Fri Sep 03, 2004 1:14 am
by wolf
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 !

More like this...

Posted: Fri Sep 03, 2004 4:20 pm
by _.B._
Greetings!
More like this:

/* See I/O in post below */

Hope it helps ;)
Thanks to Daveon too!

Keep posting!

Posted: Fri Sep 03, 2004 5:45 pm
by wolf
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 ?

Indeed :)

Posted: Fri Sep 03, 2004 7:03 pm
by _.B._
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 :o
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!

Posted: Fri Sep 03, 2004 10:36 pm
by wolf
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 :-D ), or maybe you have another test cases ?

Here's the code:

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

Well, so far...

Posted: Sat Sep 04, 2004 1:16 am
by _.B._
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.