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 ```