454 - Anagrams

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

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

454 Anagrams

Post by serur » Thu Apr 06, 2006 8:42 pm

I'm getting RTE with this stuff, how do you think what may cause it?

Code: Select all

/*"anagrams"*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>
#define L 1009
#define N 100
 
typedef
struct{
	char word[1009];
	char sig[1009];
}foo;

foo ans[N];

int isempty(char a[]){
	int t;
	for(t=0;t<(int)strlen(a);t++)
		if(!isspace(a[t]))
			return 0;
	return 1;
}
int foo_comp(const void *a,const void *b){
	int t;
	foo *x=(foo*)a;
	foo *y=(foo*)b;
	t=strcmp(x->sig,y->sig);
	if(t==0)
		return strcmp(x->word,y->word);
	else
		return t;

}
int char_comp(const char *a,const char *b){
	/*if((islower(*a) && islower(*b))||(isupper(*a) && isupper(*b)))
		return *a-*b;
	else{
		if(islower(*a) && isupper(*b))
			return *a-('a'-'A')-*b;
		else
			return *a+('a'-'A')-*b;
	}*/
	return *a-*b;
}
void det_sig(foo *A){
	char s[L];
	int t,k;
	qsort(A->sig,strlen(A->sig),sizeof(char),char_comp);
	for(t=0,k=0;t<(int)strlen(A->sig);t++)
		if(!isspace(A->sig[t]))
			s[k++]=A->sig[t];
	s[k]='\0';
	strcpy(A->sig,s);
}
int main()
{
	int T;
	int status;
	int n,t,i,j,k;
	char dummy[L];
#ifndef ONLINE_JUDGE
	freopen("A.in","r",stdin);
#endif
	scanf("%d",&T);
	gets(dummy); 
	gets(dummy); 
	while(T--)
	{
		for(i=0;gets(ans[i].word);i++)
		{
			if(isempty(ans[i].word))
				break;
			strcpy(ans[i].sig,ans[i].word);
			det_sig(&ans[i]);
		}
		n=i;
		qsort(ans,n,sizeof(foo),foo_comp);
		status=0;
		for(t=0;t<n-1;t++)
			if(strcmp(ans[t].sig,ans[t+1].sig)==0)
			{
				status=1;
				break;
			}
		if(!status)
			putchar('\n');
		else
		{
			k=1;t=k;
			while(t<=n)
				if(t==n || strcmp(ans[t].sig,ans[t-1].sig)!=0)
				{
					for(i=k-1;i<t;i++)
						for(j=i+1;j<t;j++)
							printf("%s = %s\n",ans[i].word,ans[j].word);
					k=t+1;
					t=k;
				}
				else
					t++;
		}
		if(T)
			putchar('\n');
	}
	return 0;
}
Thanks in advance
Last edited by serur on Thu Jun 01, 2006 7:27 pm, edited 3 times in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Jun 01, 2006 5:27 am

i take input as below:

Code: Select all

scanf("%d", &testCase);
gets(dummy);
gets(dummy);
while(testCase--)
{
     for(i = 0; gets(ans[i].word); ++i) // i used word[1009]
     {
          if(isempty(ans[i].word)) 
                break;
          ............
          ............
      }
      n = i;
}
there shouldn't be any blank line after the last test case
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Thu Jun 01, 2006 6:56 pm

Thank you!

The fact is, I have given up this problem...
Now I'll try again :)

Best regards.

EDIT: I have changed my code according to your instructions - see above.
But still RTE...

Also,

Code: Select all

3 

carthorse 
horse 
horse cart 
i do not know u 
ok i now donut 
orchestra 

aPPLE 
PPLEa 
LEaPP 

erosh 
erosh 
horse 
horse 
ac bd 
a cbd 
q 
q 
[horse]' 
[e]rosh' 
iiiiiiiiiiiiij 
iiiiiiiiiiiiji 
orchestra 
pq 
qp 
carthorse 
erosh 
horsecart 
ok i now donut 
oknow uidot n 
i do not know u 
abdc 
kencti kecut 
kecut kencit

Output:
carthorse  = horse cart 
carthorse  = orchestra 
horse cart  = orchestra 
i do not know u  = ok i now donut 

LEaPP  = PPLEa 
LEaPP  = aPPLE 
PPLEa  = aPPLE 

[e]rosh'  = [horse]' 
a cbd  = abdc 
a cbd  = ac bd 
abdc  = ac bd 
carthorse  = horsecart 
carthorse  = orchestra 
horsecart  = orchestra 
kecut kencit = kencti kecut 
i do not know u  = ok i now donut 
i do not know u  = oknow uidot n 
ok i now donut  = oknow uidot n 
erosh  = erosh 
erosh  = erosh 
erosh  = horse 
erosh  = horse 
erosh  = erosh 
erosh  = horse 
erosh  = horse 
erosh  = horse 
erosh  = horse 
horse  = horse 
iiiiiiiiiiiiij  = iiiiiiiiiiiiji 
pq  = qp 
q  = q 
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Jun 01, 2006 10:34 pm

my output for the last input

Code: Select all

[e]rosh'  = [horse]'
a cbd  = abdc
a cbd  = ac bd
abdc  = ac bd
carthorse  = horsecart
carthorse  = orchestra
erosh  = erosh
erosh  = erosh
erosh  = horse
erosh  = horse
erosh  = erosh
erosh  = horse
erosh  = horse
erosh  = horse
erosh  = horse
horse  = horse
horsecart  = orchestra
i do not know u  = ok i now donut
i do not know u  = oknow uidot n
iiiiiiiiiiiiij  = iiiiiiiiiiiiji
kecut kencit = kencti kecut
ok i now donut  = oknow uidot n
pq  = qp
q  = q
but i am not sure why RTE. and my process is little bit different than yours, to check for anagram i just compare two strings' frequency. i used

Code: Select all

struct{ 
   char word[1009]; 
   int freq[130]; // for 127 charcaters
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 10, 2006 11:01 am

Well, I am getting crazy ....continuously getting RTE , but I dont know whats the reason ? All the sample input and output matches for my prgram and arraysize are far too big than its necessary ... I have absolutely no idea whats going wrong here :s

can any one help me? Here is my code..

Code: Select all

removed after AC
Thanx.
Last edited by Kallol on Tue Jul 18, 2006 1:17 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Jul 12, 2006 7:31 pm

tui amar ager post gulo porish ni?
use

Code: Select all

       while(1) 
      { 
         if(gets(s) == NULL)
              break;
         if(strcmp(s,"")==0) 
         { 
            break; 
         } 
         strcpy(a[i],s); 
         i++; 
      }
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 18, 2006 1:18 pm

Thanx Ayon !

i finally got AC. But whats the reason for these types of nasty input system ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Tue Jul 18, 2006 6:50 pm

because the last test case ends with EOF, not newline
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

ALEXANDRIA_2
New poster
Posts: 10
Joined: Tue Nov 07, 2006 2:03 pm
Location: Jakarta

454 why PE???

Post by ALEXANDRIA_2 » Wed Nov 22, 2006 7:33 pm

Hi all, I still wondering what makes my program PE...
can u give me some hints...
thanks before..

Code: Select all

input:
2

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

aaa
aaa
aaa

Code: Select all

output:
carthorse = horse cart--->end of line
carthorse = orchestra---->eol
horse cart = orchestra--->eol
i do not know u = ok i now donut--->eol
--->new line
aaa = aaa-->eol
aaa = aaa-->eol
aaa = aaa--->eol
Impossible is nothing

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Nov 22, 2006 10:21 pm

Dont open a new thread if there is one already. My accepted code returns same output.
Ami ekhono shopno dekhi...
HomePage

ALEXANDRIA_2
New poster
Posts: 10
Joined: Tue Nov 07, 2006 2:03 pm
Location: Jakarta

Post by ALEXANDRIA_2 » Wed Dec 20, 2006 2:59 pm

Thanks for replying Jan
finally found my silly mistake
I forgot to print a new line after the last output
Impossible is nothing

zooom
New poster
Posts: 4
Joined: Tue Jun 12, 2007 9:20 am

WA help!!

Post by zooom » Tue Jun 12, 2007 9:28 am

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;

int main(){
 int testcases;
 cin>>testcases;
 string emptyss;
 getline(cin,emptyss);
 getline(cin,emptyss);
 bool ans=false;
	while(testcases>0){
		if(ans){
		cout<<endl;
		}
	ans=true;
	string dummy;
	vector<string>finals(100);
	vector<string>charac(100);
		for(int i=0;i<finals.size();i++){
		finals[i]=charac[i]="zzzzzz";
		}
	int m=0;
		while(getline(cin,dummy)){
			if(dummy==""){
			break;
			}
//cout<<dummy<<endl;
		finals[m]=dummy;
		m++;
		}
//for(int i=0;i<6;i++){
//cout<<finals[i]<<endl;
//}
	m=0;
	sort(finals.begin(),finals.end());
	string itr;
		for(int i=0;i<finals.size();i++){
			if(finals[i]=="zzzzzz"){
			break;
			}
			for(int j=0;j<finals[i].length();j++){
				if(finals[i].at(j)!=32){
					itr+=finals[i].substr(j,1);
				}
			}
//cout<<itr<<endl;
		vector<char>anand(itr.length());
			for(int i=0;i<itr.length();i++){
				anand[i]=(char)itr[i];
			}
			itr="";
		sort(anand.begin(),anand.end());
			for(int i=0;i<anand.size();i++){
				itr+=(char)anand[i];
			}
		charac[i]=itr;
		itr="";
		}
		for(int i=0;i<charac.size();i++){
			if(charac[i]=="zzzzzz"){
			break;
			}
			for(int j=i+1;j<charac.size()-1;j++){
				if(charac[i]==charac[j]){
				cout<<finals[i]<<" "<<"="<<" "<<finals[j]<<endl;
				}
			}
		}
	testcases--;
	}
 }


I wrote The following code checked against the inputs given above .. the output was in the same order .. please anyone tell me the error :( :( why i am getting WA!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: Help me in 454

Post by Obaida » Tue Jul 28, 2009 4:14 am

I am getting WA for this problem.. :(
Any one who got recent Acc plz reply the output of this case:

Code: Select all

1

aaaa
aaa a
a           aaa
aaaa
aaaa

My output is:

Code: Select all

aaaa = aaaa
aaaa = aaa a
aaaa = a           aaa
aaa a = a           aaa
>>i searched uvatoolkit bt this problem don't exists. :(
Advance thank for helping.. :)
Last edited by Obaida on Tue Jul 28, 2009 5:40 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Help me in 454

Post by mf » Tue Jul 28, 2009 4:49 am

Obaida wrote:I am getting WA for this problem.. :(
Any one who got recent Acc plz reply the output of this case:

Code: Select all

1

aaaa
aaa a
a           aaa
aaaa
aaaa

I get:

Code: Select all

a           aaa = aaa a
a           aaa = aaaa
aaa a = aaaa

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 454 - Anagrams

Post by Obaida » Tue Jul 28, 2009 5:36 pm

I changed my code a bit. Got the above case right but still getting wa(such a simple code!!).
Would you please help me with some test case?
And here is my code:-

Code: Select all

removed
Last edited by Obaida on Tue Jul 28, 2009 7:23 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 4 (400-499)”