eolymp
bolt
Try our new interface for solving problems
Problems

Two Mysterious Alphabets from a Tree

Two Mysterious Alphabets from a Tree

Your task is to extract \textbf{2 }alphabets from a \textbf{binary }tree which is composed of unsigned integers respecting the following rules. Let \textbf{n} be the height of a tree. At the level \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{n}), the tree contains \textbf{k }of nodes and each node has \textbf{2 }children nodes (except the leaf nodes at the level \textbf{n} which have no children). See the example below to understand the tree formation. Some nodes may have \textbf{2 }parent nodes. \textbf{Example}: \includegraphics{https://static.e-olymp.com/content/0e/0e2a59d56959645ae396a410c28c4fada4b2ae5f.jpg} \includegraphics{https://static.e-olymp.com/content/12/124aa387a9e1fee61b081cff04c856a5adaea1fc.jpg} You need to walk in a tree on the path that has a maximum summation (e.g. \textbf{1 + 5 + 9} = \textbf{15}). Numbers in each summation cannot cross into different links (e.g. \textbf{5 + 7 }is illegal). Then, your intermediate task is to calculate \textbf{2 }numbers for alphabet extraction. The first number is calculated from \textbf{i^2} where \textbf{i }is a number along the maximum summation path and \textbf{n }is the height of a tree. \includegraphics{https://static.e-olymp.com/content/12/124aa387a9e1fee61b081cff04c856a5adaea1fc.jpg} \textit{The second number} is a summation of the maximum path (\textbf{i} ). Regarding to the example above, the first number =\textbf{ 1 + 25 + 81} = \textbf{107 }and the second number = \textbf{1 + 5 + 9} = \textbf{15}. Finally, these two numbers are transformed into two lower case alphabets from '\textbf{a}' to '\textbf{z}' respectively, where '\textbf{a}' is used for \textbf{0 }and '\textbf{z}' is used for \textbf{25}. Since there are only \textbf{26} alphabets, a number greater than \textbf{25 }will reuse the same set of alphabets. For example \textbf{107} = '\textbf{d}' and \textbf{15} = '\textbf{p}' (that is, the first alphabet '\textbf{a}' = \textbf{0} or \textbf{26 }or \textbf{52 }etc). Write a program to find the \textbf{2 }mysterious alphabets from a given tree. \InputFile The first line contains the height \textbf{n }(\textbf{0 }< \textbf{n }< \textbf{100}) of a tree. The second line contains unsigned integer numbers \textbf{i }(\textbf{0 }< \textbf{i }< \textbf{100}) in each level of a tree, consecutively. Assume that there is only one maximum path in a tree. \OutputFile The first line contains two integer calculated from the rules above, and the second line contains \textbf{2 }decoded alphabets.
Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1 4 5 7 8 9
Output example #1
107 15
dp
Author Dr. Warodom Werapun
Source 2013 ACM-ICPC Thailand Southern Programming Contest, August 10, Problem B