OJ Board

The Online Judge board
https://onlinejudge.org/board/

10848 - Make Palindrome Checker

https://onlinejudge.org/board/viewtopic.php?t=8102

Page 2 of 2

Posted: Thu May 12, 2005 4:53 pm
by dumb dan
> if the 2

Thnx

Posted: Thu May 12, 2005 5:08 pm
by [_TANG_]
Thnx dumb dan ... I got AC after that tip

:D
_______________
[_TANG_]

Posted: Sat Jun 04, 2005 10:34 pm
by 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

Posted: Wed Jun 08, 2005 6:29 pm
by jaracz
My God!!
I didn't check if strings are lowercase!!
;)

Posted: Sat Oct 15, 2005 3:31 pm
by 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;
}

Posted: Sat Dec 10, 2005 5:13 pm
by Martin Macko
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".

Posted: Thu Jul 13, 2006 5:14 am
by 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?

Could somebody help me...

Posted: Sat Nov 11, 2006 1:49 am
by 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;
}

Posted: Fri Jan 12, 2007 12:02 am
by 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!

Posted: Fri Jan 12, 2007 4:06 am
by 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

Posted: Wed May 02, 2007 3:32 pm
by 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);
	}
}

Re: 10848 - Make Palindrome Checker

Posted: Thu Mar 26, 2015 7:25 am
by 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.
All times are UTC+02:00
Page 2 of 2

Powered by phpBB® Forum Software © phpBB Limited