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

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu May 12, 2005 4:53 pm

> if the 2

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

Thnx

Post by [_TANG_] » Thu May 12, 2005 5:08 pm

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

:D
_______________
[_TANG_]

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

Post by jaracz » Sat Jun 04, 2005 10:34 pm

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!

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

Post by jaracz » Wed Jun 08, 2005 6:29 pm

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

Post by mysword » Sat Oct 15, 2005 3:31 pm

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;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Dec 10, 2005 5:13 pm

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

Post by Darko » Thu Jul 13, 2006 5:14 am

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...

Post by zxul767 » Sat Nov 11, 2006 1:49 am

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:

Post by Larry » Fri Jan 12, 2007 12:02 am

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:

Post by mf » Fri Jan 12, 2007 4:06 am

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

Post by marthapfhui » Wed May 02, 2007 3:32 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

Post by dibery » Thu Mar 26, 2015 7:25 am

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.

Post Reply

Return to “Volume 108 (10800-10899)”