fork download
copy 
  1. object Main {
  2.  
  3.   def main(args: Array[String]): Unit = {
  4.     val sum = BigDecimal(Console.readLine()).*(100).toIntExact
  5.     val unitPrices = (0 until 3).map(_ => BigDecimal(Console.readLine()).*(100).toIntExact).filter(_ != 0)
  6.     val dynArray = Array.ofDim[Int](unitPrices.length, sum + 1)
  7.     dynArray.foreach(row => row.indices.foreach(row(_) = -1))
  8.     dynArray.foreach(_(0) = 0)
  9.     for (((row, rowIndex), unitPrice) <- dynArray.zipWithIndex.zip(unitPrices);
  10.           elemIndex <- row.indices) {
  11.       if (elemIndex >= unitPrice) {
  12.         val leftElem = row(elemIndex - unitPrice)
  13.         if (leftElem >= 0) {
  14.           row(elemIndex) = leftElem + 1
  15.         }
  16.       }
  17.       if (rowIndex > 0) {
  18.         val prevElem = dynArray(rowIndex - 1)(elemIndex)
  19.         if (row(elemIndex) < 0 || (prevElem > 0 && prevElem < row(elemIndex))) {
  20.           row(elemIndex) = dynArray(rowIndex - 1)(elemIndex)
  21.         }
  22.       }
  23.     }
  24.     val counts = (0 until unitPrices.length).map(_ => 0).toArray
  25.     var row = unitPrices.length - 1
  26.     var col = sum
  27.     while (col > 0 && dynArray(row)(col) >= 0) {
  28.       val elem = dynArray(row)(col)
  29.       if (row > 0 && elem == dynArray(row - 1)(col)) {
  30.         row -= 1
  31.       } else if (col >= unitPrices(row) && elem == dynArray(row)(col - unitPrices(row)) + 1) {
  32.         counts(row) += 1
  33.         col -= unitPrices(row)
  34.       } else {
  35.         throw new Error
  36.       }
  37.     }
  38.     print(s"$sum = ")
  39.     println(counts.zipWithIndex.map{case(count, index) => s"$count * ${unitPrices(index)}"}.mkString(" + "))
  40.   }
  41. }
  42.  
Success #stdin #stdout 0.62s 382144KB
comments (?)
stdin
copy 
30987
4537
5792
0
stdout
copy 
3098700 = 3 * 453700 + 3 * 579200
https://ideone.com/1AzRnU
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!