401 - Palindromes

[Algoritmo]

Alun, you checked for mirroring and palindroming, both things at the same time. I think it's easier if you check independently:

[cpp]int Len = strlen(S);
bool IsPal = true, IsMir = true;
for (int i = 0; i < Len; i++) {
char C = S;
char Op = S[Len-1-i];
if (C != Op) IsPal = false;
if (C != Rev(Op)) IsMir = false;
}
[/cpp]
One thing that bored me about this problem is this sentence:

"A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string."

This sentence is ambuguous. What if it does not have a reverse? Should I not replace that character, should I replace it with blank space or all characters must have an reverse for that input to be mirrored?
The sample input does not answer my question, but I discovered the answer by sending mutiple codes until I got Accepted.
I replaced characters that didn't have a reverse with blank space.

[Jewel of DIU]

Here is my code for prob 401, It causes WA.
[c]
#===========#
CUT AFTER AC
#===========#
[/c]

[sohel]

Reversing V yields V and not U.

A part of your code
[c]
rev['T'] = 'T';
rev['U'] = 'U';
rev['V'] = 'U';
[/c]

Hope you can see the mistake...

[Jewel of DIU]

Now I have got AC .
Thank you Sohel Bhai.

[RustB]

This seems too simple to give this much trouble
Can anyone see what the problem is?

Code: Select all

#include <stdio.h>
char rev[40]="01SE0Z0080A000300HIL0JM0O0002TUVWXY5";
int ispalin(char *x, int n)
{
	int i;
	for(i=0;i<n;i++)
	     if(x[i] != x[n-i-1])
	     	return 0;
	return 1;
}
int ismirror(char *x, int n)
{
	int i,flag=0;
     for(i=n/2;i<n;i++)
    	     if(isalpha(x[i]))
    	     	if(rev[x[i]-'A'+10]!=0)
    	     	{
    	     	    	x[i]=rev[x[i]-'A'+10];
    	     	    	flag=1;
    	     	}
    	     else
    	     	if(rev[x[i]])
    	     	{
    	     	   	x[i]=rev[x[i]];
    	     	   	flag=1;
    	     	}

	if(!flag) return 0;

    	for(i=0;i<n;i++)
    	     if(x[i] != x[n-i-1])
    	     	return 0;
	return 1;
}
int main(void)
{
	char inp[25],xinp[25];
	while(!feof(stdin))
	{
	     int isp,ism,n;
	     scanf("%s",inp);
		n=strlen(inp);
		strcpy(xinp,inp);
	     isp=ispalin(xinp,n);
	     ism=ismirror(xinp,n);
	     if(!isp && !ism)
	     	printf("%s -- is not a palindrome.\n\n",inp);
	     else if(isp && !ism)
	     	printf("%s -- is a regular palindrome.\n\n",inp);
	     else if(!isp && ism)
	     	printf("%s -- is a mirrored string.\n\n",inp);
	     else
	     	printf("%s -- is a mirrored palindrome.\n\n",xinp);
	}
	return 0;
}

[sohel]

Consider these inputs and outputs..

input
[c]
B
E
[/c]

your program outputs
[c]
0 -- is a mirrored palindrome.

3 -- is a mirrored palindrome.
[/c]

Hope you can find your mistake and rectify it.

[RustB]

Okay... Thanks for that. I made some stupid assumptions about ASCII conversions :/ But I have a different set of problems now. I suppose I have to sort this out the hard way :/

Thanks anyway

[RustB]

I still don't understand. This is my test data

Code: Select all

NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA
MAIAM
123ESI
123ES1
DEO3D
9339
A
B
E
M
1
3
2
4

Output is:

Code: Select all

NOTAPALINDROME -- is not a palindrome.
ISAPALINILAPASI -- is a regular palindrome.
2A3MEAS -- is a mirrored string.
ATOYOTA -- is a mirrored palindrome.
MAIAM -- is a mirrored palindrome.
123ESI -- is not a palindrome.
123ES1 -- is a mirrored string.
DEO3D -- is a mirrored string.
9339 -- is a regular palindrome.
A -- is a mirrored palindrome.
B -- is a regular palindrome.
E -- is a mirrored palindrome.
M -- is a mirrored palindrome.
1 -- is a mirrored palindrome.
3 -- is a mirrored palindrome.
2 -- is a mirrored palindrome.
4 -- is a regular palindrome.

Is everything correct? Why do I still get a WA? Please help me
Edit: The formatting is correct in the actual output

[sohel]

By giving a quick glance I see that the output for

E

is not correct.

E is a palindrome - right.... but its not a mirrored one.

So I think the output should be

E -- is a regular palindrome.

[RustB]

I changed that, but it's still not accepted

[jagadish]

i lost my AC code for this one ..anyway consider these inputs

2S2
SS22
output:

222 -- is a mirror.... // original string is changed
SS22 -- is not a palindrome // must be mirrored string

[RustB]

This is my modified code

Code: Select all

#include <stdio.h>
char rev[40]="01SE0Z0080A000300HIL0JM0O0002TUVWXY5";
int ispalin(char *x, int n)
{
	int i;
	for(i=0;i<n;i++)
	     if(x[i] != x[n-i-1])
	     	return 0;
	return 1;
}
int ismirror(char *x, int n)
{
	int i,flag=0;
	if(n<2) return 0;
     for(i=n/2;i<n;i++)
    	     if(isalpha(x[i]))
    	     {
    	     	if(rev[x[i]-'A'+10]!='0')
    	     	{
				x[i]=rev[x[i]-'A'+10];
    	     	    	flag=1;
    	     	}
    	     }
    	     else
    	     {
    	     	if(rev[x[i]-'0']!= '0')
    	     	{
				x[i]=rev[x[i]-'0'];
    	     	   	flag=1;
    	     	}
    	     }

	if(!flag) return 0;
    	for(i=0;i<n;i++)
    	     if(x[i] != x[n-i-1])
    	     	return 0;
	return 1;
}
int main(void)
{
	char inp[25],xinp[25];
	int i;
	while(1)
	{
	     int isp,ism,n;
	     fgets(inp,sizeof(inp),stdin);
		n=strlen(inp);
		inp[n-1]='\0';
		n--;
		if(strcmp(inp,"")==0) break;
		strcpy(xinp,inp);
	     isp=ispalin(xinp,n);
	     ism=ismirror(xinp,n);
	     if(!isp && !ism)
	     	printf("%s -- is not a palindrome.\n\n",inp);
	     else if(isp && !ism)
	     	printf("%s -- is a regular palindrome.\n\n",inp);
	     else if(!isp && ism)
	     	printf("%s -- is a mirrored string.\n\n",inp);
	     else
	     	printf("%s -- is a mirrored palindrome.\n\n",inp);
	}
	return 0;
}

The OJ says it gets a wrong answer.
It gives the correct answer for your inputs jagadish

[jagadish]

since sohel told pointed out that program is not working for B ,E you
probably added this line [c] if(n<2) return 0; [/c] to fix it ,now it doesnt work for 8 ! ..its an easy program you need to test properly

btw i re-wrote the solution if u still get WA i can send that ..

[RustB]

For 8 I'm getting
8 -- is a regular palindrome

What's wrong with that?

[sohel]

8 is a mirrored palindrome.. I think.