11103 - WFF 'N PROOF

[coolguy]

hi everybody ,
i dont understand what the problem statements says . it seems a similiar problem of 11108 ( Tautology ) . but i dont understand either of them . so can anyone please tell me what the problem asks for ........
waiting to be helped ................
bye bye

[helloneo]

Only thing you need to do is to find the longest WFF which can be made with given characters..
You don't need to warry about the table of definition of K A N C E for this problem..

And another thing..
If you change the title of this post to "11103 WFF 'N PROOF", it will look better..

[coolguy]

thanx for the reply . could you please explain the sample input output please . i means how "qKpNq" results "KqNq" .....
waiting to be helped
bye bye

[helloneo]

thanx for the reply . could you please explain the sample input output please . i means how "qKpNq" results "KqNq" .....
waiting to be helped
bye bye

The problem is to make a longest WFF with given charaters..

q is a WFF by the statement (p, q, r, s, and t are WFFs)
so, N(q) is also a WFF by this statement (if w is a WFF, Nw is a WFF)
so, K(q)(Nq) is also a WFF by this statement (if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs)

We can't make a longer WFF than KqNq with given characters so it's the answer..

Of course there could be many solutions..
You can print just one of them..

Good luck..~

[Kallol]

I got WA with this code , but it seems OK to me..... can anyone check it?
here is the code

Code: Select all

#include<stdio.h>
#include<string.h>
#include<memory.h>

#define NULL 0

char s[130];
bool b[130];
bool flag;
class node
{
public:
	node* left;
	node* right;
	char val;
	node()
	{
		left=NULL;
		right=NULL;
		val=0;
	}
	
};

int numOfSmall()
{
	int i,count=0;
	i=0;
	while(s[i])
	{
		if(s[i]>='a' && s[i]<='z')
		{
			count++;
		}
		i++;
	}
	return count;
}

int numOfRoot()
{
	int i=0,count=0;
	while(s[i])
	{
		if(s[i]=='K' || s[i]=='A' || s[i]=='E' || s[i]=='C')
		{
			count++;
		}
		i++;
	}
	return count;
}

int numOfN()
{
	int i,count=0;
	i=0;
	while(s[i])
	{
		if(s[i]=='N')
		{
			count++;
		}
		i++;
	}
	return count;
}

node* constructTree()
{
	int i;
	node* n=new node();
	for(i=0;s[i];i++)
	{
		if(b[i]==true && (s[i]=='K' || s[i]=='A' || s[i]=='E' || s[i]=='C'))
		{
			n->val=s[i];
			b[i]=false;
			n->left=constructTree();
			n->right=constructTree();
			return n;			
		}
	}
	for(i=0;s[i];i++)
	{
		if(b[i]==true && s[i]>='a' && s[i]<='z')
		{
			n->val=s[i];
			b[i]=false;
			n->left=NULL;
			n->right=NULL;
			return n;			
		}
	}
	flag=false;
	return NULL;
}

node* makeRoot()
{
	int i;
	node* n=new node();
	for(i=0;s[i];i++)
	{
		if(b[i]==true && (s[i]=='K' || s[i]=='A' || s[i]=='E' || s[i]=='C'))
		{
			n->val=s[i];
			b[i]=false;
			n->left=constructTree();
			n->right=constructTree();
			return n;
		}
	}
	return n;
}

void print(node* n)
{
	if(n==NULL)
	{
		return;
	}
	printf("%c",n->val);
	print(n->right);
	print(n->left);

	return;
}

int main(void)
{
	int i,N;
	while(1)
	{
		gets(s);
		if(strcmp(s,"0")==0)
		{
			break;
		}
		if(numOfRoot()==0)
		{
			if(numOfSmall()!=1)
			{
				printf("no WFF possible\n");
				continue;
			}
			else
			{
				N=numOfN();
				for(i=0;i<N;i++)
				{
					printf("N");
				}
				for(i=0;s[i];i++)
				{
					if(s[i]>='a' && s[i]<='z')
					{
						printf("%c",s[i]);
					}
				}
				printf("\n");
				continue;
			}
		}
		memset(b,true,sizeof(b));
		flag=true;
		node* n=makeRoot();
		if(!flag)
		{
			printf("no WFF possible\n");
			continue;
		}
		N=numOfN();
		for(i=0;i<N;i++)
		{
			printf("N");
		}
		print(n);
		printf("\n");
	}
	return 0;
}

[medv]

Your code has a lot of WA:
1. input: w
your program says: w
But 'w' is not WWF, only p,q,r,s,t!

2. input: qwerty
your program says: no WFF possible
But we can find a subset of WWF, for example: t.

[medv]

Why Run Time Error?
(Sorry, I can't use HTML)


#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

char s[101];
vector<char> op,var;
vector<char>::iterator iter;
string res;

int f(char a, char b)
{
if (a == 'N') return 1;
if (b == 'N') return 0;
return a < b;
}

void main(void)
{
int i,j;
while(gets(s))
{
if (s[0] == '0') break;
op.clear(); var.clear();
for(i=0;i<strlen(s);i++)
if ((s <='Z') && (s >= 'A')) op.push_back(s);
else var.push_back(s);
for(iter=var.begin();iter!=var.end();)
if (!((*iter == 'p') || (*iter == 'q') || (*iter == 'r') || (*iter == 's') || (*iter == 't'))) var.erase(iter);
else iter++;
for(iter=op.begin();iter!=op.end();)
if (!((*iter == 'K') || (*iter == 'A') || (*iter == 'N') || (*iter == 'C') || (*iter == 'E'))) op.erase(iter);
else iter++;
sort(op.begin(),op.end(),f);
if (var.empty())
{
printf("no WFF possible\n");
continue;
}
res = "";i=j=0;
if (op.size() > 0)
{
while((op == 'N') && (i < op.size())) res += op,i++;
while((i < op.size()) && (j < var.size()-1))
{
res = res + op + var[j];
i++; j++;
}
}
res += var[j];
printf("%s\n",res.c_str());
}
}

[Vexorian]

It is not html it is bb code you simply use [code] tags for example:

[code]
your c++ program
[/code]

You should check your email, it should tell you the kind of run time error your program got

[Khaled_912]

is it asking for a 'sub-sequence' or a 'substring' (consecutive characters)? Is it allowed to re-order the symbols?

[helloneo]

is it asking for a 'sub-sequence' or a 'substring' (consecutive characters)? Is it allowed to re-order the symbols?

Re-ordering is allowed..

[Jemerson]

I don't understand why qKpNq is not a valid WFF. Can someone explain me please? I'm misunderstanding the problem.

Thanx in advance

[Erik]

Hi,

I don't understand why qKpNq is not a valid WFF. Can someone explain me please? I'm misunderstanding the problem.

The problem statement says

* p, q, r, s, and t are WFFs
* if w is a WFF, Nw is a WFF
* if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

Hence q, p, Nq and KpNq are valid. But qKpNq doesn't match any rule. It doesn't start with N, K, A, C nor E. Hence it could only be valid WFF if it matches the first rule. But as qKpNq doesn't equal p, q, r, s or t it finally is no valid WFF.

Cu, Erik

[annhy]

is it asking for a 'sub-sequence' or a 'substring' (consecutive characters)? Is it allowed to re-order the symbols?

Re-ordering is allowed..

Re-ordering is allowed?
So if the input is qpqKN, the output is still KpNq ?

I am really confused now...

[annhy]

Re-ordering is allowed..

Re-ordering is allowed?
So if the input is qpqKN, the output is still KpNq ?

I am really confused now...

OK... Re-ordering is allowed.
If the input is qpqKN, the answer could be KpNq, NKpq or KqNq.

I got AC now.