KiddiePool.scala

import java.io.FileOutputStream

import scala.io.Source

/**
 * 풀에 물을 채우는 가장 좋은 방법은 모든 관을 하나의 관처럼 생각하고 그 관을 들이 붓는것.
 * 하지만 그 경우 온도가 틀릴수 있다.
 *
 * 온도가 틀릴 경우, 목표 온도를 기준으로 두개 의 리스트를 만든다.
 * 열량 호율 측면에서.
 * 온도가 낮을 경우, 낮은 묶음 중 가장 낮은 온도의 관부터 잠근다.
 * 온도가 높을 경우, 높은 묶음 중에서 가장 높은 온도의 관부터 잠궈나간다.
 */
object KiddiePool {
  val INPUT = "B-large-practice.in"
  val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
  val isConsole = false

  /**
   *
   * @param r rate of water
   * @param c temperature
   */
  case class Pipe(r: Double, c: Double) {
    def merge(pipe: Pipe) = {
      val volume = r + pipe.r
      Pipe(volume, (c * r + pipe.c * pipe.r) / volume)
    }
  }

  def main(args: Array[String]): Unit = {
    val itr = Source.fromFile(INPUT).getLines()
    val stream = if (isConsole) Console.out else new FileOutputStream(OUTPUT)
    try {
      Console.withOut(stream) {
        val sets = itr.next().toInt
        (1 to sets).foreach { set =>
          val Array(pipes, v, x) = itr.next().split(' ').map(_.toDouble)

          val ps = (1 to pipes.toInt).map { _ =>
            val Array(r, c) = itr.next().split(' ').map(_.toDouble)
            Pipe(r, c)
          }
          println(f"Case #$set: ${minimumSeconds(ps.toList, v, x)}")
        }
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }


  /**
   *
   * @param ps
   * @param V Traget Volume
   * @param X Target Temperature
   * @return
   */
  def minimumSeconds(ps: List[Pipe], V: Double, X: Double) = {
    def fastenPipes(cList: List[Pipe], opened: Pipe, comp: (Double) => Boolean, currentTemp: Double): Option[Double] = cList match {
      case x :: xs =>
        val Pipe(size, adjustedT) = mergePipes(opened :: xs)
        if (Math.abs(adjustedT - X) < 0.0000000001) {
          Some(V / size)
        } else if (comp(adjustedT)) {
          //x 를 배제해도 여전히 뜨겁거나 차가운 경우,
          fastenPipes(xs, opened, comp, adjustedT)
        } else {
          /**
           * T = ((V0*X0)+(V1*X1)) / (V0 + V1)
           * -> X = ((size * adjustedT) + (x.c * newRate)) / (size + newRate)
           * -> X*size + X*newRate = size * adjustedT + x.c * newRate
           * -> x.c * newRate - X*newRate = X*size - size * adjustedT
           * -> (x.c - X) * newRate = X*size - size * adjustedT
           * -> newRate = (X*size - size * adjustedT) / (x.C - X)
           */
          val rate = (X - adjustedT) * size / (x.c - X)
          //            if(rate.isNaN()) {
          //              println("weird - nan", adjustedT, opened, xs)
          //              None
          //            } else {
          Some(V / (size + rate))
          //            }
        }
    }
    val mergedPipes = mergePipes(ps)
    val currentTemperature = mergedPipes.c
    val ret = if (Math.abs(currentTemperature - X) < 0.0000000001) {
      Some(V / mergedPipes.r)
    } else {
      val sortedList = ps.sortBy(_.c)
      val (lowerSources, others) = sortedList.span(_.c < X)
      val (neutralSource, higherSource) = others.span(_.c == X)
      if (neutralSource.isEmpty && (higherSource.isEmpty || lowerSources.isEmpty)) { //Impossible
        None
      } else {
        val (controlledPipes, openedPipe, func) =
          if (currentTemperature > X)
            (higherSource.reverse, mergePipes(lowerSources ++ neutralSource), (x: Double) => x > X)
          else (lowerSources, mergePipes(higherSource ++ neutralSource), (x: Double) => x < X)
        fastenPipes(controlledPipes, openedPipe, func, currentTemperature)
      }
    }
    ret match {
      case Some(d) => d.toString
      case None => "IMPOSSIBLE"
    }
  }


  def mergePipes(pipes: List[Pipe]) = (Pipe(0, 0) /: pipes)(_ merge _)
}