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

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

146 - ID Codes

Post by galois_godel »

who can give some sample input and sample output for problem 146
I can't find where go wrong in it?



var
s:string[50];
l,i,j,k:integer;
t:char;
procedure sort(m:integer);
var
r,k:integer;
temp:char;
begin
for r:=m to l do
begin
for k:=r+1 to l do
begin
if ord(s[r])>ord(s[k]) then
begin
temp:=s[r];
s[r]:=s[k];
s[k]:=temp;
end;
end;
end;
end;
begin
// Insert user code here
while not eof(input) do
begin
readln(s);
if s='#' then exit;
l:=length(s);
for k:=l downto 2 do
begin
if ord(s[k])>ord(s[k-1]) then break;
end;
if (k<=2)and(ord(s[2])<=ord(s[1])) then begin writeln('No Successor');end
else
begin
i:=k-1;
for k:=l downto i do
begin
if ord(s[k])>ord(s) then break;
end;
j:=k;
t:=s;
s:=s[j];
s[j]:=t;
sort(i+1);
writeln(s);
end;
end;
end.

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

146:WR why??

Post by galois_godel »

who can give some sample input and sample output for 146
program a146(input,output);
var
s:string[50];
l,i,j,k:integer;
t:char;
procedure sort(m:integer);
var
r,k:integer;
temp:char;
begin
for r:=m to l do
begin
for k:=r+1 to l do
begin
if ord(s[r])>ord(s[k]) then
begin
temp:=s[r];
s[r]:=s[k];
s[k]:=temp;
end;
end;
end;
end;
begin
// Insert user code here
while not eof(input) do
begin
readln(s);
if s='#' then exit;
l:=length(s);
for k:=l downto 2 do
begin
if ord(s[k])>ord(s[k-1]) then break;
end;
if (k<=2)and(ord(s[2])<=ord(s[1])) then begin writeln('No
Successor');end
else
begin
i:=k-1;
for k:=l downto i do
begin
if ord(s[k])>ord(s) then break;
end;
j:=k;
t:=s;
s:=s[j];
s[j]:=t;
sort(i+1);
writeln(s);
end;
end;
end.

visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands

Post by visser »

Try the following inputfile

cbbaa
a
a
#

output should be:

No Successor
No Successor
No Successor

but in your case I get a `Segmentation fault'

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

Thank you

Post by galois_godel »

Thank you

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

P 146(ID CODES) WA

Post by Red Scorpion »

HI, I Always GOT WA.
I try test case : CBABA, and my result is:
No succesor. I can't find the bug. Please help me...

This is my code :

:cry:
#include <stdio.h>
#include <string.h>
#define MAX 1000

char original[MAX], word[MAX], res[MAX];
int f_exit, flag, len;

void sort (char *str) {
int i,index;
char temp;

for (i=1; i<strlen(str); i++) {
index = i;
while (str[index] < str[index-1] && index>0) {
temp = str[index];
str[index] = str[index-1];
str[index-1] = temp;
index--;
}
}
}

void recurence(int index) {
int i;
char before;

if (index==len) {
if (!flag) flag=1;
else {
f_exit=1;
res[len] = '\x0';
printf ("%s\n", res);
}
}
else {
for (i=0; i<len && !f_exit; i++) {
if (!flag) {
if (original[index] == word[i]) {
before = word[i];
word[i] = '#';
res[index] = before;
recurence(index+1);
word[i] = before;
}
}
else {
if (word[i] != '#' && word[i] != before) {
res[index] = word[i];
word[i] = '#';
recurence(index+1);
}
}
}
}
}

int main() {
while (scanf ("%s", original)==1 && original[0] != '#') {
strcpy (word, original);
sort(word);
len = strlen(word); f_exit = 0; flag=0;
recurence(0);
if (!f_exit) printf ("No Successor\n");
}
return (0);
}
:cry:

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

input: CBABA
output should be "CBBAA" !

Mouquiette
New poster
Posts: 2
Joined: Sun Feb 02, 2003 9:34 pm

146 : WA ??

Post by Mouquiette »

I've done the 146 program but it say that I have a WA, and I don't know why .

Here are my input and my output file.If you know an input/output who can make some problems, can you give it to me.


Input :
abaacb
ddccbaa
coucou
gloups
sdqgsgh
l
AbnvfswV
jjonsf
#



Output :
ababac
No Successor
coucuo
glousp
sdqgshg
No Successor
AbnvfwVs
jjosfn



thanks

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Problem 146 (ID Codes) : WA, cannot figure out why

Post by RustB »

Has anyone else had similar trouble with 146? No matter what input I give while testing, I get the right answer. But the online judge returns "Wrong Answer".

This is what I've written.

Code: Select all

#include <stdio.h>
void swap(char *a, char *b) 
{
     char t=*a; 
	*a=*b;
	*b=t;
}
void printnext(char *a);
int main(void)
{
	char a[50];
	while(1)
	{
	     scanf("%s",a);
	     if(strcmp(a,"#")==0)
	     	return 0;
	     printnext(a);
	}
	return 0;
}
void printnext(char *a)
{
    	int i,j,k,n;
	n=strlen(a);
	j=n-2;
	while(a[j]>=a[j+1] && j>=0) j= j-1;
	if(j<0)
	{    printf("\nNo Successor");
		return;
	}
	k=n-1;
	while(a[j] > a[k]) k=k-1;
	swap(&a[j], &a[k]);
	i=n-1; k=j+1;
	while(i>=k)
	{	swap(&a[i],&a[k]);
		i--;k++;
	}
	printf("\n%s",a);
}
Can someone please tell me if the above code works?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

cxxoc --> occxx

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB »

Very sorry for bothering you all, But I fixed it :)

I changed while(a[j] > a[k]) k=k-1; to while(a[j] >= a[k]) k=k-1;

code#
New poster
Posts: 2
Joined: Sun Jul 04, 2004 3:04 am

146 Why WA? Help me plz~

Post by code# »

[java]
import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}

void Begin()
{
String line;
StringTokenizer idata;
char end = '#';
char input[];
int size, flag, point;

try
{
while ((line = Main.ReadLn(255)) != null)
{
if (line.charAt(0) == end)
break;
else
{
flag = 1;
point = 0;
size = line.length() - 1;
input = new char[size];
size--;

for (int i = 0; i <= size; i++)
input = line.charAt(i);

for (point = size-1 ; point >= 0; point--)
{
for (int i = size; i > point; i--)
{
if (input > input[point])
{
swap(input, i, point);
bubbleSort(input, point+1);
flag = 2;
break;
}
}
if (flag == 2)
break;
}
}
if (flag == 1)
System.out.println("No Successor");
else
System.out.println(input);
}
}
catch(Exception e) {System.out.println("error:" + e);}
}

void bubbleSort(char arr[], int p)
{
for (int i = p; i < arr.length-1; i++)
{
for (int j = i+1; j < arr.length; j++)
{
if (arr[j] < arr)
swap(arr, i, j);
}
}
}

void swap(char s[], int a, int b)
{
char temp = s[a];
s[a] = s;
s = temp;
}
}
[/java]

:x I don't understand that why WA.
:o Help me, Plz~~

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek »

your algorithm is wrong. try it on the input "aaccbb".
The correct answer is "ababcc", but I think yours will output
"acacbb".

Eug
New poster
Posts: 2
Joined: Thu Jul 15, 2004 7:33 pm
Location: Kazakhstan

146 - WA on standard algorithm?

Post by Eug »

class Main{
static String readLn(int maxLg){
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
try {
while(lg < maxLg){
car = System.in.read();
if((car == '#')||(car == '\n'))break;
lin[lg++] += car;
}
}
catch (Exception ex) {
return null;
}
if ((car == '#') && (lg == 0)) return null;
return (new String(lin,0,lg-1));
}

public static void main(String[] args){
Main m = new Main();
m.begin();
}

void begin(){
String no = "No Successor";
String input, next;
while ( (input = Main.readLn(255)) != null){
next = Main.nextPermutation(input);
if(next != null) System.out.println (next);
else System.out.println (no);
}
}

static String nextPermutation(String str){ //returns null if it does not exist
byte[] a = str.getBytes();
int n = a.length-1;
int j,k,r,s;
byte t;
j = n-1;
while (a[j]>=a[j+1]){
j--;
if(j == -1)return null;
}
k=n;
while (a[j]>=a[k])k--;
t = a[k];
a[k] = a[j];
a[j] = t;
r=n;
s=j+1;
t=0;
while (r>s){
t = a[r];
a[r] = a[s];
a[s] = t;
r--;
s++;
}
return new String(a,0,a.length);
}
}



Plz, take a look on it. Somehow Judge outputs WA. I cannot understand why.
Please help me.
:-? :-? :-? :-? :-?
All is the Vanity

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

146 - mine or next_permutation error?

Post by Jemerson »

Hi guys, im a noob C++ programmer but decided to use it just for the next_permutation() function of its library, so I can't really find my mistake, could anyone help me please?

Code: Select all

#include <algorithm>
#include <iostream>
#include <string.h>

using namespace std;

int main() {
    char s[50];
    cin >> s;
    while (s[0] != '#') {
          next_permutation(s, s+strlen(s));
          if (strcmp(s, s1) == -1) cout << "No Successor" << endl;
          else cout << s << endl;
          cin >> s;
    }
}
So.. Why am I getting WAs?
Last edited by Jemerson on Tue Jul 05, 2005 11:44 pm, edited 1 time in total.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson »

changed part of the above code and got acceptance

now:

Code: Select all

next_permutation(s, s+strlen(s), compare)

bool compare(char x, char y) { 
    if (x < y) 
        return true; 
    return false; 
}
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Post Reply

Return to “Volume 1 (100-199)”