ALpha Ceiling Manufacturers (ACM) is analyzing the p roperties of its new series of Incredibly
Collapse-Proof Ceilings (ICPCs). An ICPC consists of n la
yers of material, each with a different
value of collapse resistance (measured as a positive integer). The analysis ACM wants to run will
take the collapse-resistance values of the la
yers, store them in a binary search tree, and check
whether the shape of this tree in any way correlates with the quality of the whole construction.
Because, well, why should it not?
To be precise, ACM takes the collapse-resistance values for the la
yers, ordered from the top la
yer
to the bottom la
yer, and inserts them one-by-one into a tree. The rules for inserting a value v are:
• If the tree is empty, make v the root of the tree.
• If the tree is not empty, compare v with the root of the tree. If v is smaller, insert v into the left
subtree of the root, otherwise insert v into the right subtree.
ACM has a set of ceiling prototypes it wants to analyze by trying to collapse them. It wants to take
each group of ceiling prototypes that have trees of the same shape and analyze them together.
For example , assume ACM is considering five ceiling prototypes with three la
yers each, as
described by Sample Input 1 and shown in Figure C.1. Notice that the first prototype’s top la
yer
has collapseresistance value 2, the middle la
yer has value 7, and the bottom la
yer has value 1. The
second prototype has la
yers with collapse-resistance values of 3, 1, and 4 – and yet these two
prototypes induce the same tree shape, so ACM will analyze them together.
Given a set of prototypes, your task is to determine how many different tree shapes they induce.