codeforces-scrape

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

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