https://coderun.yandex.ru/problem/buses-ya-intern Средняя

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math
import java.lang.IllegalArgumentException
import java.lang.ArithmeticException

fun gcd(a: Long, b: Long): Long {
    var x = Math.abs(a)
    var y = Math.abs(b)
    while (y != 0L) {
        val temp = y
        y = x % y
        x = temp
    }
    return x
}

fun power(base: Long, exp: Int): Long {
    if (exp < 0) throw IllegalArgumentException("Exponent must be non-negative, got $exp")
    if (exp == 0) return 1L
    var result = 1L
    for (i in 1..exp) {
        if (base > 0 && result > Long.MAX_VALUE / base) {
            throw ArithmeticException("Long overflow during power calculation: $base^$exp")
        }
        result *= base
    }
    return result
}

data class Fraction(val num: Long, val den: Long) {
    companion object {
        fun create(n: Long, d: Long): Fraction {
            require(d != 0L) { "Denominator cannot be zero" }
            if (n == 0L) return Fraction(0, 1)
            val common = gcd(n, d)
            var numNorm = n / common
            var denNorm = d / common
            if (denNorm < 0) {
                numNorm = -numNorm
                denNorm = -denNorm
            }
            return Fraction(numNorm, denNorm)
        }
    }

    operator fun plus(other: Fraction): Fraction {
        val newNum = num * other.den + other.num * den
        val newDen = den * other.den
        return create(newNum, newDen)
    }

    operator fun minus(other: Fraction): Fraction {
        val newNum = num * other.den - other.num * den
        val newDen = den * other.den
        return create(newNum, newDen)
    }

    operator fun times(other: Fraction): Fraction {
        val newNum = num * other.num
        val newDen = den * other.den
        return create(newNum, newDen)
    }

    operator fun div(other: Fraction): Fraction {
        require(other.num != 0L) { "Division by zero fraction" }
        val newNum = num * other.den
        val newDen = den * other.num
        return create(newNum, newDen)
    }

    operator fun unaryMinus(): Fraction {
        return create(-num, den)
    }

    override fun toString(): String {
        return "$num/$den"
    }
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt()
    val tValues = reader.readLine().split(" ").map { it.toInt() }
    val tMin = tValues.minOrNull() ?: throw IllegalArgumentException("Input list of t_k cannot be empty")
    require(tMin >= 1) { "t_k must be >= 1, but found minimum $tMin" }

    var coeffs = mutableListOf(Fraction.create(1, 1))
    for (ti in tValues) {
        val minusOneOverTi = Fraction.create(-1, ti.toLong())
        val nextCoeffs = MutableList(coeffs.size + 1) { Fraction.create(0, 1) }
        for (j in coeffs.indices) {
            val aj = coeffs[j]
            nextCoeffs[j] = nextCoeffs[j] + aj
            val term = aj * minusOneOverTi
            nextCoeffs[j + 1] = nextCoeffs[j + 1] + term
        }
        coeffs = nextCoeffs
    }

    var expectedValue = Fraction.create(0, 1)
    for (k in coeffs.indices) {
        val ck = coeffs[k]
        if (ck.num == 0L) continue
        val tMinPowKPlus1 = power(tMin.toLong(), k + 1)
        val tMinTerm = Fraction.create(tMinPowKPlus1, 1)
        val kPlus1Term = Fraction.create((k + 1).toLong(), 1)
        val termValue = ck * tMinTerm / kPlus1Term
        expectedValue = expectedValue + termValue
    }

    writer.write(expectedValue.toString())
    writer.newLine()
    reader.close()
    writer.close()
}