630 - Anagrams (II)

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

630 - Anagrams (II)

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

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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 :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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 :(
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

jeff1999
New poster
Posts: 4
Joined: Wed Oct 01, 2003 5:35 pm

630 - Wrong Answer

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
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

630 WA

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;
}

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

630 -> Anagrams (II)

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

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!
_.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

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?
I'm always willing to help, if you do the same.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks!

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

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!
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

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 !

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

More like this...

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!
Last edited by _.B._ on Sat Sep 04, 2004 11:56 pm, edited 1 time in total.
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

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 ?

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Indeed :)

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 :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!
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

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 :-D ), or maybe you have another test cases ?

Here's the code:

[cpp]
/*remove cause of AC*/
[/cpp]
Last edited by wolf on Sat Sep 04, 2004 9:41 pm, edited 1 time in total.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Well, so far...

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.
_.

Post Reply

Return to “Volume 6 (600-699)”