The 3rd Series Problem Set

If announcement is none of these types, the answer is I DO NOT UNDERSTAND.

Density of inhabitants in the Large Sandy Country is very low. All settlements are situated near Small Sandy River - the only river in the country. Frequent sandstorms impede cultivation of butu, a plant with big fruits from which is made butu brandy. People are often on trail where the main role plays the number of fruits of butu which remain on the tree until the nearest harvest. Many foretellers are taking their chance to predict the future, especially when they got butu brandy and some money. Then they as loudly as much money they have got cry predictions like these: "The first four settlements from Hole of Sand down the river will gather minimal eightythree fruits" or "If you flow down the river from Sandy Hill to Stack of Sand, you will find no more than fiftyseven fruits".

One of these foretellers is very suspicious. Native people do not believe him and they would like to treat him according to their habits. In the first place, they must prove that at least one of his predictions is false. They have written all predictions on the paper, but they do not know what they should do now.

Task: Let 1, ..., n be the numbers of n settlements down the Sandy river. All predictions are of type "in settlements k, k+1, ..., l is together at least m fruits of butu" or "in settlements k, k+1, ..., l is together at most m fruits of butu". Write a program which for given triples of numbers k,l,m (k<= l) and the type of prediction outputs whether all predictions can be true.

Example:
Input:
3 predictions:
1 2 at least 26
3 3 at least 15
1 3 at most 40
Output:
All prediction cannot be true.

Like any other year, Frutus and Brutus assembled themselves to spend the Christmas at home. Holiday atmosphere prevailed. They both became identical presents, so they could not quarrel who has got better or more valuable present. But after they unpacked all their presents, a new problem appeared. Two identical sets of empty boxes remained them. Frutus began to show that he is the smarter one. He began to build a tower of his boxes. Brutus would not stand back and in a while he also built a tower. The objective was clear: to arrange boxes one on the another to get highest possible tower. It was the only way to win. When one of them finished a tower of some height, the other soon came with new configuration of boxes, forming a higher one. Maybe they are trying until now, because they don't know, how high tower can be built.

Task: Write a program, that for given N - number of boxes and dimensions (x[1], y[1], z[1]),...(x[N], y[N], z[N]) computes the height of highest possible tower, that can be built of those N boxes. The boxes can be arbitrarily rotated. But, if box B is laid on box A, box A having top face of dimensions a1, a2 (a1<= a2) and box B having bottom face of dimensions b1, b2 (b1<= b2), then must inequalities a1 <= b1 a a2 <= b2 hold (box with larger base should not lay on a box with smaller base).

Example:
Input: N=3
Dimensions of boxes: (2,2,2), (3,2,1), (1,2,2)
Output: Maximal height of tower 7.

In this problem we will work with functional programming language described in task descriptions of first two rounds. We already learned to operate with clauses over natural numbers and to code a list of numbers into a single number. It is also very natural to represent tree structure by a number. In this problem, we will consider so called binary trees. The empty binary tree does not contain any node. An nonempty binary tree contains exactly one node with no edge leading in, called root. Out from the root lead two edges, connecting it to the left and right subtrees (if the particular subtree is not empty, this edge leads to its root). Each node of the tree has assigned one natural number.

Binary tree. Empty binary tree will be represented by empty list (number) 0. Nonempty binary tree T with value k assigned to the root, left subtree TL and right subtree TR is represented using pair function as number z(T) = (k,z(TL),z(TR)), where z(TL) and z(TR) are numbers representing TL and TR respectively.

Depth of the tree. Depth of the tree is defined in functional language by defining function Depth as follows:
Depth(zT)=0 <- zT=0
Depth(zT)=Depth(zTL)+1 <- zT=k,zTL,zTR & Depth(zTL)>Depth(zTR)
Depth(zT)=Depth(zTR)+1 <- zT=k,zTL,zTR & Depth(zTL)<=Depth(zTR)

Example. Tree on the left picture is represented by the list (number) (1,(2,(3,0,0),(4,0,0)),(5,(6,0,0),0)), tree on the right picture is represented by the list (4,(1,0,(2,0,0)),(7,(6,0,0),0)).

Serching Trees. Binary tree is said to be searching tree, if for each its subtree T value k assigned to its root is larger than any value assigned to a node from the left subtree of T and simultaneously, k is greater than any value assigned to a node from right subtree of T.

For example, the tree on the left figure is not an searching tree, because each left son has larger value than its father. The tree on the right figure is an searching tree.

For a given searching tree T is very easy to find out, if it contains a given number n (it means, if there is a node in T with assigned number n) - we can easily say by comparing n with value assigned to root, whether n should (if ever) be contained in left or right subtree. Unfortunately, some trees could have very long branches, causing that during a search must be examined large number of nodes. Improved version of searching trees are balanced searching trees - their subtrees have about the same size so each comparison can exclude about half of the nodes.

AVL-trees. We call a binary searching tree an AVL-tree, if, for each subtree T, depths of its left and right subtrees differ at most by 1.

Tree on the right figure is an AVL tree, because for each node except nodes with numbers 1 and 7 have left and right subtrees of equal depth. left subtree of node with number 1 has depth 0 and right has depth 1, so the difference si 1. Similarly difference of depths for node with number 7 is 1.

Task: Write in functional language

1. function Member(T,x), that returns 0, if AVL-tree T contains a node with assigned value x, or 1, if no node of T has value x.
2. function Insert(T,x), that for AVL-tree T and number x returns AVL-tree T', containing nodes with the same assigned numbers as T and a node with assigned number x. You can assume, that T does not contain x. For example, Insert((1,0,(2,0,0)),3) = 2,(1,0,0),(3,0,0).
3. function Delete(T,x), that takes an AVL-tree T and an element (a number) x on input and computes AVL-tree T', that contains nodes with the same assigned numbers as T, but it does not contain node with assigned number x. Assume, that T does contain a node with assigned number x. For example, Delete((4,(1,0,(2,0,0)),(5,0,0)),5) = 2,(1,0,0),(4,0,0).

Remark: Do not forget detailed description and justification of correctness of your program.

Remark 2: Try to write your programs effective (try to minimize number of recursion calls). But correctness of your program is much more important than efficiency.