Created
February 6, 2013 17:09
-
-
Save redoacs/4724082 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import scala.io.Source | |
import java.io.PrintWriter | |
import scala.collection.mutable.Queue | |
import scala.collection.mutable.BitSet | |
import scala.collection.mutable.Map | |
object findmin extends App { | |
def rfm(j: Int, n: Int, k: Int, m: Queue[Int], mm: Map[Int,Int], csm:BitSet): Int = { | |
if (j==n) m.last | |
else if (j > 2*k){ | |
m += csm.head | |
m( (k+(n-j)-1) % (k+1) ) | |
} | |
else { | |
val min = csm.head | |
val out = m.dequeue | |
m += min | |
csm -= min | |
if (mm.contains(min)) mm.update(min, mm.get(min).get+1) | |
else mm.put(min, 1) | |
val oc = mm.get(out).get | |
if (oc == 1) { | |
csm += out | |
mm.remove(out) | |
} | |
else mm.update(out, oc-1) | |
rfm(j+1, n, k, m , mm, csm) | |
// if (m.contains(out)) rfm(j+1, n, k, m , mm, csm -= min ) | |
// else rfm(j+1, n, k, m , mm, (csm += out) -= min ) | |
} | |
} | |
def complement(m:Queue[Int], k:Int): BitSet = { | |
var c = BitSet.empty | |
for ( i <- k to 0 by -1 ) c += i | |
for ( e <- m ) c -= e | |
c | |
} | |
def genFirstK(k: Int, a: Int, b: Int, c: Int, r: Int): Queue[Int] = { | |
val m = new Array[Int](k) | |
m(0) = a | |
for (val i <- 1 until k) m(i) = ((b.toLong*m(i-1).toLong+c.toLong)%r.toLong).toInt | |
Queue.empty[Int] ++= m | |
} | |
def findMin(n:Int, k:Int, a:Int, b:Int, c:Int, r:Int): Int = { | |
val m = genFirstK(k,a,b,c,r) | |
val mm = Map.empty[Int,Int] ++ m.groupBy(n=>n).mapValues(l => l.length) | |
val csm = complement(m,k) | |
rfm(k,n,k,m,mm,csm) | |
} | |
def consolidate(dp: List[String], acc: List[String]): List[String] = { | |
if (dp.isEmpty) acc | |
else consolidate(dp drop 2, acc :+ dp(0)++" "+dp(1)) | |
} | |
def dispatchSolving(s: String): Long = { | |
val tokens = s.split(' ') map (_.toInt) | |
findMin(tokens(0),tokens(1),tokens(2),tokens(3),tokens(4),tokens(5)) | |
} | |
val input = Source.fromFile("input") | |
val output = new PrintWriter("output") | |
val lines = input.getLines.toList | |
val n = (lines take 1)(0).toInt | |
val problem_strings = lines drop 1 | |
val problems = consolidate(problem_strings,List()) | |
val startTime = System.currentTimeMillis | |
val results = (problems.par map dispatchSolving).toList | |
val elapsedTime = System.currentTimeMillis - startTime | |
println("Elapsed Time: " + elapsedTime/60000 + "m " + (elapsedTime%60000)/1000 + "s " + elapsedTime%1000 + "ms" ); | |
val lp = ( (1 to n).toList,problems,results ).zipped.toList map { case (n, problem, result) => output.println("Case #" + n + ": " + result) } | |
input.close | |
output.close | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment