11103  WFF 'N PROOF
Moderator: Board moderators
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
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
The problem is to make a longest WFF with given charaters..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
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..~
I got WA with this code , but it seems OK to me..... can anyone check it?
here is the code
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
CSE,BUET
Bangladesh
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.
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.
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[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());
}
}
(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());
}
}

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
I don't understand why qKpNq is not a valid WFF. Can someone explain me please? I'm misunderstanding the problem.
Thanx in advance
Thanx in advance
UFCG Brazil  Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
Hi,
Cu, Erik
The problem statement saysJemerson wrote:I don't understand why qKpNq is not a valid WFF. Can someone explain me please? I'm misunderstanding the problem.
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.* 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.
Cu, Erik
Re:
Reordering is allowed?helloneo wrote:Reordering is allowed..Khaled_912 wrote:is it asking for a 'subsequence' or a 'substring' (consecutive characters)? Is it allowed to reorder the symbols?
So if the input is qpqKN, the output is still KpNq ?
I am really confused now...
Re: Re:
OK... Reordering is allowed.annhy wrote:Reordering is allowed?helloneo wrote: Reordering is allowed..
So if the input is qpqKN, the output is still KpNq ?
I am really confused now...
If the input is qpqKN, the answer could be KpNq, NKpq or KqNq.
I got AC now.