2087.md (15058B)
1 Source: https://codeforces.com/blog/entry/141608 2 3 The contest was prepared by [adedalic](/profile/adedalic "Международный мастер adedalic"), [awoo](/profile/awoo "Мастер awoo"), [Neon](/profile/Neon "Кандидат в мастера Neon") and me. We had a great team of testers: [shnirelman](/profile/shnirelman "Международный гроссмейстер shnirelman"), [ashmelev](/profile/ashmelev "Гроссмейстер ashmelev"), [FelixArg](/profile/FelixArg "Международный мастер FelixArg"), [KIRIJIJI](/profile/KIRIJIJI "Мастер KIRIJIJI"), [Alenochka](/profile/Alenochka "Эксперт Alenochka"), [alyoks1](/profile/alyoks1 "Эксперт alyoks1"), [Vladosiya](/profile/Vladosiya "Кандидат в мастера Vladosiya"), [mariibykova](/profile/mariibykova "Специалист mariibykova") — huge thanks to all of you! 4 5 **One insane moment from the testing phase** 6 7 One day before the contest, [shnirelman](/profile/shnirelman "Международный гроссмейстер shnirelman") completely destroyed problem H in less than 15 minutes. Thankfully, I had an idea of a replacement problem. 8 9 Thanks to all competitors for participation, I hope you enjoyed the problems we made! 10 11 And last but not least, I would like to express my gratitude to [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") for keeping Codeforces and Polygon running even under unprecedented pressure from the bots. 12 13 Okay, now for the editorial itself: 14 15 [2087A - Генератор паролей](/contest/2087/problem/A "Kotlin Heroes: Episode 12") 16 17 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 18 19 **Tutorial** 20 21 Tutorial is loading... 22 23 **Solution (Neon)** 24 25 ``` 26 const val chars = "01ABab" 27 28 fun main() = repeat(readln().toInt()) { 29 val a = readln().split(" ").map { it.toInt() } 30 println(a.mapIndexed { i, x -> 31 CharArray (x) { j -> chars[i * 2 + j % 2] } 32 }.flatMap { it.asIterable() }.joinToString("")) 33 } 34 ``` 35 36 [2087B - Шоу-матч](/contest/2087/problem/B "Kotlin Heroes: Episode 12") 37 38 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution (Neon)** 45 46 ``` 47 fun main() = repeat(readln().toInt()) { 48 val n = readln().toInt() * 2 49 val a = readln().split(" ").map { it.toInt() }.sorted() 50 println(if ((1 until n - 1 step 2).any { i -> 51 a[i + 1] - a[i] < maxOf(a[i] - a[i - 1], a[i + 2] - a[i + 1]) 52 }) "NO" else "YES") 53 } 54 ``` 55 56 [2087C - Игра с монетами](/contest/2087/problem/C "Kotlin Heroes: Episode 12") 57 58 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") 59 60 **Tutorial** 61 62 Tutorial is loading... 63 64 **Solution (Neon)** 65 66 ``` 67 const val coins = "BSG" 68 69 fun main() { 70 val s = readln() 71 val sum = Array(3) { 72 s.map { c -> if (c == coins[it]) 1 else 0 } 73 .scan(0) { x, y -> x + y } 74 } 75 76 val q = readln().toInt() 77 println((0 until q).map { 78 val (l, r) = readln().split(" ").map { it.toInt() } 79 val cnt = sum.map { it[r] - it[l - 1] } 80 cnt.max() + cnt.min() 81 }.joinToString("\n")) 82 } 83 ``` 84 85 [2087D - Заглавные или строчные?](/contest/2087/problem/D "Kotlin Heroes: Episode 12") 86 87 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution (adedalic)** 94 95 ``` 96 import kotlin.system.exitProcess 97 98 fun main() { 99 val (nString, h) = readln().split(" ") 100 101 fun ask(pos: Int): String { 102 println("? ${pos + 1}") 103 System.out.flush() 104 val resp = readln() 105 if (resp == "-1") 106 exitProcess(0) 107 return resp 108 } 109 110 fun isLower(s: String) = s[0].isLowerCase() 111 112 val lowerCaseFirst = isLower(ask(0)) 113 fun lowerOrEqual(a: String, b: String) : Boolean { 114 if (isLower(a) == isLower(b)) 115 return a <= b; 116 return isLower(a) == lowerCaseFirst 117 } 118 var l = 0 119 var r = nString.toInt() 120 while (r - l > 1) { 121 val mid = (l + r) / 2 122 if (lowerOrEqual(ask(mid), h)) 123 l = mid 124 else 125 r = mid 126 } 127 println("! ${l + 1}") 128 } 129 ``` 130 131 [2087E - Раскрась стрелки](/contest/2087/problem/E "Kotlin Heroes: Episode 12") 132 133 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Мастер awoo") 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution (awoo)** 140 141 ``` 142 fun main() = repeat(readLine()!!.toInt()) { 143 val n = readLine()!!.toInt() 144 var s = readLine()!! 145 var a = readLine()!!.split(" ").map { it.toInt() } 146 147 var ans = 0.toLong() 148 149 repeat(2) { 150 var sum = 0.toLong() 151 for (i in 0 until n) { 152 if (s[i] == '<') 153 ans = maxOf(ans, sum + a[i]) 154 sum += maxOf(a[i], 0) 155 } 156 a = a.reversed() 157 s = s.reversed().replace('<', '.').replace('>', '<').replace('.', '>') 158 } 159 160 println(ans) 161 } 162 ``` 163 164 [2087F - Улучшение оружия](/contest/2087/problem/F "Kotlin Heroes: Episode 12") 165 166 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") 167 168 **Tutorial** 169 170 Tutorial is loading... 171 172 **Solution (Neon)** 173 174 ``` 175 const val N = 505 176 const val INF = 1e9.toInt() 177 178 fun main() { 179 val n = readln().toInt() 180 val a = readln().split(" ").map { it.toInt() - 1} 181 val b = readln().split(" ").map { it.toInt() - 1} 182 183 val cnt = Array(N) { IntArray(N) { 0 } } 184 val dp = Array(2) { Array(N) { IntArray(N) { INF } } } 185 dp[0][0][0] = 0 186 187 for (t in 0 until 2 * n) { 188 val ct = t and 1 189 val nt = ct xor 1 190 191 if (t < n) { 192 for (i in 0 until N) for (j in 0 until N) { 193 if (a[t] <= i || b[t] <= j) ++cnt[i][j]; 194 } 195 } 196 197 dp[nt].forEach { it.fill(INF) } 198 for (i in 0 until N) for (j in 0 until N) { 199 if (dp[ct][i][j] != INF) { 200 val lft = minOf(t + 1, n) - i - j 201 if (cnt[i][j] > i + j) { 202 dp[nt][i + 1][j] = minOf(dp[nt][i + 1][j], dp[ct][i][j] + lft - 1) 203 dp[nt][i][j + 1] = minOf(dp[nt][i][j + 1], dp[ct][i][j] + lft - 1) 204 } else { 205 if (t < n || lft == 0) dp[nt][i][j] = minOf(dp[nt][i][j], dp[ct][i][j] + lft) 206 } 207 } 208 } 209 } 210 211 var ans = INF 212 for (i in 0 until N) for (j in 0 until N) ans = minOf(ans, dp[0][i][j]) 213 if (ans == INF) ans = -1 214 println(ans) 215 } 216 ``` 217 218 [2087G - Киберспорт в Берляндии](/contest/2087/problem/G "Kotlin Heroes: Episode 12") 219 220 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution (adedalic)** 227 228 ``` 229 fun main() { 230 data class ModInt(val value : Int = 0) { 231 val MOD = 998244353 232 operator fun plus(oth : ModInt) : ModInt { 233 val cur = (this.value + oth.value) % MOD 234 return ModInt(cur) 235 } 236 operator fun times(oth : ModInt) : ModInt { 237 val cur = value.toLong() * oth.value % MOD 238 return ModInt(cur.toInt()) 239 } 240 fun pow(k: Int) : ModInt { 241 var ans = ModInt(1) 242 var a = ModInt(value) 243 var curPw = k 244 while (curPw > 0) { 245 if (curPw % 2 == 1) 246 ans *= a 247 a *= a 248 curPw /= 2 249 } 250 return ans 251 } 252 fun inverse() = this.pow(MOD - 2) 253 override fun toString() = this.value.toString() 254 } 255 256 val n = readln().toInt() 257 val a = readln().split(" ").map { it.toInt() } 258 259 val factorials = (1..n).runningFold(ModInt(1)) { acc, it -> acc * ModInt(it) } 260 val invFact = factorials.map { it.inverse() } 261 262 fun choose(n : Int, k : Int) : ModInt { 263 if (k < 0 || n < k) 264 return ModInt(0) 265 return factorials[n] * invFact[k] * invFact[n - k] 266 } 267 268 val sum = a.sumOf { it.toLong() } 269 val delta = List(n) { n - it - 1 - a[it] }.sortedDescending() 270 271 var ansVal = sum 272 var ansCnt = ModInt(1) 273 274 var curSum = 0L 275 var lf = 0 276 var rg = 0 277 for (k in 1..n) { 278 curSum += delta[k - 1] 279 while (delta[lf] > delta[k - 1]) 280 lf++ 281 while (rg < delta.size && delta[rg] >= delta[k - 1]) 282 rg++ 283 val curVal = sum + curSum - k.toLong() * (k - 1) / 2 284 val curCnt = choose(rg - lf, k - lf) 285 if (ansVal < curVal) { 286 ansVal = curVal 287 ansCnt = ModInt(0) 288 } 289 if (ansVal == curVal) { 290 ansCnt += curCnt 291 } 292 } 293 println("$ansVal $ansCnt") 294 } 295 ``` 296 297 [2087H - Ним со специальными числами](/contest/2087/problem/H "Kotlin Heroes: Episode 12") 298 299 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 300 301 **Tutorial** 302 303 Tutorial is loading... 304 305 **Solution (BledDest)** 306 307 ``` 308 import java.util.* 309 310 data class Node(var x: Int = 0, var a: Int = 0, var b: Int = 0) 311 312 fun get(n: Node, x: Int): Int { 313 return when { 314 n.x == -1 -> x 315 x < n.x -> n.a 316 else -> n.b 317 } 318 } 319 320 fun combine(a: Node, b: Node): Node { 321 return when { 322 a.x == -1 -> b 323 b.x == -1 -> a 324 else -> Node(a.x, get(b, a.a), get(b, a.b)) 325 } 326 } 327 328 fun emptyNode(): Node { 329 return Node(-1, -1, -1) 330 } 331 332 fun fromLength(len: Int): Node { 333 return if (len == -1) emptyNode() else Node(len, len, len - 1) 334 } 335 336 const val N = 300003 337 const val M = 300001 338 339 val S = sortedSetOf<Int>() 340 val T = Array<Node>(4 * N) { emptyNode() } 341 342 fun recalc(v: Int) { 343 T[v] = combine(T[v * 2 + 1], T[v * 2 + 2]) 344 } 345 346 fun build(v: Int, l: Int, r: Int) { 347 if (l == r - 1) { 348 T[v] = emptyNode() 349 } else { 350 val m = (l + r) / 2 351 build(v * 2 + 1, l, m) 352 build(v * 2 + 2, m, r) 353 recalc(v) 354 } 355 } 356 357 fun upd(v: Int, l: Int, r: Int, pos: Int, x: Int) { 358 if (l == r - 1) { 359 T[v] = fromLength(x) 360 } else { 361 val m = (l + r) / 2 362 if (pos < m) upd(v * 2 + 1, l, m, pos, x) 363 else upd(v * 2 + 2, m, r, pos, x) 364 recalc(v) 365 } 366 } 367 368 fun get(v: Int, l: Int, r: Int, L: Int, R: Int): Node { 369 if (L >= R) return emptyNode() 370 if (L == l && R == r) return T[v] 371 val m = (l + r) / 2 372 return combine(get(v * 2 + 1, l, m, L, minOf(m, R)), get(v * 2 + 2, m, r, maxOf(L, m), R)) 373 } 374 375 fun prepare() { 376 build(0, 0, M) 377 upd(0, 0, M, 0, 0) 378 S.add(0) 379 } 380 381 fun insertValue(x: Int) { 382 val it = S.ceiling(x) 383 if (it != null) { 384 upd(0, 0, M, it, it - x) 385 } 386 S.lower(x)?.let { upd(0, 0, M, x, x - it) } 387 S.add(x) 388 } 389 390 fun eraseValue(x: Int) { 391 upd(0, 0, M, x, -1) 392 S.remove(x) 393 val it = S.ceiling(x) 394 if (it != null) { 395 val y = it 396 S.lower(y)?.let { upd(0, 0, M, y, y - it) } 397 } 398 } 399 400 fun getGrundy(x: Int): Int { 401 val n = get(0, 0, M, 0, x) 402 val it = S.lower(x) 403 val y = it ?: return x 404 val valY = get(n, 0) 405 val dist = x - y 406 return if (dist <= valY) dist - 1 else dist 407 } 408 409 fun main() { 410 val q = readln().toInt() 411 412 prepare() 413 println((0 until q).map { 414 val params = readln().split(" ").map { it.toInt() } 415 val (t, x) = params.take(2) 416 if (t == 1) { 417 if (S.contains(x)) eraseValue(x) else insertValue(x) 418 null 419 } else { 420 val res = params.drop(2).fold(0) { r, y -> r xor getGrundy(y) } 421 if (res == 0) "Second" else "First" 422 } 423 }.filterNotNull().joinToString("\n")) 424 } 425 ``` 426 427 [2087I - Гамильтоново разбиение](/contest/2087/problem/I "Kotlin Heroes: Episode 12") 428 429 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 430 431 **Tutorial** 432 433 Tutorial is loading... 434 435 **Solution (BledDest)** 436 437 ``` 438 fun main() { 439 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 440 val x = IntArray(m) 441 val y = IntArray(m) 442 val edgeId = mutableMapOf<Pair<Int, Int>, Int>() 443 val inDeg = IntArray(n) 444 val outDeg = IntArray(n) 445 446 for (i in 0 until m) { 447 val (xi, yi) = readLine()!!.split(" ").map { it.toInt() } 448 x[i] = xi - 1 449 y[i] = yi - 1 450 edgeId[Pair(x[i], y[i])] = i 451 inDeg[y[i]]++ 452 outDeg[x[i]]++ 453 } 454 455 var c = 0 456 for (i in 0 until n) { 457 c = maxOf(c, inDeg[i], outDeg[i]) 458 } 459 460 val color = Array(n * 2) { IntArray(c) { -1 } } 461 for (i in 0 until m) { 462 val a = x[i] 463 val b = y[i] + n 464 var ca = 0 465 while (color[a][ca] != -1) ca++ 466 var cb = 0 467 while (color[b][cb] != -1) cb++ 468 color[a][ca] = b 469 color[b][cb] = a 470 if (ca != cb) { 471 var cur = b 472 while (cur != -1) { 473 val temp = color[cur][cb] 474 color[cur][cb] = color[cur][ca] 475 color[cur][ca] = temp 476 cur = color[cur][cb] 477 val tempCa = ca 478 ca = cb 479 cb = tempCa 480 } 481 } 482 } 483 484 val ans = MutableList(m) { 0 } 485 for (i in 0 until n) { 486 for (j in 0 until c) { 487 if (color[i][j] != -1) { 488 ans[edgeId[Pair(i, color[i][j] - n)]!!] = j 489 } 490 } 491 } 492 493 val xsAdd = mutableListOf<Int>() 494 val ysAdd = mutableListOf<Int>() 495 var k = 0 496 for (i in 0 until c) { 497 val nxt = IntArray(n) { -1 } 498 val pre = IntArray(n) { -1 } 499 for (j in 0 until m) { 500 if (ans[j] == i) { 501 nxt[x[j]] = y[j] 502 pre[y[j]] = x[j] 503 } 504 } 505 val parts = mutableListOf<Pair<Int, Int>>() 506 for (j in 0 until n) { 507 if (pre[j] == -1) { 508 var l = j 509 var r = j 510 while (nxt[r] != -1) r = nxt[r] 511 parts.add(Pair(l, r)) 512 } 513 } 514 val p = parts.size 515 k += p 516 for (j in 0 until p) { 517 xsAdd.add(parts[j].second) 518 ysAdd.add(parts[(j + 1) % p].first) 519 } 520 for (j in 0 until p) { 521 ans += i 522 } 523 } 524 525 println(k) 526 for (i in 0 until k) { 527 println("${xsAdd[i] + 1} ${ysAdd[i] + 1}") 528 } 529 println(c) 530 for (x in ans) { 531 print("${x + 1} ") 532 } 533 println() 534 } 535 ```