Page 8 of 17
Posted: Sat Jun 12, 2004 5:54 am
by angga888
Hi, samueljj
In this problem we must assume that 'A'<'a'<'B'<'b'.
Posted: Tue Jun 15, 2004 4:36 pm
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.
Posted: Mon Jul 05, 2004 11:20 am
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;
}
195:why wrong answer?
Posted: Tue Jul 06, 2004 12:11 pm
by 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]
oops
Posted: Tue Jul 06, 2004 1:16 pm
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.
Posted: Wed Jul 07, 2004 9:23 am
by wos
i solved it i didn't realise that sort() compares by ASCII codes
Posted: Sun Jul 11, 2004 11:08 pm
by joshila21
now i got "ACCEPTED"
i don't know how i missed it.
thanks for your help.
195 OLE
Posted: Mon Nov 01, 2004 6:57 am
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.
Posted: Mon Nov 01, 2004 8:21 am
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.
Posted: Mon Nov 01, 2004 8:25 am
by eg_frx
Try not use the same loop variable for different loops.
Posted: Mon Nov 01, 2004 5:14 pm
by rifter1818
Fixed the multiple uses of i (shouldnt that have thrown a compile error?) still getting OLE
Posted: Mon Nov 01, 2004 5:40 pm
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.
Posted: Wed Nov 03, 2004 2:03 pm
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.
Posted: Mon Nov 08, 2004 1:18 am
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]
complier error c++ on 195
Posted: Sun Feb 06, 2005 5:02 pm
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;
}