146 - ID Codes

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

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by 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
keep it real!

ripon51
New poster
Posts: 3
Joined: Sun Aug 28, 2005 7:08 am

problem 146 why wrong

Post by 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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

146 ID Codes - WA

Post by 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
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

146 ID Codes - WA

Post by 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
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

Post by Cytoplasm »

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

ripon51
New poster
Posts: 3
Joined: Sun Aug 28, 2005 7:08 am

can't understand

Post by ripon51 »

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

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

Post by 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
New poster
Posts: 3
Joined: Sun Aug 28, 2005 7:08 am

yes

Post by ripon51 »

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

heber
New poster
Posts: 2
Joined: Sat Jun 10, 2006 4:20 am

146 ID Codes

Post by 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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by 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.
Istiaque Ahmed [the LA-Z-BOy]

heber
New poster
Posts: 2
Joined: Sat Jun 10, 2006 4:20 am

Post by heber »

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

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by 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
Istiaque Ahmed [the LA-Z-BOy]

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by 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
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

the point is simple, you dont have to write a complex program.
you can just use a function to print the next permutation.
fahim
#include <smile.h>

chilenocarreira
New poster
Posts: 1
Joined: Mon Jun 18, 2007 8:02 am

Why WA ???

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

Post Reply

Return to “Volume 1 (100-199)”