Back
Close
  • 79

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

begin
if (condition1) then
action1
else
action2
endif

if (condition2) then
action3
else
action4
endif
end

How many different results this program can produce?
Answer is 4.

By varying combination of condition1 and condition2, there are 4 possible different results:
🔹 action1, action3
🔹 action1, action4
🔹 action2, action3
🔹 action2, action4


In this puzzle, our focus is to evaluate the program logical structure.
We do not care what conditions are given nor what actions are to happen.
We just want to know the number of result combinations.

To ease evaluation, we normalize the syntax of the program.

🔶 "if...then" is represented by "if". We assume there should always be a condition, hidden, after "if".
🔶 We assume following an "if" line there is always one (no more, no less) related "else" line. "if..else" will be finalized by an "endif" line to make a complete statement.
🔶 Nested conditions are allowed.
🔶 Action statements are represented by "S". It can appear anywhere within the program to perform actions. We are lazy sometimes we may omit writing it but you have to assume within an if-else-endif structure there is always at lease one action statement (can be hidden) for the "true" condition and another one (also can be hidden) for the "false" condition.
🔶 The whole program is enclosed by begin and end
🔶 We do not indent the lines; we do not insert blank lines.

The above example program can be normalized as:

begin
if
else
endif
if
else
endif
end


Another example with nested conditions:

begin
if (condition1) then
S
else
if (condition2) then
S
else
S
endif
endif
end


This program can be normalized as:

begin
if
S
else
if
S
else
S
endif
endif
end

It has 3 result combinations.

More program structure examples are in the test cases.

Your task is to evaluate some normalized program structures to tell the number of result combinations.
Input
Line 1 : N, the number of lines in the program.
The following N lines are the normalized program codes.

There is no unnecessary space at the front or end of the lines.
You can assume all given codes are syntactically correct.
Output
Line 1 : The number of result combinations
Constraints
2 ≤ N ≤ 195
Example
Input
8
begin
if
else
endif
if
else
endif
end
Output
4

A higher resolution is required to access the IDE