// @EXPECTED_RESULTS@: ACCEPTED,TIME_LIMIT_EXCEEDED /** * A just do it problem, model it as a graph and find a path for the queries. Only tricky part is that you can go both ways. * An important observation is that the number of queries is way higher than the number of conversion rules. This signals * that a form of memorization is required. * * I'm doing a DFS trying to find a path for each conversion query. Due to set operations to deal with bidirectional * paths its O(n log n). Hopefully fast enough since the n is quite low. I also try to learn and add earlier found * query (sub)-results to the conversions (and impossible combinations). */ import java.util.LinkedList fun main() { val input = System.`in`.bufferedReader() val (n, q) = input.readLine().split(" ", limit = 2).map { it.toInt() } val map = mutableMapOf>() val known = mutableSetOf>() repeat(n) { val line = input.readLine() val (_, unit, amount, other) = regex.matchEntire(line)!!.groupValues map.putIfAbsent(unit, mutableSetOf()) map.putIfAbsent(other, mutableSetOf()) map[unit]!!.add(UnitConversion(other, amount.toDouble())) map[other]!!.add(UnitConversion(unit, 1.0 / amount.toDouble())) known.add(unit to other) known.add(other to unit) } val queue = LinkedList>() val seen = mutableSetOf() val impossibleSet = mutableSetOf>() repeat(q) { val line = input.readLine() val (_, amount, unit, other) = other.matchEntire(line)!!.groupValues seen.clear() queue.clear() queue.add(unit to amount.toDouble()) seen.add(unit) var result = -1.0 while (queue.isNotEmpty()) { val (current, value) = queue.removeFirst() if (current to other in impossibleSet) break if (current == other) { result = value break } map[current]!!.filter { seen.add(it.unit) } .map { it.unit to (it.amount * value).also { value -> if (known.add(it.unit to unit)) { known.add(unit to it.unit) val factor = value / amount.toDouble() map[it.unit]!!.add(UnitConversion(unit, 1.0 / factor)) map[unit]!!.add(UnitConversion(it.unit, factor)) } } } .toCollection(queue) } println( when (result) { -1.0 -> "impossible".also { impossibleSet.addAll(listOf(unit to other, other to unit)) } else -> result.also { val factor = result / amount.toDouble() map[unit]!!.add(UnitConversion(other, factor)) map[other]!!.add(UnitConversion(unit, 1.0 / factor)) } } ) } } val regex = Regex("1 (\\w+) = ([\\d.]+) (\\w+)") val other = Regex("([\\d.]+) (\\w+) to (\\w+)") data class UnitConversion( val unit: String, val amount: Double )