Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package ru.jcorp.coins
- import java.util.Date
- import collection.Set
- import collection.mutable
- object Runner {
- class CoinsCounter(components: Set[Int]) {
- val cache: mutable.Map[Int, Set[Map[Int, Int]]] = mutable.Map()
- var cacheLimit = 0
- def add(map: Map[Int, Int], i: Int): Map[Int, Int] = {
- val option = map.get(i)
- map + (i -> (if (None == option) 1 else option.get + 1))
- }
- def decompose(value: Int) : Set[Map[Int, Int]] = value match {
- case t if (t <= 0) => Set(Map[Int, Int]())
- case t if (cache.contains(t)) => cache(value)
- case _ => {
- def getVariants(subtracted: Int): Set[Map[Int, Int]] = {
- val remain: Int = value - subtracted
- val variants: Set[Map[Int, Int]] = decompose(remain)
- if ((variants.size > 0) && ((cacheLimit > cache.size) || (cacheLimit <= 0)))
- cache.put(remain, variants)
- val result: Set[Map[Int, Int]] = variants.map(variant => add(variant, subtracted))
- result
- }
- val variants: Set[Set[Map[Int, Int]]] = components.map(component => getVariants(component))
- ((Set[Map[Int, Int]]() /: variants)(_ ++ _))
- }
- }
- def setCacheLimit(value : Int) = {
- cacheLimit = value
- this
- }
- def getCacheLimit = cacheLimit
- }
- def main(args: Array[String]) {
- print("Sum: ")
- val sum = readInt()
- print("Coins: ")
- var coins = Set[Int]()
- readLine().split(' ').foreach( f => { coins += f.toInt } )
- print("Cache: ")
- val cacheLimit = readInt()
- println()
- val now = new Date()
- val counts = new CoinsCounter(coins).setCacheLimit(cacheLimit).decompose(sum)
- println("Time: " + (new Date().getTime - now.getTime) + " ms")
- println()
- for {variant <- counts} {
- print(variant)
- println()
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement