195 - Anagram

[bundy]

yes I am using windows. I guess i missread the documentation. it is usually pretty good at telling me when something is not standard. Anyway i swtiched to the toupper and my compile errors are gone. Now I am timing out(seems to be a common problem for me lately).

Any idea what my code is messing up on?
[cpp]#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
//#include <malloc.h>
#include <ctype.h>

using namespace std;

string toString(vector<char> &data);
bool bSorted(string x, string y);
void printEntry(vector<string> &data);
string Upper(string s);

int main()
{

int numberOfWords = 0;
int count = 0;
vector<char> combo;
string input = "";
vector<string> output;


cin >> numberOfWords;

while (count++ < numberOfWords)
{
int i = 0;

combo.clear();
output.clear();
input = "";

cin >> input;

for (;i < input.size();i++)
combo.push_back(input);

sort(combo.begin(), combo.end());
output.push_back(toString(combo));

while(next_permutation(combo.begin(),combo.end()))
{
output.push_back(toString(combo));
}

sort(output.begin(),output.end(),bSorted);
printEntry(output);
}


return 0;
}

void printEntry(vector<string> &data)
{
for(int i = 0; i < data.size(); i++)
cout << data << endl;
return;
}

bool bSorted(string x, string y)
{
string xCap;
string yCap;

xCap = Upper(x);
yCap = Upper(y);

if (x == y)
{
//cout << "equal" << endl;
return true;
}
else
{
if ( xCap == yCap)
{

if (x < y)
{
// cout << "caps equal and x less than" << endl;
return true;
}
else
{
// cout << "caps equal and x greater than" << endl;
return false;
}
}
else
{
if (xCap < yCap)
{
// cout << "caps less than" << endl;
return true;
}
else
{
// cout << "caps greater than" << endl;
return false;
}

}
}

}

string Upper(string s)
{


string temp;

for (int i = 0; i < s.size(); i++)
{
temp += toupper(s);
}

//cout << "s = " << s << "\treturn = " << temp << endl;
return temp;
}
string toString(vector<char> &data)
{
string temp = "";
for (int i = 0; i < data.size();i++)
temp += data;
return temp;
}[/cpp]

[Rodrigo]

Weird...

I got AC without giving a damn about empty lines...

And your error was that you weren't treating them?

[galois_godel]

program a195;
var
alpha:array[0..57]of integer;
cnum:integer;
icase,l:integer;
s:string[100];
procedure getalpha;
var
i:integer;
begin
for i:=0 to 57 do
begin
alpha:=100;
if (i+65)<91 then alpha:=2*i;
if (i+65)>96 then alpha:=2*(i+65-97)+1;
end;
end;
procedure sort;
var
i,j:integer; t:char;
begin
for i:=1 to l do
begin
for j:=i+1 to l do
if alpha[ord(s)-65]>alpha[ord(s[j])-65] then
begin
t:=s;
s:=s[j];
s[j]:=t;
end;
end;
end;
function getord(c:char):integer;
begin
getord:=alpha[ord(c)-65];
end;
function getnext:boolean;
var
i,j,k:integer;
reb:boolean;
ch:char;
begin
reb:=true;
if l=1 then begin getnext:=false;exit;end;
for k:=l-1 downto 1 do
begin
if getord(s[k])<getord(s[k+1]) then break;
end;
if (k<=1)and(getord(s[1])>=getord(s[2]))then
begin getnext:=false;exit;end;
i:=k;
for k:=l downto 1 do
begin
if getord(s[k])>getord(s) then break;
end;
j:=k;
ch:=s;
s:=s[j];
s[j]:=ch;
for k:=i+1 to l do
for j:=k+1 to l do
if getord(s[k])>getord(s[j]) then
begin
ch:=s[k];
s[k]:=s[j];
s[j]:=ch;
end;
getnext:=reb;
end;



begin
// Insert user code here
getalpha;
readln(cnum);
for icase:=1 to cnum do
begin
readln(s);
if s=''then writeln('')
else begin
l:=length(s);
sort;
writeln(s);
while getnext do
begin
writeln(s);
end;
end;
end;

end.

[mmammel]

I have not been able to get my anagrams program to work correctly with the judge even though it works fine on my PC. Yes, I have the correct order AaBb. I think the problem is in reading the input: I use
char str1[80];
int nPuz, l1;

scanf("%d", &nPuz); /*read number of inputs*/

scanf("%s", str1);
l1=0; /* string length */
while (str1[l1]>64 && l1<79) l1++; /*count characters above ASCII 64 */

but I get time limit exceeded. I think my program is fast so I doubt it is timing out on the correct input. It is probably reading more than one string at a time. I added
if (l1>56) return 1;
and now I get runtime error after 0.010 seconds: Invalid memory reference
That seems like a strange error but it must mean it exited because l1>56 ?
..which means it is reading a very long string which would lead to the timeout.
I have tried scanf("%s\n", str1);
but that doesn't seem to help.

I have tried gets(str1) and it exits immediately.

Thanks,
Mark

[mmammel]

Oops, nevermind, I found the post that mentions that the string length can be almost 100...

[ec3_limz]

I do not understand your code. Can you use tags to format it so that it will be readable?

[Daniel Chia]

Correct me if i'm wrong but 195 has both upper case and lower case.
Your sort function ( or what i managed to make out ) only handles upper case letters

[tp]

Correct me if i'm wrong but 195 has both upper case and lower case.

Yes, case matters in this problem. The correct sequence goes as AaBbCc..... and so forth.

[cym]

I don't know why I got OLE...
can anyone help me??

Code: Select all

#include<stdio.h>
#include<string.h>
#include<ctype.h>
void main(void)
{
 int i,j,c,temp;
 char s[5000],t;
 void perm(char a[5000],int k,int n);
 while(scanf("%d",&c)!=-1 && c>0)
 {
 
  for(temp=1;temp<=c;temp++)
  {
   scanf("%s",s);
   for(i=strlen(s);i>0;i--)
	   for(j=0;j<i-1;j++)
	   {
	    if(tolower(s[j])>tolower(s[j+1]))
		{
		 t=s[j];
		 s[j]=s[j+1];
		 s[j+1]=t;
		}
		else
		{
		 if(s[j]>s[j+1] && tolower(s[j])==tolower(s[j+1]))
		 {
		  t=s[j];
		  s[j]=s[j+1];
		  s[j+1]=t;
		 }
		}
	   }
   perm(s,0,strlen(s)-1);
  }
 }
}

void perm(char a[5000],int k,int n)
{
 int i,j;
 char t;
 if(k==n)
 {
  for(i=0;i<=n;i++)
	  printf("%c",a[i]);
  printf("\n");
 }
 else
 {
  for(i=k;i<=n;i++)
  {
   if(a[i]!=a[i+1])
   {
    t=a[i];
	for(j=i;j>k;j--)
		a[j]=a[j-1];
    a[k]=t;
    perm(a,k+1,n);
    t=a[k];
    for(j=k;j<i;j++)
		a[j]=a[j+1];
    a[i]=t;
   }
  }
 }
}

[Balon]

first , you should format your code more readable before you submit it, then you'll get more help from others.
I think your code here
[cpp]for(i=k;i<=n;i++)
{
if(a!=a[i+1])
{
t=a;
for(j=i;j>k;j--)
a[j]=a[j-1];
a[k]=t;
perm(a,k+1,n);
t=a[k];
for(j=k;j<i;j++)
a[j]=a[j+1];
a=t;
}
} [/cpp]
may should be
[cpp]
for(i=k;i<=n;i++)
{
if(a!=a[i+1])
{
t=a[i+1];
for(j=i+1;j>k;j--)
a[j]=a[j-1];
a[k]=t;
perm(a,k+1,n);
t=a[k];
for(j=k;j<i+1;j++)
a[j]=a[j+1];
a=t;
}
}

[/cpp]
wish you a good luck

[cym]

sorry, i tried what you said, Balon
but it failed.
you can try the input "aAb", and see what happened.

thx anyway

[Dominik Michniewski]

try to use permutation algorithm from Knuth or

Code: Select all

next_perm()

in C++ (It in <algorithm> is placed I think) (if I corrct remember its name )

Dominik

[Sword Coast]

I don't see any error in your code! It seems very good.
But i didn't understand why you put the string so huge.
I got accepted with a string with length 100.
Another thing that is good to change is your loop to write this huge string.
Put: char a[100], and change this code:

Code: Select all

if(k==n)
{
  for(i=0;i<=n;i++)
     printf("%c",a[i]);
  printf("\n");
}

to:

Code: Select all

  if(k==n){
    a[k+1]='\0';
    printf("%s\n",a);
  }

it would be much more faster. Try this. Good luck.

[deddy one]

pls help

I got WA on 195, but I got acc on 10098.
I think that basicly it's just the same problem.

is there any trick on dealing with 195 here?

[Red Scorpion]

Think about the order :
Ascending order : A-a-B-b-C-c-D-d-...
So :
Aac
ABc
.
.

Sample Input:
3
AaAab
bBCca
ccaAaC

Sample Output:
AAaab
AAaba
AAbaa
AaAab
AaAba
AaaAb
AaabA
AabAa
AabaA
AbAaa
AbaAa
AbaaA
aAAab
aAAba
aAaAb
aAabA
aAbAa
aAbaA
aaAAb
aaAbA
aabAA
abAAa
abAaA
abaAA
bAAaa
bAaAa
bAaaA
baAAa
baAaA
baaAA
aBbCc
aBbcC
aBCbc
aBCcb
aBcbC
aBcCb
abBCc
abBcC
abCBc
abCcB
abcBC
abcCB
aCBbc
aCBcb
aCbBc
aCbcB
aCcBb
aCcbB
acBbC
acBCb
acbBC
acbCB
acCBb
acCbB
BabCc
BabcC
BaCbc
BaCcb
BacbC
BacCb
BbaCc
BbacC
BbCac
BbCca
BbcaC
BbcCa
BCabc
BCacb
BCbac
BCbca
BCcab
BCcba
BcabC
BcaCb
BcbaC
BcbCa
BcCab
BcCba
baBCc
baBcC
baCBc
baCcB
bacBC
bacCB
bBaCc
bBacC
bBCac
bBCca
bBcaC
bBcCa
bCaBc
bCacB
bCBac
bCBca
bCcaB
bCcBa
bcaBC
bcaCB
bcBaC
bcBCa
bcCaB
bcCBa
CaBbc
CaBcb
CabBc
CabcB
CacBb
CacbB
CBabc
CBacb
CBbac
CBbca
CBcab
CBcba
CbaBc
CbacB
CbBac
CbBca
CbcaB
CbcBa
CcaBb
CcabB
CcBab
CcBba
CcbaB
CcbBa
caBbC
caBCb
cabBC
cabCB
caCBb
caCbB
cBabC
cBaCb
cBbaC
cBbCa
cBCab
cBCba
cbaBC
cbaCB
cbBaC
cbBCa
cbCaB
cbCBa
cCaBb
cCabB
cCBab
cCBba
cCbaB
cCbBa
AaaCcc
AaacCc
AaaccC
AaCacc
AaCcac
AaCcca
AacaCc
AacacC
AacCac
AacCca
AaccaC
AaccCa
ACaacc
ACacac
ACacca
ACcaac
ACcaca
ACccaa
AcaaCc
AcaacC
AcaCac
AcaCca
AcacaC
AcacCa
AcCaac
AcCaca
AcCcaa
AccaaC
AccaCa
AccCaa
aAaCcc
aAacCc
aAaccC
aACacc
aACcac
aACcca
aAcaCc
aAcacC
aAcCac
aAcCca
aAccaC
aAccCa
aaACcc
aaAcCc
aaAccC
aaCAcc
aaCcAc
aaCccA
aacACc
aacAcC
aacCAc
aacCcA
aaccAC
aaccCA
aCAacc
aCAcac
aCAcca
aCaAcc
aCacAc
aCaccA
aCcAac
aCcAca
aCcaAc
aCcacA
aCccAa
aCccaA
acAaCc
acAacC
acACac
acACca
acAcaC
acAcCa
acaACc
acaAcC
acaCAc
acaCcA
acacAC
acacCA
acCAac
acCAca
acCaAc
acCacA
acCcAa
acCcaA
accAaC
accACa
accaAC
accaCA
accCAa
accCaA
CAaacc
CAacac
CAacca
CAcaac
CAcaca
CAccaa
CaAacc
CaAcac
CaAcca
CaaAcc
CaacAc
CaaccA
CacAac
CacAca
CacaAc
CacacA
CaccAa
CaccaA
CcAaac
CcAaca
CcAcaa
CcaAac
CcaAca
CcaaAc
CcaacA
CcacAa
CcacaA
CccAaa
CccaAa
CccaaA
cAaaCc
cAaacC
cAaCac
cAaCca
cAacaC
cAacCa
cACaac
cACaca
cACcaa
cAcaaC
cAcaCa
cAcCaa
caAaCc
caAacC
caACac
caACca
caAcaC
caAcCa
caaACc
caaAcC
caaCAc
caaCcA
caacAC
caacCA
caCAac
caCAca
caCaAc
caCacA
caCcAa
caCcaA
cacAaC
cacACa
cacaAC
cacaCA
cacCAa
cacCaA
cCAaac
cCAaca
cCAcaa
cCaAac
cCaAca
cCaaAc
cCaacA
cCacAa
cCacaA
cCcAaa
cCcaAa
cCcaaA
ccAaaC
ccAaCa
ccACaa
ccaAaC
ccaACa
ccaaAC
ccaaCA
ccaCAa
ccaCaA
ccCAaa
ccCaAa
ccCaaA

Good Luck.
Red Scorpion.