1297.md (11494B)
1 Source: https://codeforces.com/blog/entry/74356 2 3 [1297A - Likes Display](/contest/1297/problem/A "Kotlin Heroes: Episode 3") 4 5 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution (elizarov)** 12 13 ``` 14 fun main() { 15 repeat(readLine()!!.toInt()) { 16 when (val n = readLine()!!.toInt()) { 17 in 0..999 -> println(n) 18 in 1000..999_499 -> println("${(n + 500) / 1000}K") 19 else -> println("${(n + 500_000) / 1_000_000}M") 20 } 21 } 22 } 23 ``` 24 25 [1297B - Cartoons](/contest/1297/problem/B "Kotlin Heroes: Episode 3") 26 27 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 28 29 **Editorial** 30 31 Tutorial is loading... 32 33 **Solution (elizarov)** 34 35 ``` 36 fun main() { 37 class M(val a: Int, val b: Int) 38 repeat(readLine()!!.toInt()) { 39 val n = readLine()!!.toInt() 40 val ms = Array(n) { 41 readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) } 42 } 43 var ans = -1 44 fun check(x: Int) { 45 if (ms.count { m -> x in m.a..m.b } == 1) ans = x 46 } 47 for (m in ms) { 48 for (d in -1..1) { 49 check(m.a + d) 50 check(m.b + d) 51 } 52 } 53 println(ans) 54 } 55 } 56 ``` 57 58 [1297C - Dream Team](/contest/1297/problem/C "Kotlin Heroes: Episode 3") 59 60 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 61 62 **Editorial** 63 64 Tutorial is loading... 65 66 **Solution (elizarov)** 67 68 ``` 69 fun main() { 70 repeat(readLine()!!.toInt()) { 71 val n = readLine()!!.toInt() 72 val a = readLine()!!.split(" ").map { it.toInt() } 73 val s = a.withIndex().sortedByDescending { it.value } 74 val i = s.indexOfLast { it.value > 0 } 75 val j = s.indexOfFirst { it.value < 0 } 76 val c = CharArray(n) { '0' } 77 for (k in 0 until i) c[s[k].index] = '1' 78 if (j >= 0 && -s[j].value < s[i].value) { 79 c[s[i].index] = '1' 80 c[s[j].index] = '1' 81 } 82 val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 } 83 println(sum) 84 println(c.joinToString("")) 85 } 86 } 87 ``` 88 89 [1297D - Bonus Distribution](/contest/1297/problem/D "Kotlin Heroes: Episode 3") 90 91 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 92 93 **Editorial** 94 95 Tutorial is loading... 96 97 **Solution (elizarov)** 98 99 ``` 100 fun main() { 101 repeat(readLine()!!.toInt()) { 102 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 103 val a = readLine()!!.split(" ").map { it.toInt() } 104 val s = a.withIndex().sortedByDescending { it.value } 105 val d = IntArray(n) 106 var rem = k 107 for (p in 1 until n) { 108 val i = s[p - 1].index 109 val j = s[p].index 110 d[j] = minOf(a[i] + d[i] - a[j] - 1, rem) 111 rem -= d[j] 112 } 113 val add = rem / n 114 val ext = rem % n 115 for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0 116 println(d.joinToString(" ")) 117 } 118 } 119 ``` 120 121 [1297E - Modernization of Treeland](/contest/1297/problem/E "Kotlin Heroes: Episode 3") 122 123 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 124 125 **Editorial** 126 127 Tutorial is loading... 128 129 **Solution (elizarov)** 130 131 ``` 132 fun main() { 133 repeat(readLine()!!.toInt()) { 134 // readLine() // skip empty line 135 solveCase() 136 } 137 } 138 139 private fun solveCase() { 140 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 141 val gf = IntArray(n) { -1 } 142 val gy = IntArray(2 * n) 143 val gn = IntArray(2 * n) 144 var ec = 0 145 fun edge(x: Int, y: Int) { 146 gy[ec] = y 147 gn[ec] = gf[x] 148 gf[x] = ec++ 149 } 150 repeat(n - 1) { 151 val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 } 152 edge(x, y) 153 edge(y, x) 154 } 155 val v = BooleanArray(n) 156 val q = IntArray(n) 157 var h = 0 158 var t = 0 159 fun enqueue(x: Int) { 160 q[t++] = x 161 v[x] = true 162 } 163 enqueue(0) 164 var lc = 1 165 while (lc < k && h < t) { 166 val x = q[h++] 167 var i = gf[x] 168 var cc = 0 169 while (i >= 0 && lc < k) { 170 val y = gy[i] 171 if (!v[y]) { 172 enqueue(y) 173 if (cc++ > 0) lc++ 174 } 175 i = gn[i] 176 } 177 if (x == 0 && cc == 1) lc++ 178 } 179 if (lc < k) { 180 println("No") 181 return 182 } 183 println("Yes") 184 println(v.count { it }) 185 println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() }) 186 } 187 ``` 188 189 [1297F - Movie Fan](/contest/1297/problem/F "Kotlin Heroes: Episode 3") 190 191 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 192 193 **Editorial** 194 195 Tutorial is loading... 196 197 **Solution (elizarov)** 198 199 ``` 200 import java.util.* 201 202 fun main() { 203 repeat(readLine()!!.toInt()) { 204 // readLine() // skip empty line 205 solveCase() 206 } 207 } 208 209 private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> { 210 override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i) 211 } 212 213 private fun solveCase() { 214 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 215 val d = Array(n) { i -> 216 readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) } 217 } 218 d.sortBy { it.a } 219 var t = 0 220 val w = TreeSet<Mv>() 221 fun advance(to: Int) { 222 while (t < to && !w.isEmpty()) { 223 repeat(minOf(w.size, m)) { 224 val v = w.first() 225 v.t = t 226 w -= v 227 } 228 t++ 229 } 230 t = to 231 } 232 for (v in d) { 233 advance(v.a) 234 w += v 235 } 236 advance(Int.MAX_VALUE) 237 d.sortBy { it.i } 238 println(maxOf(0, d.map { it.t - it.b }.max()!!)) 239 println(d.joinToString(" ") { it.t.toString() }) 240 } 241 ``` 242 243 [1297G - M-numbers](/contest/1297/problem/G "Kotlin Heroes: Episode 3") 244 245 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 246 247 **Editorial** 248 249 Tutorial is loading... 250 251 **Solution (elizarov)** 252 253 ``` 254 fun main() { 255 val (m, k) = readLine()!!.split(" ").map { it.toInt() } 256 val f = factor(m) ?: run { 257 println(-1) 258 return 259 } 260 val dp = HashMap<Long,Long>() 261 val dig = IntArray(100_000) 262 fun count(nd: Int, p: Long = -1): Long { 263 val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20) 264 if (nd == 0) return if (e == 0L) 1 else 0 265 if (p == -1L) dp[e]?.let { return it } 266 var cnt = 0L 267 for (d in 1..9) { 268 dig[nd - 1] = d 269 val df = factors[d] 270 for (i in 0..3) f[i] -= df[i] 271 if (f.all { it >= 0 }) { 272 val nc = count(nd - 1) 273 if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt) 274 cnt += nc 275 } 276 for (i in 0..3) f[i] += df[i] 277 } 278 dp[e] = cnt 279 return cnt 280 } 281 var num = 1L 282 var nd = 1 283 while (count(nd) <= k - num) num += count(nd++) 284 check(count(nd, k - num) == 1L) 285 println(dig.take(nd).reversed().joinToString("")) 286 } 287 288 private val pr = listOf(2, 3, 5, 7) 289 private val factors = Array(10) { factor(it)!! } 290 291 private fun factor(m: Int): IntArray? { 292 val f = IntArray(4) 293 if (m <= 1) return f 294 var rem = m 295 for ((i, p) in pr.withIndex()) { 296 while (rem % p == 0) { 297 rem /= p 298 f[i]++ 299 } 300 } 301 return f.takeIf { rem == 1 } 302 } 303 ``` 304 305 [1297H - Paint the String](/contest/1297/problem/H "Kotlin Heroes: Episode 3") 306 307 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 308 309 **Editorial** 310 311 Tutorial is loading... 312 313 **Solution (elizarov)** 314 315 ``` 316 fun main() { 317 class Ans(val a: String, val m: String) 318 repeat(readLine()!!.toInt()) { 319 val s = readLine()!! 320 val n = s.length 321 val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) } 322 dp[0][0] = Ans(s.substring(0, 1), "R") 323 var best = Ans(s, "") 324 fun updateBest(p: Ans) { 325 if (p.a <= best.a) best = p 326 } 327 fun updateDP(i: Int, j: Int, p: Ans) { 328 val cur = dp[i][j] 329 if (cur == null || p.a < cur.a) dp[i][j] = p 330 } 331 for (i in 1 until n) { 332 for (j in 0 until i) { 333 val p = dp[i - 1][j] ?: continue 334 updateDP(i, j, Ans(p.a + s[i], p.m + "R")) 335 if (j >= i - j) continue 336 if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B")) 337 if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i))) 338 } 339 } 340 for (p in dp[n - 1]) if (p != null) updateBest(p) 341 println(best.m) 342 } 343 } 344 ``` 345 346 [1297I - Falling Blocks](/contest/1297/problem/I "Kotlin Heroes: Episode 3") 347 348 Authors: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix"), [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 349 350 **Editorial** 351 352 Tutorial is loading... 353 354 **Solution (elizarov)** 355 356 ``` 357 import java.util.* 358 359 private class Block(val l: Int, val r: Int) : Comparable<Block> { 360 fun cover(c: Block) = l <= c.l && r >= c.r 361 override fun compareTo(other: Block): Int = l.compareTo(other.l) 362 } 363 364 fun main() { 365 val (n, d) = readLine()!!.split(" ").map { it.toInt() } 366 val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height 367 // Segment tree 368 val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree 369 val th = IntArray(4 * d) // max height in this segment 370 tt[0] = true 371 // Segment tree functions 372 fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int { 373 if (tt[i] || b.l <= tl && b.r >= tr) return th[i] 374 val tm = (tl + tr) / 2 375 return maxOf( 376 if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0, 377 if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0 378 ) 379 } 380 fun setLeaf(i: Int, h: Int) { 381 tt[i] = true 382 th[i] = h 383 } 384 fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) { 385 if (b.l <= tl && b.r >= tr) return setLeaf(i, h) 386 val tm = (tl + tr) / 2 387 val j1 = 2 * i + 1 388 val j2 = 2 * i + 2 389 if (tt[i]) { // split node 390 tt[i] = false 391 setLeaf(j1, th[i]) 392 setLeaf(j2, th[i]) 393 } 394 if (b.l <= tm) place(b, h, j1, tl, tm) 395 if (b.r > tm) place(b, h, j2, tm + 1, tr) 396 th[i] = maxOf(th[j1], th[j2]) 397 } 398 // Simulate each incoming block & print answer 399 var bc = 0 400 repeat(n) { 401 val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) } 402 var maxH = findMax(b, 0, 1, d) 403 while (true) { 404 val bs = bh[maxH] ?: break 405 var floor = bs.floor(b) 406 if (floor != null && floor.r < b.l) floor = bs.higher(floor) 407 if (floor == null) floor = bs.first() 408 check(floor.l <= b.r) 409 val list = bs.tailSet(floor).takeWhile { it.l <= b.r } 410 if (!b.cover(list.first()) || !b.cover(list.last())) break 411 for (c in list) bs -= c // don't use bs.removeAll(list) 412 bc -= list.size 413 maxH-- 414 } 415 val h = maxH + 1 416 place(b, h, 0, 1, d) 417 val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } } 418 bs += b 419 println(++bc) 420 } 421 } 422 ```