10854 - Number of Paths

Programmer · Post by **Programmer** » Fri May 27, 2005 9:48 pm

I'm getting this program WA WA and WA.
I want just some tests.I want to know is answer always even or 1 can answer be 0.
Please give some tests.It seems ease but WA.

dumb dan · Post by **dumb dan** » Sat May 28, 2005 12:11 am

Perhaps this answers your questions?

input:

Code: Select all

4
ENDPROGRAM
S
ENDPROGRAM
IF
ELSE
END_IF
ENDPROGRAM
IF
ELSE
IF
ELSE
END_IF
END_IF
ENDPROGRAM

output:

Code: Select all

Cho · Post by **Cho** » Sat May 28, 2005 4:59 am

The output must be positive integer. For any possible output, you can easily generate the corresponding input like the pattern below:

Code: Select all

1
IF
IF
IF
IF
IF
IF
IF
IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ELSE
END_IF
ENDPROGRAM

The ouput of this case is 9.

zhang · Post by **zhang** » Sat May 28, 2005 4:36 pm

I also get WA ,but it seems that I have right answer from your test data.
Please give me some hard test data.Thank u.

Programmer · Post by **Programmer** » Sun May 29, 2005 9:06 am

What is answer for this inout

Code: Select all

1 
IF 
IF 
IF 
IF 
IF 
IF 
IF 
IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
IF 
IF 
IF 
IF 
IF 
IF 
IF 
IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ELSE 
END_IF 
ENDPROGRAM

Cho · Post by **Cho** » Sun May 29, 2005 10:06 am

Emilio · Post by **Emilio** » Mon May 30, 2005 9:43 pm

Hi!
I haven't got AC. But I think that the correct answer is 18, not 81.

Tamagodzi · Post by **Tamagodzi** » Mon May 30, 2005 9:54 pm

The correct answer is 81.

Lets take this simple Programm to show you the idea:

Code: Select all

IF
ELSE
END_IF
IF
ELSE
END_IF
IF
ELSE
END_IF
ENDPROGRAM

Here all IF-Conditions can be true, short: TTT
Or the first two are true and the third false, short: TTF
And so on to FFF
So at all there are 2*2*2=8 possibilities.

So the answer to the sample Input is 9*9=81 and not 9+9=18.

Emilio · Post by **Emilio** » Mon May 30, 2005 10:29 pm

you are right!

Sorry by the fault!

zhang · Post by **zhang** » Sat Jun 04, 2005 4:37 am

I got WAs again. I was tired out by this problem.
Who could send your souce code to me!
My e-mail address is: zhangfan555@tom.com
Thx.

Cho · Post by **Cho** » Sat Jun 04, 2005 4:44 am

Tell us your algorithm.

mf · Post by mf » Sat Jun 04, 2005 9:47 am

Make a test case, which consists of "IF\nELSE\nEND_IF\n" repeated 32 times.
The correct answer to it is "4294967296," but some programs may print "0."

zhang · Post by **zhang** » Sat Jun 04, 2005 9:02 pm

Still WA,Who can tell me why?Thank u!!

Code: Select all

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
long long count1=0;
char com[805000];
long long find(long long from,long long end){
	//cout<<from<<' '<<end<<endl;
	//if(from==end) return 1;
	//if(from+1==end) return 1;
	if(from==end+1) return 1;
	long long i=0,ans,p=0,start,no=0;
	ans=0;
	for(i=from;i<=end;i++){
		//if(com[i]=="ELSE") no++;
		if(com[i]=='I') p++;
		if(com[i]=='N') p--;
		if(p==0){
			no++;			
		}
	}
	//cout<<"no"<<no<<endl;
	p=0;
	if(no>1){
//		cout<<"2**"<<endl;
		start=1;
		ans=1;
		for(i=from;i<=end;i++){
			if(com[i]=='I') p++;
			if(com[i]=='N') p--;
			if(p==0){
				ans*=find(start,i);
				start=i+1;
			}
		}
	}
	else{
//		cout<<"1**"<<endl;
		p=0;
		for(i=from+1;i<=end-1;i++){
			if(com[i]=='I' ) p++;
			if(com[i]=='N') p--;
			if(com[i]=='E' && p==0)
			{
				ans=find(from+1,i-1)+find(i+1,end-1);
				break;
			}
		}
	}
	return ans;
}
int main(){
	char a[30];
	long long n,i;
	cin>>n;
	while(n--)
	{
		count1=0;
		while(cin>>a){
			if(strcmp(a,"ENDPROGRAM")==0) break;
			if(a[0]!='S'){
				count1++;
				if(a[1]=='N')
				com[count1]=a[1];
				else com[count1]=a[0];

			}		
		}
		cout<<find(1,count1)<<endl;
	}
//system("pause");
}

mf · Post by mf » Sat Jun 04, 2005 11:17 pm

Input:

Code: Select all

1
IF
END_IF
ENDPROGRAM

The correct output: 2.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Sat Jun 04, 2005 11:24 pm

This is not a valid input.

A conditional sentence is represented by the keywords IF, ELSE and END_IF. The condition of the IF sentence is omitted (i.e., only the IF keyword appears) and it is supposed that all IF sentences have a corresponding ELSE.