Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import scala.collection.mutable.{ Map => MMap }
- object Solution {
- case class PrefixTrieNode(
- base: Char, // current node
- next: MMap[Char, PrefixTrieNode]) {
- var v: Boolean = false
- }
- class PrefixTrieTree {
- val root: PrefixTrieNode = PrefixTrieNode(
- '\u0000',
- MMap[Char, PrefixTrieNode]())
- val insertMonitor = new AnyRef
- def put(k: String) = {
- var p = root
- for (c <- k) {
- insertMonitor.synchronized {
- if (!p.next.contains(c)) {
- p.next += (c -> PrefixTrieNode(c, MMap[Char, PrefixTrieNode]()))
- }
- }
- p = p.next.get(c).get
- }
- p.v = true
- }
- def next(c: Char, n: PrefixTrieNode): Option[PrefixTrieNode] = n.next.get(c)
- def next(c: Char): Option[PrefixTrieNode] = root.next.get(c)
- def count(s: String) = {
- s.toCharArray.foldLeft((0, Array[PrefixTrieNode]().par)) { (l, c) =>
- val n = l._2.flatMap { p =>
- next(c, p)
- }
- next(c) match {
- case Some(v) =>
- if (v.v) {
- (l._1 + n.count(_.v) + 1, n :+ v)
- } else {
- (l._1 + n.count(_.v), n :+ v)
- }
- case None =>
- (l._1 + n.count(_.v), n)
- }
- }._1
- }
- }
- def main(args: Array[String]) {
- val bi1 = scala.math.BigInt.long2bigInt(1)
- val r = new PrefixTrieTree()
- r.put("1".toString);
- (0 to 800).par.foldLeft(bi1) { (l, c) => val v = l * 2; r.put(v.toString); v }
- (1 to Console.in.readLine().toInt).map { i =>
- (Console.in.readLine(), i)
- }.par.map { e =>
- (e._2, r.count(e._1))
- }.toArray.sortWith(_._1 < _._1).map(_._2).foreach { v =>
- println(v)
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement