353 - Pesky Palindromes

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

353 - AC, BUT...

Post by Dmytro Chernysh » Sat Jun 14, 2003 4:14 am

I got AC, but I spent too much memory - the worst one on the ranklist :-(
However, I see a lot of people got AC only with 64K. How???

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Post by LawrenceT » Sun Jun 15, 2003 6:49 pm

all you need is the original string, which should be a character array of size 81, and a array storing the avaliable start positions.

the way i do this question is to find all palindromes of length i, before moving on to find palindromes of length i + 1. It is easy to eliminate all duplicates just by keeping another boolean array the same length as the string.

hope this helps without spoiling the problem.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

353 - Pesky Palindromes

Post by miras » Mon Jan 05, 2004 2:06 pm

Hello ....

Tell me sth. what is the output for sth like that


BTW. this input can be not good (i don't know.,....))

Code: Select all

aAa
 AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA
A   A

my outpur...

Code: Select all

The string 'aAa' contains 3 palindromes.
The string 'A  A' contains 4 palindromes.



What do u think about it ???




___________________________________________
Regards MIras



:D

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

What about the other one?

Post by sohel » Mon Jan 05, 2004 2:17 pm

Your output seems to be correct for the two you have mentioned but what about the second case of your input. :-?

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Thu Jan 08, 2004 1:22 pm

hey what test are u thikking about... ?? :D

Corpse Fiend
New poster
Posts: 5
Joined: Wed Dec 17, 2003 6:18 pm
Location: Poland

Post by Corpse Fiend » Sat Jan 10, 2004 11:01 am

Question:
If I have only 1 palindrome as my output should I print:
1. The string 'a' contains 1 palindrome.
-or-
2. The string 'a' contains 1 palindromes.

BTW, if you can post here some complex tests I'd be grateful.
My programm gets WA, but I don't know what's wrong with it. All test cases that I was thinking about are going OK :cry: .

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

353 WA

Post by IRA » Wed Feb 08, 2006 1:00 am

Why WA!?
I can't find my bug...
Please help me to find the bug.
Thanks in advance!

Code: Select all

I got AC.

almorales
New poster
Posts: 2
Joined: Fri Oct 27, 2006 10:44 pm

353

Post by almorales » Sat Dec 02, 2006 1:16 am

I got CE but I don't know why. Would you help me ? This is my code:

#include <cstring.h>
#include <iostream.h>
char e[80];int cant_cads=0;
int piv_cadenitas=0;string cadenitas[3240];
bool Palindrome(char* a)
{
int b = (int)strlen(a);bool result;int c=0,d=b-1;
if (b == 1)
{result = true;}
else
{
if (b%2==0)
{
while ( c<d && a[c]==a[d])
{c++;d--;}
result = !(c < d);
}
else
{
while ( c!=d && a[c]==a[d])
{c++;d--;}
result = c == d;
}
}
return result;
}

bool Estaba(string str)
{
bool result;int i=0;
while (cadenitas!=str && i<piv_cadenitas)
{i++;}
if(i==piv_cadenitas)
{result=false;}
else
{result=true;}
return result;
}

void Principal()
{
int longi = (int)strlen(e)-1;
for (int i=0;i<=longi;i++)
for (int j=i;j<=longi;j++)
{
char* aux = new char[j-i+2];aux[j-i+1]=0;int piv_aux=0;
for (int z=i;z<=j;z++)
{aux[piv_aux++]=e[z];}
if (Palindrome(aux))
{
if (Estaba(aux)==false)
{
cant_cads++;
cadenitas[piv_cadenitas++]=(string)aux;
}
}
}
}
int main()
{
while (gets(e))
{
Principal();
printf(" The string '");
printf("%s",e);
printf("' contains ");
printf("%i",cant_cads);
printf(" palindromes.\n");
for (int m=0;m<(int)strlen(e);m++)
{e[m]=0;}
cant_cads=0;piv_cadenitas=0;
}
return 0;
}
//---------------------------------------------------------------------------

almorales
New poster
Posts: 2
Joined: Fri Oct 27, 2006 10:44 pm

Post by almorales » Sat Dec 02, 2006 1:22 am

test

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Sun Aug 26, 2007 10:35 pm

Miras, is your second case's output OK?

Code: Select all

A***A
your output is 4. But aren't there 5 palindromes?

Code: Select all

A
A***A
*
**
***
Though i'm getting WA :D
Can you please send me more test cases..??

Ashis, CSEDU

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Mon Aug 27, 2007 8:33 am

Miras's input:

Code: Select all

aAa 
 AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA 
A   A
My output: (yet getting WA):(

Code: Select all

The string 'aAa ' contains 4 palindromes.
The string ' AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA ' contains 28 palindromes.
The string 'A   A' contains 5 palindromes.

Is there anybody verify this? Can you give some more critical I/Os?

Ashis

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Mon Aug 27, 2007 8:38 am

My previous post was a mistake cause i copied Miras's input with mouse and pasted, so a trailing space character can be seen in my output. Now i've corrected the input, now my output is -

Code: Select all

The string 'aAa' contains 3 palindromes.
The string ' AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA' contains 28 palindromes.
The string 'A   A' contains 5 palindromes.

Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 28, 2007 2:28 pm

There are no spaces in the input file. However, you can post your code.
Ami ekhono shopno dekhi...
HomePage

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Wed Aug 29, 2007 5:57 am

Jan,
I'm getting WA in the following code. can you find bugs in my code? Can you give some test cases too.

Code: Select all

Removed after accepted.
Thanks.
Last edited by ashis.csedu on Thu Aug 30, 2007 8:09 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 29, 2007 6:52 pm

Ashis vai, it look a long time. Your code seems 99.99% correct. But just imagine that, a string with 80 characters are given, and is a palindrome. Then your code will fail. Guess why? You have used

Code: Select all

char temp[80];
Use 81 or more. Hope it helps. :D
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”