10854 - Number of Paths

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

Moderator: Board moderators

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

10854 - Number of Paths

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.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

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

1
1
2
3

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

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
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

81

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

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
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

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

:oops: you are right!

Sorry by the fault!

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

Tell us your algorithm.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Input:

Code: Select all

1
IF
END_IF
ENDPROGRAM
The correct output: 2.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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.

Post Reply

Return to “Volume 108 (10800-10899)”