454 - Anagrams

[Junayeed]

First of all keep in mind that this is a multiple input problem.

For input check this

http://online-judge.uva.es/board/viewtopic.php?t=1964

Hope this will help

[wolf]

Thanx Junayeed ! AC now !

P.S. The array size must be about 1000, not 500

[Junayeed]

But I got AC with the array size of 301.

[Minilek]

edit: i switched to C++ and used string to avoid a static array since the input constraints don't say how long each word is to get AC.

[c]
CUT
[/c]

[Arm.Turbo]

Each line in test cases < 64 chars

[yiuyuho]

this is seriously wrong:

using an AC program (2004-11-12):

1

aPPLE
PPLEa
LEaPP

gives output:
LEaPP = PPLEa
LEaPP = aPPLE
PPLEa = aPPLE

how lexicographical is "aPPLE" ranked AFTER "LEaPP"?

so now if you rank aPPLE before LEaPP is then incorrect.

[Antonio Ocampo]

I got RTE several times, please help me.

Code: Select all

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct
{
  char original[10000];
  char junta[10000];
  char ordenada[10000];
}
inputs;


bool orden(inputs a, inputs b)
{
   if( strcmp(a.junta,b.junta)==-1 )
    return true;

   return false;
}


void main()
{
      int n,i=0,j,k,total;
      inputs input[102];

      while( gets(input[i].original) )
      {
         if(input[i].original[0]==' ')
          break;

         n=strlen(input[i].original);

         for(k=0,j=0;j<n;++j)  // borro los espacios
          if(input[i].original[j]!=' ')
           input[i].junta[k++]=input[i].original[j];

         input[i].junta[k]='\n';
         strcpy(input[i].ordenada,input[i].junta); //copio la cadena junta
         sort(input[i].ordenada,input[i].ordenada+strlen(input[i].ordenada)); //ordeno para luego chequear si es anagrama
         ++i;
      }

      total=i;
      sort(input,input+total,orden);

      for(i=0;i<total;++i)
       for(j=i+1;j<total;++j)
        if( !strcmp(input[i].ordenada,input[j].ordenada) )
         cout<<input[i].original<<" = "<<input[j].original<<'\n';
}

[nnahas]

I got RTE several times, please help me.

Code: Select all

         if(input[i].original[0]==' ')

I didn't check very carefully but I think the above line of code has an error. Are you assuming a blank line starts with space character ? What if it is empty?

Also your code looks like you are solving for a single test case . Read the prob carefully . the first line is the number of test cases and each test case maybe up to 100 lines.

Also maybe the line if( strcmp(a.junta,b.junta)==-1 ) is correct but I think it it is better to use the condition if( strcmp(a.junta,b.junta)<0 ) because I think the standard guarantees only the sign of the return value.

[Antonio Ocampo]

Thx for your reply nnahas. I didn't realize that this is a multiple input problem. However, I have corrected this problem and I got RTE, again.

This is my new code

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct
{
char original[10000];
char junta[10000];
char ordenada[10000];
}
inputs;


bool orden(inputs a, inputs b)
{
if( strcmp(a.junta,b.junta)<0 )
return true;

return false;
}


void main()
{
int casos,n,i=0,j,k,total;
inputs input[101];

scanf("%i\n",&casos);

do
{

while( gets(input.original) )
{
if( (input.original[0]==' ') || (strcmp(input.original,"")==0) )
break;

n=strlen(input.original);

for(k=0,j=0;j<n;++j) // borro los espacios
if(input.original[j]!=' ')
input.junta[k++]=input.original[j];

input.junta[k]='\n';
strcpy(input.ordenada,input.junta); //copio la cadena junta
sort(input[i].ordenada,input[i].ordenada+strlen(input[i].ordenada)); //ordeno para luego chequear si es anagrama
++i;
}

total=i;
sort(input,input+total,orden);

for(i=0;i<total;++i)
for(j=i+1;j<total;++j)
if( strcmp(input[i].ordenada,input[j].ordenada) ==0)
cout<<input[i].original<<" = "<<input[j].original<<'\n';

}
while(--casos);
}

[nnahas]

Thx for your reply nnahas. I didn't realize that this is a multiple input problem. However, I have corrected this problem and I got RTE, again.

input.junta[k]='\n';


}

I think the above line has an error, because your string is not null terminated.
You should write input.junta[k]=0; That is probably causing the RTE error.

But you also have other bugs:

if( (input.original[0]==' ') || (strcmp(input.original,"")==0) )

I think this line is still wrong : What if the line is made of tabs ?
What if there is a line containing text that starts with a space ?

Also, as far as I can judge , your code doesn't take this line of the given into account :

"the order of the two phrases within a printed pair must be lexicographic, as well as the first phrases and the second ones in case some first are equal"

Finally , I don't know if this is a trap as I didn't attempt the problem, but they don't specify a maximum line length. perhap you should allocate a very large buffer to use with gets, and allocate the memory in the struct dynamically. I recommend that use the STL string data type, I think it will make your life easier.

[subzero]

Hi,How are you?

I'm trying to solve this problem......but still getting WA... I got some inputs and the outputs are correct (i think), just see....

input:

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

please..... what is the problem???????

Regards

[Andisheh]

I dont know why I get RTE on this problem,could you help me?
This is my code:

Code: Select all

#include <iostream.h>
//#include <fstream.h>
#include <string.h>
char st[100][1000];

int check(int n,int m)
{
	int k,i,j,sw[1000],ssw;
	k=0;
	for(i=0 ; st[n][i] ; i++)
		if(st[n][i]!=' ')
			k++;
	j=0;
	for(i=0 ; st[m][i] ; i++)
		if(st[m][i]!=' ')
			j++;

	if(j!=k)
		return 0 ;
	
	for(i=0 ; st[m][i] ; i++)
		sw[i]=0;
	ssw=1;
	for(i=0 ; st[n][i] && ssw; i++)
	{
		if(st[n][i]!=' ')
		{
			for(j=0 ; st[m][j] ; j++)
			{
				ssw=0;
				if(st[m][j]==st[n][i] && sw[j]==0)
				{
					sw[j]=1;
					ssw=1;
					break;
				}
			}
		}
	}

	if(i==strlen(st[n]) && ssw)
	{
		return 1;
	}
	return 0 ;
}

void main()
{
	int i,j,k;
	
	//ifstream f("454.in");
	cin.getline(st[0],1000);
	while(!st[0][0])
		cin.getline(st[0],1000);
	i=1;
	while(!cin.eof())
	{
		cin.getline(st[i++],1000);
	}
	for(j=0;j<i;j++)
	{
		for(k=j+1 ; k<i ; k++)
			if(check(j,k))
				cout<<st[j]<<" = "<<st[k]<<endl;

	}
//	cin>>i;
}

[Jan]

I think you r missing something. Try the following input output set. I think you will find your error.

Input:

Code: Select all

2

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

aaa
aaa
aaa

Output:

Code: Select all

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

aaa = aaa
aaa = aaa
aaa = aaa

Hope you will get Accepted.

[Jan]

Just check the input output...

Input:

Code: Select all

2

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

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

Output:

Code: Select all

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

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

Hope it works.

[Andisheh]

thank you!