/** * For each value from 0 to 9, find the number of substrings that have * that specific value. * For value K, split the string into intervals that do not contain * values larger than K. For each interval find the positions where * K occurs and count the number of substrings in each interval that * do not include at least one occurrence of K. * * @author Finn Lidbetter */ fun gcd(a: Long, b: Long): Long { if (b == 0L) { return a } return gcd(b, a%b) } fun main() { val digits = readln().toCharArray().map{ it -> it - '0'} val n = digits.size var counts = LongArray(10){ 0 } for (value in 0..9) { var intervals = mutableListOf>() var start = -1 var index = 0 while (index < n) { if (digits[index] <= value) { if (start == -1) { start = index } } else if (start != -1) { val end = index - 1 intervals.add(Pair(start, end)) start = -1 } index++ } if (start != -1) { intervals.add(Pair(start, n-1)) } var valueSubstrings = 0L for (interval in intervals) { var nonValueStart = -1 var nonValueSubstrings = 0L for (intervalIndex in interval.first..interval.second) { if (digits[intervalIndex] == value) { if (nonValueStart != -1) { val nonValueEnd = intervalIndex - 1 val nonValueWidth = (nonValueEnd - nonValueStart + 1).toLong() nonValueSubstrings += (nonValueWidth * (nonValueWidth + 1L)) / 2L nonValueStart = -1 } } else { if (nonValueStart == -1) { nonValueStart = intervalIndex } } } if (nonValueStart != -1) { val nonValueEnd = interval.second val nonValueWidth = (nonValueEnd - nonValueStart + 1).toLong() nonValueSubstrings += (nonValueWidth * (nonValueWidth + 1L)) / 2L } val intervalWidth = (interval.second - interval.first + 1).toLong() val intervalSubstrings = (intervalWidth * (intervalWidth + 1L)) / 2L valueSubstrings += (intervalSubstrings - nonValueSubstrings) } counts[value] = valueSubstrings } var totalSubstrings = n.toLong()*(n.toLong()+1L) / 2L var totalValue = 0L for (value in 0..9) { totalValue += value.toLong() * counts[value] } val gcf = gcd(totalSubstrings, totalValue) totalSubstrings /= gcf totalValue /= gcf var wholePart = 0 while (totalValue >= totalSubstrings) { wholePart++ totalValue -= totalSubstrings } if (totalValue == 0L) { println(wholePart) } else { val gcf2 = gcd(totalSubstrings, totalValue) totalSubstrings /= gcf2 totalValue /= gcf2 if (wholePart > 0) { println("$wholePart $totalValue/$totalSubstrings") } else { println("$totalValue/$totalSubstrings") } } }