// Liam Keliher, 2024 // // TLE submission for problem "Average Substring Value" (averagesubstringvalue) // // Not as bad as the obvious brute-force solution. Still processes every substring, // but uses precomputation to calculate the value of a substring in constant time. // // Complexity: O(n^2) import java.io.*; public class TLE_BetterThanBruteForce { 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 + 1]; // use 1-based indexing for (int index = 1; index <= n; index++) { arr[index] = s.charAt(index-1) - '0'; } // for index // Precomputation int[][] freq = new int[n + 1][NUM_DIGITS]; for (int index = 1; index <= n; index++) { for (int d = 0; d < NUM_DIGITS; d++) { freq[index][d] = freq[index-1][d]; } // for d freq[index][arr[index]]++; } // for index long valueSum = 0; long numIntervals = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { // start at i for (int d = NUM_DIGITS-1; d >= 0; d--) { if (freq[j][d] > freq[i-1][d]) { valueSum += d; break; } // if } // for d numIntervals++; } // for j } // for i // Print answer 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 TLE_BetterThanBruteForce