fork(1) download
  1. import scala.collection._
  2.  
  3. class Bag[E] private (val items: Map[E, Int]) {
  4. def isEmpty = items.isEmpty
  5. def view = items.keys.view
  6. def -(item: E) = new Bag[E](items(item) match {
  7. case 1 => items - item
  8. case n => items.updated(item, n - 1)
  9. })
  10. }
  11.  
  12. object Bag {
  13. def apply[E](items: Traversable[E]): Bag[E] = {
  14. val itemCounts = mutable.HashMap.empty[E, Int].withDefaultValue(0)
  15. items.foreach(itemCounts(_) += 1)
  16. new Bag[E](itemCounts)
  17. }
  18. }
  19.  
  20. object Main extends App {
  21. type Solution = Option[Seq[(String, String)]]
  22.  
  23. def solve(items: Bag[String], anagrams: String, matches: Solution = None): Solution =
  24. if (items.isEmpty) matches
  25. else (for {
  26. item <- items.view
  27. (label, rest) = anagrams.splitAt(item.length)
  28. if item == label.sorted
  29. newMatches = Option(matches.getOrElse(immutable.Queue.empty) :+ (item, label))
  30. solution <- solve(items - item, rest, newMatches)
  31. } yield solution).headOption
  32.  
  33. val items = readLine().split(" ")
  34. val anagrams = readLine()
  35.  
  36. val sortedItems = mutable.Buffer.empty[String]
  37. val itemOrderRestorator = mutable.Map.empty[String, mutable.Queue[String]]
  38.  
  39. for (item <- items) {
  40. val sorted = item.sorted
  41. sortedItems += sorted
  42. itemOrderRestorator.getOrElseUpdate(sorted, new mutable.Queue).enqueue(item)
  43. }
  44.  
  45. solve(Bag(sortedItems), anagrams).map(_.unzip) match {
  46. case None => println("Ne fart")
  47. case Some((items, labels)) =>
  48. println(labels.mkString(" "))
  49. items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
  50. }
  51. }
Success #stdin #stdout 0.46s 382272KB
stdin
abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc
abcabcabcbcabcabcabcabcbcabcabcabcabcbcabcabcabcabcbcabcabcabcabcbcabc
stdout
abc abcabc bca bcabca bca bc bca bcabca bca bc bca bcabca bca bc bca bcabca bca bc bca bc
abc abcabc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc bc