Sum of Keys in the Leaves
Image 1. Example of a binary tree which corresponds to Example 1 bellow. The sum of keys in the leaves is equal to 81. |
The task
In this problem, you have to find the sum of all keys in the leaves of a given binary tree.
Input
The input contains a single text line with eight positive integers A, B, M, L1, L2, L3, D, R separated by one or more spaces. These parameters regulate the shape of the tree and specify the node keys as follows:
Suppose a node X contains key with value K. Then
- X has no children if K < L1 or if the depth of X is D,
- X has only left child if L1 ≤ K < L2,
- X has only right child if L2 ≤ K < L3,
- X has both children if L3 ≤ K.
- If left child of X exists then its key value is equal to (A×K + B) mod M.
- If right child of X exists then its key value is equal to (A×K + 2×B) mod M.
Output
The output contains a single text line with one integer equal to the sum of all keys in the leaves of the input tree.
Example 1
Input31 17 43 5 15 23 5 30Output
81The input tree of Example 1 is depicted in Image 1 above.
Example 2
Input117 241 2039 250 300 450 5 555Output
11251
Example 3
Input285 242 2053 260 310 450 10 682Output
207229
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.
Link to public data set