Problem B
Average Substring Value
Let $s$ be a nonempty string consisting entirely of $\textrm{base-}10$ digits (0–9). If the length of $s$ is $n,$ number the digits $1, 2, 3, \ldots , n$ from left to right, and for $1 \leq i \leq j \leq n,$ let $s[i,j]$ denote the substring consisting of the digits from $\textrm{position}~ i$ to $\textrm{position}~ j,$ inclusive. (It follows that we are only considering nonempty substrings.) Assign a value to each substring that is simply equal to the largest digit in the substring. What is the average value of the substrings $\textrm{of}~ s$?
Note that two different substrings may be identical (as strings), but for the purposes of this problem they are treated as distinct. For example, if $s = \texttt{1010},$ then $s[1,2] = s[3,4] = \texttt{10}$ are distinct substrings (both with $\textrm{value}~ 1).$
Input
The input is a single nonempty string, $s,$ of $\textrm{base-}10$ digits. The length of $s$ is at most $200\, 000.$
Output
Output a line containing the average value of the substrings of $s.$ If the average is an integer, print the integer. If the average is a proper fraction, i.e., is equal to $a/b,$ where $a$ and $b$ are positive integers and $a < b$, print this fraction in lowest terms, with a ‘/’ symbol separating the numerator and denominator. If the average is greater $\textrm{than}~ 1$ and does not simplify to an integer, print the whole part followed by the proper fractional part, separated by a space, with the proper fractional part in lowest terms and formatted as described in the previous sentence.
Sample Input 1 | Sample Output 1 |
---|---|
123 |
2 1/3 |
Sample Input 2 | Sample Output 2 |
---|---|
4084 |
6 |
Sample Input 3 | Sample Output 3 |
---|---|
1010 |
4/5 |
Sample Input 4 | Sample Output 4 |
---|---|
00000 |
0 |