11108 - Tautology

[vinay]

i want to know whether brute force method will do here...

around 50 different varibles r possible ... making the algo 2^50

how to deal it???

[helloneo]

i want to know whether brute force method will do here...

around 50 different varibles r possible ... making the algo 2^50

how to deal it???

There are only 5 variables.. 'p', 'q', 'r', 's', 't'

[vinay]

sorry there will be only five variable variables , brute force applicable i think

[vinay]

@ helloneo

yeah i got it just now...

thanks ...

[Sedefcho]

Here is some sample I/O from my WA program.

INPUT

Code: Select all

p
q
r
s
ApNp
ApNq
ApNNNp
ANNpNNNp
EKCpqCqpEpq
EpNNp
EpNNNp
ENpNNNp
NKpNp
CpCqp
0

OUTPUT

Code: Select all

not
not
not
not
tautology
not
tautology
tautology
tautology
tautology
not
tautology
tautology
tautology

Is this output OK?
Could someone post several critical test cases ?
I think I have solved the problem but keep getting WA.

Thanks in advance.

[Darko]

That looks right. Do you trim input strings?

[Sedefcho]

I don't trim them. But anyway, I skip all chars in the
input strings which are not part of the problem statement
('N', 'A', 'p', 'r' ... etc. ).

INPUT

Code: Select all

p
q
r
s
   A  p  Np
   ApNq     
ApN    NNp
ANNpNNNp
EKCp    qCqpEpq
EpNNp
EpNNNp
EN  *****  pN   ****  NNp
NK *******  pN   **** &&&& p   ***
CpCqp
0

OUTPUT

Code: Select all

not
not
not
not
tautology
not
tautology
tautology
tautology
tautology
not
tautology
tautology
tautology

So... ? Does someone have some more test cases?
What special could we have in the input?

[Sedefcho]

I found my mistake. Thanks anyway.

[kronenthaler]

Hi, i trying to solve this problem by a brute force implementation, I use binary trees via struct, but I got a RTE signal 11. The input line buffer is large enough but I dont know where the problem is. Someone may help me?

I really appreciate any input to replicate the error.

Code: Select all

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

#define P (1)
#define Q (1<<1)
#define R (1<<2)
#define S (1<<3)
#define T (1<<4)

bool isUpper(char c){ return c>='A' && c<='Z';}

struct arbin{
	char root;
	arbin *left,*right;
	arbin(char r,arbin *_l,arbin *_r){
		root=r;
		left=_l;
		right=_r;
	}
	arbin(char r){
		root=r;
		left=right=NULL;
	}

	bool isLeaf(){
	   return left==NULL && right==NULL;
	}

	bool eval(int val){
	   if(isLeaf()){
		   if(root=='p') return val&P;
		   if(root=='q') return val&Q;
		   if(root=='r') return val&R;
		   if(root=='s') return val&S;
		   return val&T;
	   }else{
		   if(root=='K') return left->eval(val) && right->eval(val);
		   if(root=='A') return left->eval(val) || right->eval(val);
		   if(root=='N') return !left->eval(val);
		   if(root=='C') return !left->eval(val) || right->eval(val);
		   return left->eval(val) == right->eval(val);
	   }
	}

	void inOrder(){
	   if(left!=NULL)
		   left->inOrder();
	   printf("%c ",root);
	   if(right!=NULL)
		   right->inOrder();
	}
};

int parseIndex;

arbin* parse(char* line,int n){
	while(parseIndex<n){
		if(isUpper(line[parseIndex])){
			if(line[parseIndex]=='N')
				return new arbin(line[parseIndex++],parse(line,n),NULL);
			else
				return new arbin(line[parseIndex++],parse(line,n),parse(line,n));
		}else
			return new arbin(line[parseIndex++]);
	}
	return NULL;
}

int main(){
	//freopen("11108.txt","r",stdin);
	char* line=new char[1000];
	while(true){
		char c=' ';
		int i=0;
		while(scanf("%c",&c)==1){
			if(c=='\n') break;
			if(c=='p' || c=='q' || c=='r' || c=='s' || c=='t' || 
			   c=='A' || c=='K' || c=='N' || c=='C' || c=='E')
				line[i++]=c;

			if(c=='a' || c=='k' || c=='n' || c=='c' || c=='e')
				line[i++]=c-'a'+'A';

			if(c=='P' || c=='Q' || c=='R' || c=='S' || c=='T')
				line[i++]=c-'A'+'a';

			if(c=='0') return 0;
		}
		line[i]='\0';
		
		parseIndex=0;
		arbin* tree=parse(line,strlen(line));
		if(tree==NULL)
			printf("tautology\n");
		else{
			bool exit=true;
			for(int i=0;i<=32 && exit;i++)
				exit &= tree->eval(i);

			if(exit)
				printf("tautology\n");
			else
				printf("not\n");
		}
	}
	return 0;
}

PD: sorry if my english is wrong