Ordered trees
Assignment
Quido is becoming familiar with binary trees. He noticed that when a numerical key is assigned to each node various new properties of the tree may arise. For example, the values on each path from the root to a leaf might be sorted in non-desreasing order in a similar way as it is typical for binary heaps. Quido chose to call such trees ordered trees. Many trees are not ordered and to measure their un-orderliness Quido introduced a notion of displacement index. The displacement index of a node n is the number of all descendants of n which key value is smaller than the key value of n. The displacement index of the tree is the sum of displacement indices of all its nodes. Obviously, a tree is an ordered one exactly when its displacement index is equal to zero. The image bellow depicts an example of binary tree which displacement index is 17.
A node b is a descendant of a node a if the path from b to the root of the tree contains a.
Input
To avoid voluminous input data the following simplifying concept is used.
Let X, A, M, D be positive integers. For the input tree T it hods:
1. X is the key value of the root of T.
2. The depth of T is less or equal to D.
3. When the key value of a node is greater or equal to A than the node is a leaf.
4. When the depth of a node is less than D and its key value k is less than A then there are two children of this node in T. The key value of the left child is 2 + (k2 mod M) and the key value of the right child is 3 + (k2 mod M).
The input contains one text line with the values X, A, M, D in this order separated by space. The value of D is less than 25, the other input values do not exceed 109.
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.