## 10848 - Make Palindrome Checker

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

Moderator: Board moderators

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
> if the 2

[_TANG_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

### Thnx

Thnx dumb dan ... I got AC after that tip

_______________
[_TANG_]

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
hi guys!!
I've read precisely all about this pro but i'm still gettin' WA

can anyone help me?

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define max 10000

int isdigits(char *a)
{
int len = strlen(a);
for(int i = 0; i < len; i++)
if(!isdigit(a[i]))return 0;
return 1;
}

int ispallin(char *a)
{
int len = strlen(a);
int mid = len/2;
for(int i = 0; i < mid; i++)
if(a[i] != a[len-1-i])return 0;
return 1;
}

int all_letters(char *a,char *b)
{
char sign;
int len = strlen(a),len2 = strlen(b);
for(int i = 0;i < len; i++)
{
sign = a[i];
if(!strchr(b,sign))return 0;
}
return 1;
}

int freq(char *a,char *b)
{
char pom[strlen(a)-1];
int len = strlen(a),len2 = strlen(b);
int licznik1,licznik2;
for(int i = 0; i < len; i++)
{
licznik1 = licznik2 = 0;
for(int j = 0; j < len; j++)
if(a[j] == a[i])licznik1++;
for(int j = 0; j < len2; j++)
if(b[j] == a[i])licznik2++;
if(licznik1 > licznik2)return 0;
}
return 1;
}

int made_out(char *a,char *b)
{
char sign;
int len = strlen(a),len2 = strlen(b);
for(int i = 0; i < len; i++)
{
sign = a[i];
for(int j = 0; j < len2; j++)
if(strchr(b,sign))
{
if(sign == b[j])
{
b[j] = ' ';
break;
}
}
else return 0;
}
return 1;
}

int value(char *a)
{
return atoi(a);
}

int main()
{
int AC;
char line[2*max];
char str1[max],str2[max],num[10];
while(gets(line))
{
int i = 0;
while(!isspace(line[i]))
{
str1[i] = line[i];
i++;
}
str1[i] = '\0';
i++;
int j = 0;
while(!isspace(line[i]))
{
num[j] = line[i];
i++;j++;
}
i++;
num[j] = '\0';
j = 0;
while(!isspace(line[i]) && line[i] != '\0')
{
str2[j] = line[i];
i++;j++;
}
str2[j] = '\0';
AC = 1;
if(!isdigits(num) || strlen(str1)>1000 || strlen(str2)>2000 ||
strlen(str1) + strlen(num) + strlen(str2) + 2 != strlen(line))
printf("FFFFFFF The solution is not accepted\n");
else
{
printf("T");
if(ispallin(str2))printf("T");
else
{
printf("F");
AC = 0;
}
if(all_letters(str1,str2))printf("T");
else
{
printf("F");
AC = 0;
}
if(freq(str1,str2))printf("T");
else
{
printf("F");
AC = 0;
}
if(made_out(str1,str2))printf("T");
else
{
printf("F");
AC = 0;
}
if(strlen(str1) + value(num) == strlen(str2))printf("T");
else
{
printf("F");
AC = 0;
}
if(value(num) < strlen(str1))printf("T ");
else
{
printf("F ");
AC = 0;
}
if(AC)printf("The solution is accepted\n");
else printf("The solution is not accepted\n");
}
}
return 0;
}    ``````
Thx in advance
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
My God!!
I didn't check if strings are lowercase!!
keep it real!

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am
can anyone help me?
I have paid attention to the tailing spaces and some cases other have said but still WA
I don't know where is wrong......

Code: Select all

``````#include<stdio.h>
#include<string.h>
char line[50000];
char s1[1001],s2[2001];
int main() {
int i,l1,l2,n,l,j;
bool p1;
int mark1[26],mark2[26];
bool p[7],ac;
do{
if (gets(line)==NULL)  break;
p1=true;
i=0;
l=strlen(line);
while(i<l && line[i]!=' ')i++;
if (i==l || i>1000) p1=false;
else {
//the first str
for (j=0;j<i;j++) {
s1[j]=line[j];
if (!(line[j]>='a' && line[j]<='z')) {
p1=false;
goto next;
}
}
s1[i]='\0';
l1=i;
i++;
if (line[i]<'0' || line[i]>'9') {
p1=false;
goto next;
}
//the number
n=0;
while(i<l && line[i]>='0' && line[i]<='9' && n<=1000) {
n=n*10+line[i]-'0';
i++;
}

if (i==l || n>1000 || line[i]!=' ') p1=false;
else {
i++;
if (i==l) {
l2=0;
s2[0]='\0';
goto next;
}
if (!(line[i]>='a' && line[i]<='z')) {
p1=false;
goto next;
}else {
//the second str
j=0;
while(i<l && line[i]>='a' && line[i]<='z' && j<=2000) s2[j++]=line[i++];
if (i!=l) p1=false;
else {
s2[j]='\0';
l2=j;
}
}
}
}
next:;
if (!p1) {
printf("FFFFFFF The solution is not accepted\n");
continue;
}
memset(p,true,sizeof p);
//2
for (i=0;i<l2/2;i++)
if (s2[i]!=s2[l2-i-1]) {
p[1]=false;
break;
}
//3
memset(mark1,0,sizeof mark1);
memset(mark2,0,sizeof mark2);
for (i=0;i<l2;i++) mark2[s2[i]-'a']++;
for (i=0;i<l1;i++)
if (mark2[s1[i]-'a']==0) {
p[2]=false;
break;
}
//4
for (i=0;i<l1;i++) mark1[s1[i]-'a']++;
for (i=0;i<26;i++) {
if (mark2[i]<mark1[i]) {
p[3]=false;
break;
}
}
//5
j=0;
for (i=0;i<l1;i++) {
while(j<l2 && s2[j]!=s1[i]) j++;
if (j==l2) {
p[4]=false;
break;
}
j++;
}
//6
if (l1+n!=l2) p[5]=false;
//7
if (n>=l1) p[6]=false;

ac=true;
for (i=0;i<7;i++)
if (!p[i]) ac=false;
for (i=0;i<7;i++)
if(p[i]) printf("T");
else printf("F");
if (ac) printf(" The solution is accepted\n");
else printf(" The solution is not accepted\n");
}while(1);
return 0;
}
``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
mysword wrote:can anyone help me?
I have paid attention to the tailing spaces and some cases other have said but still WA
I don't know where is wrong......
My AC answers "FFFFFFF" for " 2 aa". Your solution answers "TTTTTTF".

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada
This one is really frustrating.

I am guessing that there are no " 0 " or " 2 aa" types of inputs, because Martin's and mf's outputs contradict each other.

I really have no idea what I can be missing, I checked for all the things mentioned above :(

And for the check 5, I check if LCS length is the length of the first string, right?

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### Could somebody help me...

I've been checking all possible details in my code, but I keep on getting WA on this problem. I would be very thankful if someone could check out my code and make a suggestion... Thanks in advance.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_PROPERTIES (7)
#define MAX_STRING (5000)
#define STRING_1_SIZE (1000)
#define STRING_2_SIZE (2000)
#define LOWER_LIMIT (0)
#define UPPER_LIMIT (1000)

char first[MAX_STRING + 1];
char second[MAX_STRING + 1];
char number[MAX_STRING + 1];
unsigned lenFirst;
unsigned lenSecond;
unsigned lenNumber;
unsigned lenInput;
unsigned firstSet;
unsigned secondSet;

unsigned trimFeedline(char* str)
{
unsigned len = strlen(str);

if(str[len-1] == '\n')
{
str[len-1] = '\0';
return len - 1;
}
return len;
}

short isLower(char* str)
{
while(*str && islower(*str))
str++;

return (*str == '\0');
}

short isPositive(char* integer)
{
char* number = integer;
int value;
int size;

size = 0;
while(*integer && isdigit(*integer))
{
integer++;
size++;
}

if(*integer != '\0')
return 0;

if(size > 4)
return 0;

value = atoi(number);
return (value >= LOWER_LIMIT) && (value <= UPPER_LIMIT);
}

short getStrings(char* input)
{
int i;

i = 0;
while(*input && !isspace(*input))
first[i++] = *input++;
first[i] = '\0';

while(*input && isspace(*input))
input++;

i = 0;
while(*input && !isspace(*input))
number[i++] = *input++;
number[i] = '\0';

while(*input && isspace(*input))
input++;

i = 0;
while(*input && !isspace(*input))
second[i++] = *input++;
second[i] = '\0';

/*
printf("%s\n", first);
printf("%s\n", number);
printf("%s\n", second);
*/

return strlen(first) >= 0 && (strlen(number) > 0) && (strlen(second) >= 0);
}

short test_1()
{
char input[MAX_STRING + 2];
int totalLength;
int nstrings;

fgets(input, MAX_STRING + 1, stdin);
lenInput = trimFeedline(input);
nstrings = getStrings(input);
if(nstrings)
{
lenFirst = strlen(first);
lenSecond = strlen(second);
lenNumber = strlen(number);

if(isLower(first) && (lenFirst <= STRING_1_SIZE)
&& isLower(second) && (lenSecond <= STRING_2_SIZE)
&& isPositive(number))
{
totalLength = lenFirst + lenSecond + lenNumber + 2;
if(totalLength == lenInput)
return 1;
}
}
return 0;
}

short test_2()
{
int i, j;

for(i = 0, j = lenSecond - 1; i <= j; ++i, j--)
if(second[i] != second[j])
break;

return (i > j);
}

short test_3()
{
int i;

firstSet = 0;
secondSet = 0;

for(i = 0; i < lenFirst; ++i)
firstSet |= (1 <<  (first[i]-'a'));
for(i = 0; i < lenSecond; ++i)
secondSet |= (1 <<  (second[i]-'a'));

return ((firstSet & secondSet) == firstSet);
}

short test_4()
{
unsigned frequency1['z'-'a' + 1];
unsigned frequency2['z'-'a' + 1];
int i;
short passed = 1;

for(i = 0; i < 'z' - 'a' + 1; ++i)
frequency1[i] = frequency2[i] = 0;

for(i = 0; i < lenFirst; ++i)
frequency1[first[i]-'a']++;

for(i = 0; i < lenSecond; ++i)
frequency2[second[i]-'a']++;

for(i = 0; i < 'z' - 'a' + 1; ++i)
if(((1 << i) & secondSet) && frequency2[i] < frequency1[i])
{
passed = 0;
break;
}

return passed;
}

short test_5()
{
int i, j;

i = j = 0;
while(i < lenFirst && j < lenSecond)
{
if(first[i] == second[j])
{
i++;
j++;
}
else j++;
}

return i == lenFirst;
}

short test_6()
{
return lenFirst + atoi(number) == lenSecond;
}

short test_7()
{
return atoi(number) < lenFirst;
}

void resetProperties(short property[MAX_PROPERTIES])
{
int i;

for(i = 0; i < MAX_PROPERTIES; ++i)
property[i] = 0;
}

int main()
{
short property[MAX_PROPERTIES];
short (*tests[MAX_PROPERTIES])() = {test_1, test_2, test_3, test_4, test_5,
test_6, test_7};
int i;
short accepted;

while(!feof(stdin))
{
resetProperties(property);
accepted = 1;
first[0] = second[0] = number[0] = '\0';

property[0] = tests[0]();
if(property[0])
for(i = 1; i < MAX_PROPERTIES; ++i)
property[i] = tests[i]();

for(i = 0; i < MAX_PROPERTIES; ++i)
{
putchar(property[i] ? 'T' : 'F');
if(property[i] == 0)
accepted = 0;
}
printf(" The solution is %s\n", accepted ? "accepted" : "not accepted");
}
return 0;
}

``````

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I use:

Code: Select all

``````abcd 3 abcdcba
aaaa 3 abcdcba
abc 2 abdcba
aab b baab
abababaabababa 0 abababaabababa
pqrsabcdpqrs 9 pqrsabcdpqrqpdcbasrqp
a 0 aa
aa 0 aa
0
2 aa``````
and I get:

Code: Select all

``````TTTTTTT The solution is accepted
TTTFFTT The solution is not accepted
TFTTTFT The solution is not accepted
TTTTTFT The solution is not accepted
TTTTTTT The solution is accepted
TTTTTTT The solution is accepted
TTTTTFT The solution is not accepted
FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted
``````
any other tricky inputs? Thanks!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
For your input my accepted program outputs:

Code: Select all

``````TTTTTTT The solution is accepted
TTTFFTT The solution is not accepted
TFTTTFT The solution is not accepted
FFFFFFF The solution is not accepted
TTTTTTT The solution is accepted
TTTTTTT The solution is accepted
TTTTTFT The solution is not accepted
TTTTTTT The solution is accepted
FFFFFFF The solution is not accepted
TTTTTTF The solution is not accepted
``````

marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm
I am keeping WA for more than 10 times.

I have checked the conditions 2-7 to be right. The only condition 1 puzzled me.

What's the logic I should detect if the first string is empty?

Also, any critical inputs?

Below please find my codes.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MIN(i,j) (i<j?i:j)

int main()
{
int i, j, k, n;
int len, len1, len2, len3, result, app1[26], app2[26];
char *line, *s1, *s2, *s3, flag[8];

line = (char *) malloc(sizeof(char) * 5005);
s1 = (char *) malloc(sizeof(char) * 5005);
s2 = (char *) malloc(sizeof(char) * 5005);
s3 = (char *) malloc(sizeof(char) * 5005);

flag[7] = 0;

while(gets(line))
{
for(i = 0; i < 1000000; i++);
len = strlen(line);

j = sscanf(line, "%s%s%s", s1, s3, s2);
if(j < 2)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
else if(j == 2) s2[0] = 0;

len1 = strlen(s1);
len2 = strlen(s2);
len3 = strlen(s3);
if(len1 + len2 + len3 + 2 != len)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
if(len1 > 1000 || len2 > 2000)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
if(len3 == 0)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}

for(i = k = 0, j = -1; s3[i] != 0; i++)
{
if(s3[i] < '0' || s3[i] > '9')
{
k = 1;
break;
}
if(s3[i] != '0' && j == -1)
{
j = i;
}
}
if(k)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
if(j == -1) n = 0;
else if(len3 - j > 5)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
else
{
n = atoi(&(s3[j]));
if(n < 0 || n > 1000)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
}

/*
j = sscanf(s3, "%d", &n);
if(j == 0)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}

if(n < 0 || n > 1000)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
*/
k = MIN(len1, len2);
for(i = j = 0; i < k; i++)
{
if(s1[i] < 'a' || s1[i] > 'z')
{
j = 1;
break;
}
if(s2[i] < 'a' || s2[i] > 'z')
{
j = 1;
break;
}
}
if(j)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
for(i = k; i < len1; i++)
{
if(s1[i] < 'a' || s1[i] > 'z')
{
j = 1;
break;
}
}
if(j)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
for(i = k; i < len2; i++)
{
if(s2[i] < 'a' || s2[i] > 'z')
{
j = 1;
break;
}
}
if(j)
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
/*
printf("len1 = %d, len2 = %d, n = %d\n", len1, len2, n);
*/
result = 1;
memset(flag, 0, sizeof(flag));
flag[0] = ((len1 <= 1000 && len2 <= 2000 && n >= 0 && n <= 1000)?'T':'F');
if(flag[0] == 'F')
{
printf("FFFFFFF The solution is not accepted\n");
continue;
}
for(i = len2/2; i >= 0; i--)
{
if(s2[i] != s2[len2-1-i]) break;
}
flag[1] = (i < 0? 'T':'F');
result &= (flag[1] == 'T');
memset(app1, 0, sizeof(app1));
memset(app2, 0, sizeof(app2));
for(i = 0; i < k; i++)
{
app1[s1[i]-'a']++;
app2[s2[i]-'a']++;
}
for(i = k; i < len1; i++) app1[s1[i]-'a']++;
for(i = k; i < len2; i++) app2[s2[i]-'a']++;
flag[2] = flag[3] = 'T';
for(i = 0; i < 26; i++)
{
if(app1[i] && !app2[i])
if((flag[2] = 'F') && flag[3] == 'F') break;
if(app2[i] && app2[i] < app1[i])
if((flag[3] = 'F') && flag[2] == 'F') break;
}
result &= (flag[2] == 'T');
result &= (flag[3] == 'T');
for(i = j = 0; j < len2; j++)
{
if(s2[j] == s1[i])
{
if(++i == len1) break;
}
else if(len1-i > len2-j) break;
}
flag[4] = (i == len1? 'T':'F');
result &= (flag[4] == 'T');
flag[5] = (len2 == len1 + n? 'T': 'F');
result &= (flag[5] == 'T');
flag[6] = (len1 > n? 'T':'F');
result &= (flag[6] == 'T');

if(result) printf("TTTTTTT The solution is accepted\n");
else printf("%s The solution is not accepted\n", flag);
}
}

``````

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 10848 - Make Palindrome Checker

Just some more critical cases.
Input:

Code: Select all

``````
AB 1 ABA
a 1001 a

a 10b a``````
Output:

Code: Select all

``````FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted
FFFFFFF The solution is not accepted``````
The first case is 2 spaces and the fourth one is an empty line.
Life shouldn't be null.