import scala.collection.mutable.ArrayBuffer import scala.math._ object Main { // dp 配列から、辞書順の最小を求める def construct(d: Int, k: Int, dp: Array[Array[Boolean]]): List[Int] = { def rec(money: Int, count: Int, acc: List[Int]): List[Int] = { if (count == 1) { val ret = money :: acc ret.reverse } else { for (i <- (1 to money-1).reverse) { if (dp(count-1)(i)) { val m = money - i if (!acc.contains(m)) { return rec(money - m, count - 1, m :: acc) } } } assert(false) Nil } } rec(d, k, Nil) } def main(args: Array[String]) { val sc = new java.util.Scanner(System.in) val N, D, K = sc.nextInt val dp = Array.ofDim[Boolean](K+1, D+1) // [個数, 合計金額] dp(0)(0) = true for (i <- 1 to N) { // i 円のお菓子 // i 円のお菓子は、ひとつしか購入できないので逆順でループ for (j <- (1 to K).reverse) { // j 個目のお菓子 for (k <- 0 to D) { // 合計で D 円使った if (dp(j-1)(k) && k + i <= D) { dp(j)(k + i) = true } } } } if (dp(K)(D)) { // 辞書順で最小を求める val ans = construct(D, K, dp) println(ans.mkString(" ")) } else { println(-1) } } }