146 - ID Codes

[jaracz]

next_permutation returns false when the current stan of container(string) is descending sorted
try to do this:

Code: Select all

while(gets(line) && strcmp(line,"#"))
{
    if(std::next_permutation(line,line+strlen(line)))
    printf("%s\n",line);
    else printf("No Successor\n");
}

and it's all

[ripon51]

Hey,
I use stl next_permutation and get answer.I think there are no scope to show wrong answer but it showed.Whats the problem.Please help me.
Ripon

[snar]

I've tried to solve this problem not once. I've got WA for this problem again. I just can't understand where I made a mistake. Someone, help me, please!


// 146 ID Codes
#include <iostream.h>
#include <string.h>
//using namespace std;
bool is_last(char* s)
{
int i;
for (i = 0; i < strlen(s) - 1; i++)
if (s < s[i + 1])
return 0;
return 1;
}
void main ()
{
int i, j, k, n;
char id_code[50], *mirror;
cin >> id_code;
while (id_code[0] != '#')
{
if(is_last(id_code))
cout << "No Successor"<< endl;
else
{
int n = strlen(id_code);
k = n - 2;
while (id_code[k + 1] <= id_code[k])
k--;
char min = id_code[k + 1];
int m = k + 1;
for (i = k; i < n; i++)
if (id_code > id_code[k] && id_code < min)
{
m = i;
min = id_code;
}
char letter = id_code[k];
id_code[k] = id_code[m];
id_code[m] = letter;

mirror = new char [n - k - 1];
m = 0;
for (i = n - 1; i > k; i--)
{
mirror[m] = id_code;
m++;
}

m = 0;
for (i = k + 1; i < n; i++)
{
id_code = mirror[m];
m++;
}

cout << id_code<< endl;

}
cin >> id_code;

}
}

[Salman]

Hi
There is function called next_permutation() at the STL library algorithm.h
You can use that. It is just a two line program.

Salman

[Cytoplasm]

Let me guess...
You are processing data after the #

[ripon51]

Dear cytoplasom,
Thanks for ur reply.But I can't understand what u say.Please explain.
Ripon

[Cytoplasm]

The entire file will be terminated by a line consisting of a single #.

When you get to the #, stop processing data.

output for:
"abaacb
cbbaa
#
abaacb"
is:
"ababac
No Successor"

[ripon51]

cytoplasom,
I understand.Its ok & accepted.Thanks
ripon

[heber]

[img][img]146 - ID Codes

Anybody can help me? which the problem with my program? I aways get wrong answer . I don't understand.

/* 146 - ID Codes*/

#include <stdio.h>

main()
{char cod[60],menor,aux;
int i,imenor,j,k,ehalfabetico,m,indice,n;

scanf("%s",cod);
while(strcmp(cod,"#")!=0){
ehalfabetico=0;

n=strlen(cod);
imenor=n-1;

for(i=n-1;i>=0;i--){

if(cod>cod[i-1])
ehalfabetico=1;


if((cod<=cod[imenor])&&(cod[i-1]<=cod[imenor]))
imenor=i;

if(cod>cod[i-1]){

for(m=i;m<n;m++)
if(cod[m]>cod[i-1]) {
imenor=m;break;}

for(m=i;m<n;m++)
if(cod[m]>cod[i-1])
if(cod[m]<cod[imenor])
imenor=m;

aux=cod[imenor];
cod[imenor]=cod[i-1];
cod[i-1]=aux;

j=n-1;
while(j>i){
indice=i;
for(k=i;k<=j;k++)
if(cod[k]>cod[indice])
indice=k;

aux=cod[indice];
cod[indice]=cod[j];
cod[j]=aux;
j=j-1; }
break;
}
}
if(ehalfabetico==1) {
printf("%s\n",cod);
}
else {
printf("No Successor\n");
}

scanf("%s",cod);
}

}

[the LA-Z-BOy]

Code: Select all

for(i=n-1;i>=0;i--){ 
  if(cod[i]>cod[i-1]) 
  ehalfabetico=1;
  ...
}

Carefully check this.... I think you should figure out what happens when i = 0.... if (cod[0]>cod[-1]) ... :O
This is not what you intended i suppos, so change the loops to for ( i = n-1; i > 0; --i) then it's fine.
PS.
1. Please when positing code... use the CODE TAG and post FORMATTED CODE.
2. Remove your code using EDIT if you've got Accepted.

[heber]

Thanks!!! I got Accepted!!!
But which test the program can to get Wrong Answer?

[the LA-Z-BOy]

Well, Well....
what would you expect if you run a code like if ( a[0] > a[-1]) or something ? Ask yourself as if you were a compiler you might have got a run time error on invalid memory referencing ...
the compiler behaviour is unexpected... that's the point..... so its not important at which case you are getting wrong answer.
cheers

[StanleY Yelnats]

There is function called next_permutation() at the STL library algorithm.h
You can use that. It is just a two line program.

what's the point?

[smilitude]

the point is simple, you dont have to write a complex program.
you can just use a function to print the next permutation.

[chilenocarreira]

Please, I've made several tests and my code looks ok. Can you post some critical tests for me ?? I'm trying to get AC for some days and I don't know why I'm getting WA.

Thanks,
Juliano