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

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy » Wed Jul 24, 2002 7:17 pm

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
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:

Post by Rodrigo » Wed Jul 24, 2002 8:01 pm

Weird...

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

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

galois_godel
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

195 WR?why?(or u can give me some sample input and output)

Post by galois_godel » Tue Aug 13, 2002 3:59 pm

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
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

Post by mmammel » Thu Aug 29, 2002 2:32 am

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
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

Post by mmammel » Thu Aug 29, 2002 1:57 pm

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

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz » Wed Sep 04, 2002 7:09 pm

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

Daniel Chia
New poster
Posts: 12
Joined: Mon Jul 29, 2002 3:04 pm
Contact:

Post by Daniel Chia » Fri Oct 04, 2002 2:28 pm

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
New poster
Posts: 4
Joined: Sun Feb 03, 2002 2:00 am

#195

Post by tp » Sun Oct 06, 2002 11:07 pm

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
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

195.....Output Limit Exceed....

Post by cym » Mon Nov 18, 2002 1:30 pm

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
New poster
Posts: 8
Joined: Tue Nov 26, 2002 6:00 am

Post by Balon » Tue Nov 26, 2002 3:53 pm

first , you should format your code more readable before you submit it, then you'll get more help from others. :o
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 :D

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

....

Post by cym » Wed Nov 27, 2002 3:52 am

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

thx anyway

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Nov 27, 2002 9:12 am

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
New poster
Posts: 2
Joined: Sun Jan 05, 2003 9:01 pm

Post by Sword Coast » Mon Jan 06, 2003 5:30 am

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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

why WA on 195 but got AC on 10098

Post by deddy one » Fri Feb 14, 2003 8:25 pm

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? :roll:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Sat Feb 15, 2003 8:16 am

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. :lol:

Post Reply

Return to “Volume 1 (100-199)”