// Liam Keliher, 2024 // // Solution for problem "Average Substring Value" (averagesubstringvalue) // // Use precomputation to calculate, in constant time, the number of intervals // for which a given digit is the maximum. If an interval contains more than // one maximum digit, the leftmost of these is considered the "donor". // // Complexity: O(n) import java.io.*; import java.util.*; public class AverageSubstringValueKeliher { static final int NUM_DIGITS = 10; //--------------------------------------------------------------- public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); int n = s.length(); int[] arr = new int[n]; for (int index = 0; index < n; index++) { arr[index] = s.charAt(index) - '0'; } // for index int[][] lastSeenLeft = new int[n][NUM_DIGITS]; int[][] lastSeenRight = new int[n][NUM_DIGITS]; for (int index = 0; index < n; index++) { Arrays.fill(lastSeenLeft[index], -1); Arrays.fill(lastSeenRight[index], n); } // for index // Fill lastSeenLeft lastSeenLeft[0][arr[0]] = 0; for (int index = 1; index < n; index++) { // start at 1 for (int d = 0; d < NUM_DIGITS; d++) { lastSeenLeft[index][d] = lastSeenLeft[index-1][d]; } // for d lastSeenLeft[index][arr[index]] = index; } // for index // Fill lastSeenRight lastSeenRight[n-1][arr[n-1]] = n-1; for (int index = n-2; index >= 0; index--) { // start at n-2 for (int d = 0; d < NUM_DIGITS; d++) { lastSeenRight[index][d] = lastSeenRight[index+1][d]; } // for d lastSeenRight[index][arr[index]] = index; } // for index long valueSum = 0; for (int index = 0; index < n; index++) { int digit = arr[index]; int max = -1; if (index > 0) { for (int d = digit; d < NUM_DIGITS; d++) { // start at digit if (lastSeenLeft[index-1][d] > max) { max = lastSeenLeft[index-1][d]; } // if } // for d } // if int i = max + 1; int min = n; if (index < n-1) { for (int d = digit+1; d < NUM_DIGITS; d++) { // start at digit+1 if (lastSeenRight[index+1][d] < min) { min = lastSeenRight[index+1][d]; } // if } // for d } // if int j = min - 1; // (index-i+1)*(j-index+1) is the number of intervals for which current digit is the maximum valueSum += (long)digit*(index - i + 1)*(j - index + 1); } // for index // Print answer long numIntervals = (long)n*(n+1)/2; if (valueSum % numIntervals == 0) { System.out.println(valueSum/numIntervals); } // if else { long g = gcd(valueSum, numIntervals); valueSum /= g; numIntervals /= g; if (valueSum < numIntervals) { System.out.println(valueSum + "/" + numIntervals); } // if else { long q = valueSum/numIntervals; long r = valueSum %= numIntervals; System.out.println(q + " " + r + "/" + numIntervals); } // if } // else } // main(String[]) //--------------------------------------------------------------- static long gcd(long a, long b) { while (b != 0) { long r = a % b; a = b; b = r; } // while return a; } // gcd(long,long) //--------------------------------------------------------------- } // class AverageSubstringValueKeliher