codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1958.md (13411B)


      1 Source: https://codeforces.com/blog/entry/129483
      2 
      3 We hope you enjoyed the problems! Thank you for participation.
      4 
      5 The authors are the usual suspects: [Neon](/profile/Neon "Candidate Master Neon"), [awoo](/profile/awoo "Master awoo"), [adedalic](/profile/adedalic "International Master adedalic"), [Roms](/profile/Roms "Master Roms") and me. Huge thanks to the testers: [shnirelman](/profile/shnirelman "International Grandmaster shnirelman"), [KIRIJIJI](/profile/KIRIJIJI "Candidate Master KIRIJIJI"), [soup](/profile/soup "Expert soup"), [Optoed](/profile/Optoed "Pupil Optoed"), [le.mur](/profile/le.mur "Pupil le.mur"), and the MVP tester [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"). Without your insights, this round would be impossible!
      6 
      7 [1958A - 1-3-5](/contest/1958/problem/A "Kotlin Heroes: Episode 10")
      8 
      9 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 **Solution (PavelKunyavskiy)**
     16 
     17 ```
     18 fun main() {
     19     val ans = IntArray(101) { Int.MAX_VALUE }
     20     ans[0] = 0
     21     for (i in ans.indices) {
     22         for ((d, c) in listOf(1 to 1, 3 to 0, 5 to 0)) {
     23             if (i + d in ans.indices) ans[i + d] = minOf(ans[i + d], ans[i] + c)
     24         }
     25     }
     26     repeat(readInt()) {
     27         println(ans[readInt()])
     28     }
     29 }
     30 
     31 private fun readInt() = readln().toInt()
     32 private fun readLongs() = readStrings().map { it.toLong() }
     33 private fun readStrings() = readln().split(" ")
     34 private fun readInts() = readStrings().map { it.toInt() }
     35 ```
     36 
     37 [1958B - Clock in the Pool](/contest/1958/problem/B "Kotlin Heroes: Episode 10")
     38 
     39 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (PavelKunyavskiy)**
     46 
     47 ```
     48 fun main() {
     49     repeat(readInt()) {
     50         val (k, m) = readInts()
     51         println(maxOf(0, 2 * k - (m % (3 * k))))
     52     }
     53 }
     54 
     55 private fun readInt() = readln().toInt()
     56 private fun readLongs() = readStrings().map { it.toLong() }
     57 private fun readStrings() = readln().split(" ")
     58 private fun readInts() = readStrings().map { it.toInt() }
     59 ```
     60 
     61 [1958C - Firewood](/contest/1958/problem/C "Kotlin Heroes: Episode 10")
     62 
     63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (PavelKunyavskiy)**
     70 
     71 ```
     72 fun main() {
     73     repeat(readInt()) {
     74         val (n, k) = readLongs()
     75         println(n - k.countTrailingZeroBits())
     76     }
     77 }
     78 
     79 private fun readInt() = readln().toInt()
     80 private fun readLongs() = readStrings().map { it.toLong() }
     81 private fun readStrings() = readln().split(" ")
     82 private fun readInts() = readStrings().map { it.toInt() }
     83 ```
     84 
     85 [1958D - Staircase](/contest/1958/problem/D "Kotlin Heroes: Episode 10")
     86 
     87 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (PavelKunyavskiy)**
     94 
     95 ```
     96 fun main() {
     97     repeat(readInt()) {
     98         readInt()
     99         val d = mutableListOf(mutableListOf<Long>())
    100         for (i in readLongs()) {
    101             if (i == 0L) {
    102                 d.add(mutableListOf())
    103             } else {
    104                 d.last().add(i)
    105             }
    106         }
    107         println(d.sumOf { l -> 2 * l.sum() - ((l.indices step 2).takeIf { l.size % 2 == 1 }?.maxOfOrNull { l[it] } ?: 0) })
    108     }
    109 }
    110 
    111 private fun readInt() = readln().toInt()
    112 private fun readLongs() = readStrings().map { it.toLong() }
    113 private fun readStrings() = readln().split(" ")
    114 private fun readInts() = readStrings().map { it.toInt() }
    115 ```
    116 
    117 [1958E - Yet Another Permutation Constructive](/contest/1958/problem/E "Kotlin Heroes: Episode 10")
    118 
    119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution (PavelKunyavskiy)**
    126 
    127 ```
    128 private fun solve(): String {
    129     val (n, k) = readInts()
    130     var ans = listOf(n - 1, n)
    131     repeat(k - 1) {
    132         val min = ans.min()
    133         val prevStart = min - ans.size + 1
    134         if (prevStart <= 0) {
    135             return "-1"
    136         }
    137         ans = ans.zip(prevStart .. min).flatMap { (a, b) -> listOf(a, b) }.dropLast(1)
    138     }
    139     ans = (1 until ans.min()) + ans
    140     return ans.joinToString(" ")
    141 }
    142 fun main() {
    143     repeat(readInt()) {
    144         println(solve())
    145     }
    146 }
    147 
    148 private fun readInt() = readln().toInt()
    149 private fun readLongs() = readStrings().map { it.toLong() }
    150 private fun readStrings() = readln().split(" ")
    151 private fun readInts() = readStrings().map { it.toInt() }
    152 ```
    153 
    154 [1958F - Narrow Paths](/contest/1958/problem/F "Kotlin Heroes: Episode 10")
    155 
    156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution (PavelKunyavskiy)**
    163 
    164 ```
    165 private const val MOD =  1000000007
    166 
    167 @JvmInline
    168 @Suppress("NOTHING_TO_INLINE")
    169 private value class ModInt(val x: Int) {
    170     inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
    171     inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
    172     inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
    173     fun power(p_: Int): ModInt {
    174         var a = this
    175         var res = ModInt(1)
    176         var p = p_
    177         while (p != 0) {
    178             if ((p and 1) == 1) res *= a
    179             a *= a
    180             p = p shr 1
    181         }
    182         return res
    183     }
    184 
    185     inline operator fun div(other: ModInt) = this * other.inv()
    186     inline fun inv() = power(MOD - 2)
    187 
    188     companion object {
    189         inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
    190         inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
    191     }
    192 }
    193 
    194 @JvmInline
    195 private value class ModIntArray(val storage:IntArray) {
    196     operator fun get(index: Int) = ModInt(storage[index])
    197     operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
    198     val size get() = storage.size
    199 }
    200 private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })
    201 
    202 private const val COMB_MAX = 400_010
    203 
    204 private val fs = ModIntArray(COMB_MAX) { ModInt(1) }.apply {
    205     for (i in 1 until size) {
    206         set(i, get(i - 1) * ModInt.from(i))
    207     }
    208 }
    209 private val ifs = ModIntArray(COMB_MAX) { fs[it].inv() }
    210 
    211 private fun cnk(n: Int, k: Int) = if (n >= k) fs[n] * ifs[k] * ifs[n - k] else ModInt(0)
    212 
    213 fun main() {
    214     val (n, k) = readInts()
    215     val ans = ModIntArray(n + 1) { ModInt(0) }
    216 
    217     for (diff in -n..n) {
    218         val ways = maxOf(0, diff - 1)
    219         val ll = maxOf(1, diff)
    220         val rr = minOf(n, n - 1 + diff)
    221         ans[ways] += ModInt(maxOf(0, rr - ll)) * cnk(n - diff - 1, k - 2)
    222     }
    223     for (i in 1 until n) {
    224         ans[i] += cnk(n - i - 1, k - 1)
    225     }
    226     for (j in 0 until n - 1) {
    227         ans[n - j - 1] += cnk(j, k - 1)
    228     }
    229     println(ans.storage.joinToString(" "))
    230 }
    231 
    232 private fun readInt() = readln().toInt()
    233 private fun readLongs() = readStrings().map { it.toLong() }
    234 private fun readStrings() = readln().split(" ")
    235 private fun readInts() = readStrings().map { it.toInt() }
    236 ```
    237 
    238 [1958G - Observation Towers](/contest/1958/problem/G "Kotlin Heroes: Episode 10")
    239 
    240 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
    241 
    242 **Tutorial**
    243 
    244 Tutorial is loading...
    245 
    246 **Solution (PavelKunyavskiy)**
    247 
    248 ```
    249 import kotlin.math.abs
    250 import kotlin.math.sign
    251 
    252 fun main() {
    253     readInts()
    254     val x = readInts()
    255     val h = readInts()
    256     val ord = buildList {
    257         for (i in x.indices.sortedBy { x[it] }) {
    258             while (isNotEmpty() && h[i] - h[last()] >= x[i] - x[last()]) {
    259                 removeLast()
    260             }
    261             if (isEmpty() || h[last()] - h[i] <= x[i] - x[last()]) {
    262                 add(i)
    263             }
    264         }
    265     }.map { x[it] to h[it] }
    266 
    267     fun nextAfter(pos: Int) = ord.binarySearch { (x, _) -> if (x >= pos) 1 else -1 }.inv()
    268     fun coverBy(idx: Int, pos: Int) = ord.getOrNull(idx)?.let { (x, h) -> maxOf(0, abs(x - pos) - h) } ?: Int.MAX_VALUE
    269     fun cover(pos: Int): Int {
    270         val a = nextAfter(pos)
    271         return minOf(coverBy(a - 1, pos), coverBy(a, pos))
    272     }
    273 
    274     fun cover2(l: Int, r: Int): Int {
    275         val a = nextAfter((l + r) / 2)
    276         return minOf(maxOf(coverBy(a, l), coverBy(a, r)), maxOf(coverBy(a - 1, l), coverBy(a - 1, r)))
    277     }
    278 
    279     val ans = List(readInt()) {
    280         val (l, r) = readInts()
    281         minOf(
    282             cover(l) + cover(r),
    283             cover2(l, r)
    284         )
    285     }
    286     println(ans.joinToString(" "))
    287 }
    288 
    289 private fun readInt() = readln().toInt()
    290 private fun readLongs() = readStrings().map { it.toLong() }
    291 private fun readStrings() = readln().split(" ")
    292 private fun readInts() = readStrings().map { it.toInt() }
    293 ```
    294 
    295 [1958H - Composite Spells](/contest/1958/problem/H "Kotlin Heroes: Episode 10")
    296 
    297 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
    298 
    299 **Tutorial**
    300 
    301 Tutorial is loading...
    302 
    303 **Solution (Neon)**
    304 
    305 ```
    306 import java.math.BigInteger
    307 
    308 fun main() = repeat(readLine()!!.toInt()) {
    309   val (n, hp) = readLine()!!.split(" ").let { (n, hp) -> n.toInt() to BigInteger(hp) } 
    310   val s = readLine()!!.split(" ").map { BigInteger(it) }
    311   val m = readLine()!!.toInt()
    312   val c = Array(m) { readLine()!!.split(" ").drop(1).map { it.toInt() - 1 } }
    313   val delta = Array(m) { BigInteger.ZERO }
    314   val minDelta = Array(m) { BigInteger.ZERO }
    315   for (i in 0 until m) {
    316     var curHP = BigInteger.ZERO
    317     for (id in c[i]) {
    318       if (id < n) {
    319         curHP += s[id]
    320         minDelta[i] = minOf(minDelta[i], curHP)
    321       } else {
    322         minDelta[i] = minOf(minDelta[i], curHP + minDelta[id - n])
    323         curHP += delta[id - n]
    324       }
    325     }
    326     delta[i] = curHP
    327   }
    328   
    329   fun rec(remHP : BigInteger, idCompSpell : Int) : Int {
    330     var curHP = remHP
    331     for (id in c[idCompSpell]) {
    332       if (id < n) {
    333         curHP += s[id]
    334         if (curHP <= BigInteger.ZERO)
    335           return id + 1
    336       } else {
    337         if (curHP + minDelta[id - n] <= BigInteger.ZERO)
    338           return rec(curHP, id - n)
    339         curHP += delta[id - n]
    340       }
    341     }
    342     return -1
    343   }
    344   
    345   println(rec(hp, m - 1))
    346 }
    347 ```
    348 
    349 [1958I - Equal Trees](/contest/1958/problem/I "Kotlin Heroes: Episode 10")
    350 
    351 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    352 
    353 **Tutorial**
    354 
    355 Tutorial is loading...
    356 
    357 **Solution (PavelKunyavskiy)**
    358 
    359 ```
    360 fun readTree(n: Int) : List<BooleanArray> {
    361     val p = listOf(null) + readInts().map { it - 1 }
    362     return List(n) { a -> BooleanArray(n) { b -> a in generateSequence(b) { p[it] } } }
    363 }
    364 fun main() {
    365     val n = readInt()
    366     val t1 = readTree(n)
    367     val t2 = readTree(n)
    368     val masks = LongArray(n) { a ->
    369         (0 until n).filter { b -> a != b && t1[a][b] == t2[a][b] && t1[b][a] == t2[b][a] }.sumOf { 1L shl it }
    370     }
    371     val data = mutableMapOf<Long, Int>()
    372     data[0] = 0
    373     fun compute(mask: Long) : Int = data.getOrPut(mask) {
    374         val index = mask.countTrailingZeroBits()
    375         maxOf(compute(mask xor (1L shl index)), compute(mask and masks[index]) + 1)
    376     }
    377     println(2 * (n - compute((1L shl n) - 1)))
    378 }
    379 
    380 private fun readInt() = readln().toInt()
    381 private fun readLongs() = readStrings().map { it.toLong() }
    382 private fun readStrings() = readln().split(" ")
    383 private fun readInts() = readStrings().map { it.toInt() }
    384 ```
    385 
    386 [1958J - Necromancer](/contest/1958/problem/J "Kotlin Heroes: Episode 10")
    387 
    388 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    389 
    390 **Tutorial**
    391 
    392 Tutorial is loading...
    393 
    394 **Solution (Neon)**
    395 
    396 ```
    397 const val M = 1000
    398 const val K = 10
    399 
    400 fun main() {  
    401   val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    402   val a = readLine()!!.split(" ").map { it.toInt() }
    403   val b = readLine()!!.split(" ").map { it.toInt() }
    404   val l = IntArray(q)
    405   val r = IntArray(q)
    406   for (i in 0 until q) {
    407     val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1}
    408     l[i] = x
    409     r[i] = y
    410   }
    411   val s = b.scan(0, Int::plus)
    412   val ev = Array(n) { mutableListOf<Int>() }
    413   for (i in 0 until n) {
    414     for (j in 1 until K) {
    415       val x = s[i] - (a[i] + j - 1) / j + 1
    416       val pos = s.binarySearch { if (it < x) -1 else 1 }.inv()
    417       if (pos < i) ev[pos].add(i)
    418     }
    419   }
    420   val qr = Array(n) { mutableListOf<Int>() }
    421   for (i in 0 until q) qr[l[i]].add(i)
    422   val f = IntArray(n) { 0 }
    423   fun inc(i : Int) = generateSequence(i) { (it or (it + 1)).takeIf { it < n } }.forEach { ++f[it] }
    424   fun sum(i : Int) = generateSequence(i) { ((it and (it + 1)) - 1).takeIf { it >= 0 } }.sumOf { f[it] }
    425   for (i in 0 until n) inc(i)
    426   val ans = IntArray(q) { 0 }
    427   for (i in 0 until n) {
    428     for (j in ev[i]) inc(j)
    429     for (j in qr[i]) {
    430       var cur = b[l[j]]
    431       for (x in 1 until M.coerceAtMost(r[j] - l[j] + 1)) {
    432         ans[j] += (a[l[j] + x] + cur - 1) / cur
    433         cur += b[l[j] + x]
    434       }
    435       if (l[j] + M <= r[j]) ans[j] += sum(r[j]) - sum(l[j] + M - 1)
    436     }
    437   }
    438   println(ans.joinToString("\n"))
    439 }
    440 ```