LogSet.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.io.StdIn


case class Num(num:Long, count:Long)

object Main extends App {
    Console.setIn(new FileInputStream("example.in"))

    Console.setIn(new FileInputStream("D-large-practice.in"))
    //Console.setOut(new FileOutputStream("D-large-practice.out"))

    def solve(inputs: Array[Num]):Array[Long] = {
        val inputSet = inputs.map(i => i.num).toSet

        @tailrec
        def removeNum(inputs: Array[Num], num:Long, acc: Array[Num] = Array()): Array[Num] = {
            if (0 == inputs.length) {
                acc
            } else {
                val base = inputs(0)
                val target = inputs.find(_.num == base.num + num).get
                val removedList: Array[Num] = inputs.filter(x => x != base && x != target)
                if (base.count == target.count) {
                    removeNum(removedList, num, acc :+ base)
                } else {
                    removeNum((target.copy(count = target.count - base.count) +: removedList).sortBy(_.num), num, acc :+ base)
                }
            }
        }

        @tailrec
        def absList(inputs: Array[Num], acc: Array[Long] = Array()): Array[Long] = {
            if (1 == inputs.length) {
                Array.fill((Math.log(inputs(0).count) / Math.log(2) + 0.5).toInt)(0L) ++ acc
            } else {
                val num = inputs(1).num - inputs(0).num
                absList(removeNum(inputs, num), acc :+ num)
            }
        }

        val absValues: Array[Long] = absList(inputs)

        @tailrec
        def sums(absValueWithCount: List[(Long, Int)], sumList:Stream[(Long, Array[Long])], target:Long):Stream[(Long, Array[Long])] = {
            if (0 == absValueWithCount.length) {
                sumList
            } else {
                val addValue: (Long, Int) = absValueWithCount.head
                val newValues = (1 to addValue._2).toStream.map(occur => sumList.map(x => (x._1 + addValue._1 * occur, Array.fill(occur)(addValue._1) ++ x._2)))
                val nextSumList = if (!inputSet.contains(-addValue._1)) {
                    newValues.flatten
                } else if (inputSet.contains(addValue._1)) {
                    sumList ++ newValues.flatten
                } else {
                    sumList
                }
                sums(absValueWithCount.tail, nextSumList.filter(x => x._1 <= target && inputSet.contains(x._1)), target)
            }
        }

        val allPositiveSum = inputs.last.num
        val absValueWithCount = absValues.groupBy((x:Long) => x).toList.map({ case (num: Long, nums) => (num, nums.length) })
        val positives = sums(absValueWithCount, Stream((0L, Array[Long]())), allPositiveSum).find(_._1 == allPositiveSum).get

        ((absValues diff positives._2).map(_ * (-1)) ++ positives._2).sorted
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { n => {
        StdIn.readLine()
        val num = StdIn.readLine().split(" ").map(_.toLong)
        val count = StdIn.readLine().split(" ").map(_.toLong)

        val inputs: Array[Num] = (num zip count).map(x => Num(x._1, x._2))
        println(s"Case #$n: ${solve(inputs).mkString(" ")}")
    }}
}