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

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

### 11103 - WFF 'N PROOF

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

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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;
bool b;
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

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?

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

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

char s;
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') 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
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
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
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.. Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
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:
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:

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:

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.