## 195 - Anagram

Moderator: Board moderators

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Hi, samueljj
In this problem we must assume that 'A'<'a'<'B'<'b'.

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm
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
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am
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;
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
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Contact:

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

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

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

char x;
char s;
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### oops

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
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am
i solved it i didn't realise that sort() compares by ASCII codes joshila21
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Contact: now i got "ACCEPTED"
i don't know how i missed it.

rifter1818
New poster
Posts: 2
Joined: Mon Nov 01, 2004 6:52 am

### 195 OLE

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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm
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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm
Try not use the same loop variable for different loops.

rifter1818
New poster
Posts: 2
Joined: Mon Nov 01, 2004 6:52 am
Fixed the multiple uses of i (shouldnt that have thrown a compile error?) still getting OLE

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm
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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### complier error c++ on 195

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