fork download
copy 
  1.  
  2.  
  3. const val MAX_WEIGHT = 100
  4. const val MAX_DP_J = 10000
  5.  
  6. interface Interaction {
  7.     val N: Int
  8.     val dp: List<IntArray>
  9.     fun ask(i: Int, j: Int): Int
  10. }
  11.  
  12. class LocalInteraction() : Interaction {
  13.     override val N: Int = readLine()!!.toInt()
  14.     override val dp: List<IntArray>
  15.     val asked = List(N+1) { BooleanArray(MAX_DP_J + 1) }
  16.     init {
  17.         val W = readLine()!!.split(" ").map{ it.toInt() }
  18.         val P = readLine()!!.split(" ").map{ it.toInt() }
  19.         dp = List(N+1) { IntArray(MAX_DP_J+1) }
  20.         for(i in 0 until N) {
  21.             for(j in 0 .. MAX_DP_J) {
  22.                 if(j < W[i]) dp[i+1][j] = dp[i][j]
  23.                 else dp[i+1][j] = maxOf(dp[i][j],dp[i][j-W[i]]+P[i])
  24.             }
  25.         }
  26.     }
  27.  
  28.     override fun ask(i: Int, j: Int): Int {
  29.         println("asked ${i} ${j} ${if(!asked[i][j]) "for the first time" else "again"}")
  30.         asked[i][j] = true
  31.         return dp[i][j]
  32.     }
  33. }
  34.  
  35. class RealInteraction : Interaction {
  36.     override val N: Int = readLine()!!.toInt()
  37.     override val dp: List<IntArray> = List(N+1) { IntArray(MAX_DP_J+1) { -1 } }
  38.     override fun ask(i: Int, j: Int): Int {
  39.         if(dp[i][j] < 0) {
  40.             println("1 ${i} ${j}")
  41.             dp[i][j] = readLine()!!.toInt()
  42.         }
  43.         return dp[i][j]
  44.     }
  45. }
  46.  
  47. fun binarySearchOnWeight(predicate: (Int) -> Boolean): Int {
  48.     // returns minimum `it` where `predicate(it)` is true
  49.  
  50.     var low = 1
  51.     var high = MAX_WEIGHT
  52.     var ret = -1
  53.     while(low <= high) {
  54.         val mid = (low + high) / 2
  55.         if(predicate(mid)) {
  56.             ret = mid
  57.             high = mid-1
  58.         }else {
  59.             low = mid+1
  60.         }
  61.     }
  62.     return ret
  63. }
  64.  
  65. fun main(args: Array<String>) {
  66.     if(args.isNotEmpty()) {
  67.         System.setIn(java.io.FileInputStream(args[0]))
  68.     }
  69.  
  70.     val interaction = if(args.isNotEmpty()) LocalInteraction() else RealInteraction()
  71.  
  72.     val N = interaction.N
  73.     require(N in 1..100)
  74.  
  75.     val W = IntArray(N+1)
  76.     val P = IntArray(N+1)
  77.  
  78.     // step 1: find W[1], P[1]
  79.     W[1] = binarySearchOnWeight { interaction.ask(1, it) > 0 }
  80.     P[1] = interaction.ask(1, W[1])
  81.  
  82.     // step 2: compute others
  83.     for(i in 2..N) {
  84.         val sumOfProfitsUntilNow = interaction.ask(i, MAX_DP_J)
  85.         P[i] = sumOfProfitsUntilNow - P.slice(1 until i).sum()
  86.  
  87.         val sumOfWeightsBefore = W.slice(1 until i).sum()
  88.         W[i] = binarySearchOnWeight { interaction.ask(i, it + sumOfWeightsBefore) >= sumOfProfitsUntilNow }
  89.     }
  90.  
  91.     println(2)
  92.     println(W.drop(1).toList().joinToString(" "))
  93.     println(P.drop(1).toList().joinToString(" "))
  94. }
Runtime error #stdin #stdout #stderr 0.12s 34060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" kotlin.KotlinNullPointerException
	at RealInteraction.<init>(prog.kt:36)
	at ProgKt.main(prog.kt:70)
https://ideone.com/g36J3r
language:
Kotlin (kotlin 1.3.21)
created:
4 years ago
visibility:
secret

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!