11103 - WFF 'N PROOF

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

Moderator: Board moderators

Post Reply
coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

11103 - WFF 'N PROOF

Post by coolguy » Fri Oct 20, 2006 7:19 am

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
Last edited by coolguy on Fri Oct 20, 2006 8:39 am, edited 1 time in total.
In good company

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Oct 20, 2006 8:25 am

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
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

Post by coolguy » Fri Oct 20, 2006 8:44 am

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
In good company

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Oct 20, 2006 5:12 pm

coolguy wrote: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..~

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Oct 21, 2006 7:36 pm

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Your code has a lot of WA

Post by medv » Mon Nov 13, 2006 4:12 pm

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
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

WHY RTE?

Post by medv » Mon Nov 13, 2006 4:36 pm

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Nov 14, 2006 4:09 am

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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by Khaled_912 » Sun Mar 11, 2007 10:52 am

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Mar 11, 2007 11:10 am

Khaled_912 wrote:is it asking for a 'sub-sequence' or a 'substring' (consecutive characters)? Is it allowed to re-order the symbols?
Re-ordering is allowed.. :-)

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Wed Apr 04, 2007 1:58 am

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

Thanx in advance
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Wed Apr 04, 2007 7:34 am

Hi,
Jemerson wrote: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
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re:

Post by annhy » Thu Jul 22, 2010 7:39 am

helloneo wrote:
Khaled_912 wrote: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
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: Re:

Post by annhy » Thu Jul 22, 2010 8:29 am

annhy wrote:
helloneo wrote: 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.

Post Reply

Return to “Volume 111 (11100-11199)”