195 - Anagram

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

Moderator: Board moderators

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

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

Post by 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
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

Post by 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
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Location: bangladesh
Contact:

195:why wrong answer?

Post by joshila21 »

[cpp] :oops:
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

oops

Post by 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.
:wink:

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

Post by wos »

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

joshila21
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Location: bangladesh
Contact:

Post by joshila21 »

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

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

195 OLE

Post by 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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by 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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx »

Try not use the same loop variable for different loops.

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

Post by rifter1818 »

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:

Post by 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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by 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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by 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
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

complier error c++ on 195

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

Post Reply

Return to “Volume 1 (100-199)”