195 - Anagram

[angga888]

Hi, samueljj
In this problem we must assume that 'A'<'a'<'B'<'b'.

[nibbler]

Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z.

it is very dumb ( of them ) if they put :;!"#()=/ in input.

i got AC by only reading input with scanf(), so it means that they didn't use this stuff alfter all.

[wos]

Can someone please help me here, I don't know what is wrong in my program. I tryed all test cases I could think of, and everything works, but when i post it i get WA. Here is my program:

Code: Select all

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
 int n;
 char str[1000];
 scanf("%i", &n);
 for (int i = 0; i < n; i++)
 {
  scanf("%s", str);  
  int strLen = strlen(str);
  sort(str, str + strLen);
  do
  {
   printf("%s\n", str);
  } while (next_permutation(str, str + strLen));
 }
 return 0;
}

[joshila21]

[cpp]
i submited the following code several times and tried with several inputs.
all were OK! to me.don't hnow where is the mistake.
the same code works for 10098.
please can anyone help me?

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

void cmp(int,int);
int check(char,int,int);
long fact(long);

char x[10000];
char s[10000];
long strlen_;

int main ()
{
int e,i,j,k,n,temp;
scanf("%d",&n);
for(e=0;e<n;e++)
{
scanf("%s",x);
strlen_=strlen(x);
for(j=0;j<strlen_-1;j++)
for(k=j+1;k<strlen_;k++)
if(x[j]>x[k])
{
temp=x[j];
x[j]=x[k];
x[k]=temp;
}
cmp(0,strlen_);
}
return 0;
}
void cmp(int k,int n)
{
int i,j,q,t;
char p;
for(i=0;i<n;i++)
{
q=0;t=i;p=x;
while(t>-1 && x[t--]==p)q++;
if(check(x,k,q))
{
s[k]=x;
if(k==n-1)
{
s[k+1]=NULL;
printf("%s\n",s);
}
else
cmp(k+1,n);
}
}
}
int check(char c,int k,int fre)
{
int i,t=0;
for(i=0;i<k;i++)
if(c==s)t++;
if(fre-t!=1)return 0;
return 1;
}[/cpp]

[sohel]

Here is a line from the problem statement:

The words generated from the same input word should be output in alphabetically ascending order

So this problem is not identical to 10098.

The above quote implies that the characters are listed in this order:
AaBbCcDdEe................

and not
ABCDE.................abcde

Hope you can see the difference.

[wos]

i solved it i didn't realise that sort() compares by ASCII codes

[joshila21]

now i got "ACCEPTED"
i don't know how i missed it.
thanks for your help.

[rifter1818]

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
struct HCAR{
	char T;
	HCAR(){}
	HCAR(char n){T = n;}
};
bool operator<(const HCAR& a,const HCAR& b)
{
	if(a.T >= 'A' && a.T <= 'Z')
	{
		if(b.T >= 'A' && b.T <= 'Z')
			return a.T<b.T;
		else
			return true;
	}
	if(b.T >= 'A' && b.T <= 'Z')
		return false;
	else
		return a.T<b.T;
}
int main()
{
	int n;
	cin >> n;
	string s;
	vector<HCAR> S;
	for(int i = 0;i<n;i++)
	{
		getline(cin,s);
		for(int i=0;i<s.length();i++)
			if((s[i]>='A' && s[i]<='Z')||(s[i]>='a'&&s[i]<='z'))
				S.push_back(HCAR(s[i]));
		sort(S.begin(),S.end());
		do{
			for(int iter = 0;iter<S.size();++iter)
				cout << S[iter].T;
			cout << endl;
		}while(next_permutation(S.begin(),S.end()));
	}
}

apparantly its spitting out more than asked for i keep getting OLE (i put on the if statement when translating from chars to "HCARS" but to no avail, any help would be apperciated.

[eg_frx]

Am still looking at your code, but before I give you any concrete answers, there are several points I'd like to suggest.

1. You don't need that sctruct to do the stuff.
you may only implement and bool function that takes two chars and specify it when you use next_permutation.

2. STL function can not only be used on STL classes. You may simply use a simple array.

[eg_frx]

Try not use the same loop variable for different loops.

[rifter1818]

Fixed the multiple uses of i (shouldnt that have thrown a compile error?) still getting OLE

[Zuza]

There's no compile error becouse the i's are in different scopes, thus the i in the first loop doesn't clash with the second i. Think about it as a function. The local variables do not clash with the globals so you can adress the outer scope with the scope operator ( :: ).
BTW, you can be assured that the input will be valid.

[eg_frx]

Sorry. Don't know exactly what's happening.

Anyway, even if it did work, it would still genrate wrong answer.

According to the problem discription characters are ordered alphabetically, which means a < D < d.

Your operator will not generate correct result.

In fact, your operator is not much different from the built in one.

[Antonio Ocampo]

Hi wos

I just changed this part of code

[cpp]
sort(str, str + strLen);
...
while (next_permutation(str, str + strLen));
[/cpp]

by this

[cpp]
sort(str, str + strLen,compare);
...
while (next_permutation(str, str + strLen,compare));
[/cpp]


and I got AC

My function compare is :

[cpp]
bool compare(char x, char y)
{
if( value(x)<value(y) )
return true;

return false;
}


int value(char x)
{
//In this problem 'A'<'a'<'B'<'b'.

if( isupper(x) )
return ( ((x-'A')<<1)-1 );

return ( (x-'a')<<1 );
}
[/cpp]

[sklitzz]

The program compiles on my computer just fine without any warnings but I get
Compilation error ehen I submit:

Code: Select all

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

int N;
set < string > perms;
typedef set < string >::iterator SIT;

int main()
{
	scanf( "%d", &N );
	for( int i = 0; i < N; ++i )
	{
		string t; cin >> t;

                //generate perms
		sort( t.begin(), t.end() );
		do
		{
			perms.insert( t );
		} while( next_permutation( t.begin(), t.end() ) );
		
		//output perms
		for( SIT it = perms.begin(); it != perms.end(); ++it  )
			cout << *it << endl;
		perms.clear();
	}
	
	return 0;
}