10848 - Make Palindrome Checker

[dumb dan]

> if the 2

[[_TANG_]]

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


_______________
[_TANG_]

[jaracz]

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

[jaracz]

My God!!
I didn't check if strings are lowercase!!

[mysword]

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]

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]

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]

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]

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]

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]

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]

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.