codeforces-scrape

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

2199.md (11109B)


      1 Source: https://codeforces.com/blog/entry/151783
      2 
      3 Thank you for participation! We're still removing cheaters from the ranklist, so the results are not final. But we hope to finish it as soon as possible.
      4 
      5 The problems were prepared by [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [Roms](/profile/Roms "Master Roms") and me.
      6 
      7 Huge shoutout to the testers: [awoo](/profile/awoo "Grandmaster awoo"), [FelixArg](/profile/FelixArg "Master FelixArg") and [KIRIJIJI](/profile/KIRIJIJI "Master KIRIJIJI")! Your feedback helped us immensely.
      8 
      9 Now, the editorial inself:
     10 
     11 [2199A - Game](/contest/2199/problem/A "Kotlin Heroes: Episode 14")
     12 
     13 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     14 
     15 **Tutorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Solution (BledDest)**
     20 
     21 ```
     22 fun main() {
     23     val t = readLine()!!.toInt()
     24     repeat(t) {
     25         val k = readLine()!!.toInt()
     26         val (a1, b1) = readLine()!!.split(" ").map { it.toInt() }
     27         val (a2, b2) = readLine()!!.split(" ").map { it.toInt() }
     28         println(if (a1 - b1 + a2 - b2 >= k) "NO" else "YES")
     29     }
     30 }
     31 ```
     32 
     33 [2199B - Two Towers](/contest/2199/problem/B "Kotlin Heroes: Episode 14")
     34 
     35 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution (Neon)**
     42 
     43 ```
     44 fun main() = repeat(readln().toInt()) {
     45     var (a, b, c, d) = readln().split(" ").map { it.toInt() }
     46     if (a > b) a = b.also { b = a }
     47     if (c > d) c = d.also { d = c }
     48     println(d - a - maxOf(0, b - c))
     49 }
     50 ```
     51 
     52 [2199C - Minesweeper](/contest/2199/problem/C "Kotlin Heroes: Episode 14")
     53 
     54 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution (Neon)**
     61 
     62 ```
     63 fun printAns(n : Int, pos: MutableList<Int>) {
     64     if (n == 0) {
     65         println("NO")
     66         return
     67     }
     68     println("YES")
     69     println(n)
     70     val a = CharArray(n) { '.' }
     71     println(a.joinToString(""))
     72     for (i in pos) {
     73         a[i] = '*'
     74     }
     75     println(a.joinToString(""))
     76 }
     77 
     78 fun main() = repeat(readln().toInt()) {
     79     var k = readln().toInt()
     80     if (k == 1) {
     81         printAns(1, mutableListOf(0))
     82         return@repeat
     83     }
     84     var n = 0
     85     val pos = mutableListOf<Int>()
     86     if (k % 5 == 1 || k % 5 == 3) {
     87         n += 2
     88         pos.add(0)
     89         k -= 3
     90     }
     91     while (k >= 5) {
     92         n += 3
     93         pos.add(n - 2)
     94         k -= 5
     95     }
     96     if (k % 5 == 3) {
     97         n += 2
     98         pos.add(n - 1)
     99         k -= 3
    100     }
    101     printAns(if (k == 0) n else 0, pos)
    102 }
    103 ```
    104 
    105 [2199D - Two Arrays](/contest/2199/problem/D "Kotlin Heroes: Episode 14")
    106 
    107 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
    108 
    109 **Tutorial**
    110 
    111 Tutorial is loading...
    112 
    113 **Solution (Roms)**
    114 
    115 ```
    116 import java.util.StringTokenizer
    117 
    118 fun main() {
    119     val t = readLine()!!.toInt()
    120     repeat(t) {
    121         val st = StringTokenizer(readLine())
    122         st.nextToken()
    123         st.nextToken()
    124 
    125         val a = readLine()!!.split(" ").map { it.toInt() }
    126         val b = readLine()!!.split(" ").map { it.toInt() }
    127 
    128         val aTrimmed =
    129             if (a.size > 1) a.subList(1, a.size - 1) else a
    130         val bTrimmed =
    131             if (b.size > 1) b.subList(1, b.size - 1) else b
    132 
    133         val ok = aTrimmed.toSet().intersect(bTrimmed.toSet()).isNotEmpty()
    134         println(if (ok) "Yes" else "No")
    135     }
    136 }
    137 ```
    138 
    139 [2199E - Supersequence](/contest/2199/problem/E "Kotlin Heroes: Episode 14")
    140 
    141 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution (Neon)**
    148 
    149 ```
    150 import kotlin.math.abs
    151 
    152 fun main() {
    153     val (n, q) = readln().split(" ").map { it.toInt() }
    154     val a = readln().split(" ").map { it.toInt() }
    155     val xs = readln().split(" ").map { it.toLong() }
    156     val bl = IntArray(2 * n - 1) { 1 }
    157     for (i in 1 until n) {
    158         if (a[i] != a[i - 1]) bl[2 * i - 1] = abs(a[i] - a[i - 1]) - 1
    159     }
    160     val s = bl.scan(0L) { x, y -> x + y }
    161     
    162     fun getVal(x : Long) : Int {
    163         if (x > s.last()) return -1
    164         val i = s.binarySearch { if (it < x) -1 else 1 }.inv() - 1
    165         val j = i / 2
    166         if (i % 2 == 0) return a[j]
    167         if (a[j] == a[j + 1]) return 0
    168         val d = (a[j + 1] - a[j]) / abs(a[j + 1] - a[j])
    169         return a[j] + d * (x - s[i]).toInt()
    170     }
    171     
    172     println(xs.map { getVal(it) }.joinToString(" "))
    173 }
    174 ```
    175 
    176 [2199F - Self-Produced Sequences](/contest/2199/problem/F "Kotlin Heroes: Episode 14")
    177 
    178 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution (Neon)**
    185 
    186 ```
    187 const val MOD = 998244353;
    188 
    189 fun add(x: Int, y: Int): Int {
    190     return ((x + y) % MOD + MOD) % MOD
    191 }
    192 
    193 fun mul(x: Int, y: Int): Int {
    194     return (x.toLong() * y % MOD).toInt()
    195 }
    196 
    197 fun main() = repeat(readln().toInt()) {
    198     val n = readln().toInt()
    199     val a = readln().split(" ").map { it.toInt() }
    200     val pw = generateSequence(1, { mul(it, 2) }).take(n + 1).toList()
    201     val cnt = a.scan(0) { x, y -> x + if (y == 0) 1 else 0 }
    202     val sum = mutableMapOf<Int, Int>()
    203     var ans = pw[cnt[n]]
    204     for (i in 0 until n) {
    205         if (a[i] == 0) continue
    206         val cur = sum.getOrDefault(a[i], 0)
    207         ans = add(ans, mul(cur, pw[cnt[n] - cnt[i]]))
    208         sum[a[i]] = add(cur, pw[cnt[i]]) 
    209     }
    210     println(ans)
    211 }
    212 ```
    213 
    214 [2199G - Jammer](/contest/2199/problem/G "Kotlin Heroes: Episode 14")
    215 
    216 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    217 
    218 **Tutorial**
    219 
    220 Tutorial is loading...
    221 
    222 **Solution (adedalic)**
    223 
    224 ```
    225 import kotlin.math.*
    226 
    227 fun main() {
    228     fun isqrt(a : Long) : Long {
    229         var s = max(0L, sqrt(a.toDouble()).toLong() - 2)
    230         while ((s + 1) * (s + 1) <= a)
    231             s++
    232         return s
    233     }
    234     repeat(readln().toInt()) {
    235         var (n, m, r) = readln().split(' ').map { it.toLong() }
    236         if (n > m)
    237             n = m.also { m = n }
    238         var ans = 0L
    239         for (i in 0..n) {
    240             val lf = if (i <= r) 1 + isqrt(r * r - i * i) else max(0L, m - r)
    241             val rg = if (n - i <= r) m - 1 - isqrt(r * r - (n - i) * (n - i)) else min(m, r)
    242             ans += max(0L, rg - lf + 1)
    243         }
    244         println(ans)
    245     }
    246 }
    247 ```
    248 
    249 [2199H - Sum of MEX](/contest/2199/problem/H "Kotlin Heroes: Episode 14")
    250 
    251 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    252 
    253 **Tutorial**
    254 
    255 Tutorial is loading...
    256 
    257 **Solution (BledDest)**
    258 
    259 ```
    260 import java.util.*
    261 
    262 const val MOD = 998244353
    263 
    264 fun add(x: Int, y: Int): Int {
    265     var result = x + y
    266     while (result >= MOD) result -= MOD
    267     while (result < 0) result += MOD
    268     return result
    269 }
    270 
    271 fun mul(x: Int, y: Int): Int {
    272     return ((x.toLong() * y) % MOD).toInt()
    273 }
    274 
    275 fun solve() {
    276     val scanner = Scanner(System.`in`)
    277     val n = scanner.nextInt()
    278     val a = IntArray(n) { scanner.nextInt() }
    279     var k = 0
    280     for (i in 0 until n) if (a[i] == -1) k++
    281     val ans = Array(k + 1) { IntArray(k + 1) }
    282     
    283     for (mex in 0..k) {
    284         val dp = Array(k + 1) { IntArray(mex + 1) }
    285         dp[0][0] = 1
    286         for (i in 0 until k) {
    287             for (j in 0..mex) {
    288                 if (dp[i][j] == 0) continue
    289                 val inc = mex - j
    290                 val same = n - inc
    291                 if (inc > 0) {
    292                     dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(inc, dp[i][j]))
    293                 }
    294                 dp[i + 1][j] = add(dp[i + 1][j], mul(same, dp[i][j]))
    295             }
    296         }
    297         for (i in 0..k) {
    298             ans[mex][i] = dp[i][mex]
    299         }
    300     }
    301 
    302     val unusedFirst = mutableSetOf<Int>()
    303     val unusedAll = mutableSetOf<Int>()
    304     for (i in 0..n) unusedAll.add(i)
    305     var cnt = 0
    306     for (i in 0 until n) {
    307         if (a[i] == -1) {
    308             cnt++
    309         } else {
    310             unusedFirst.remove(a[i])
    311             unusedAll.remove(a[i])
    312         }
    313         while (unusedFirst.size <= cnt) {
    314             unusedFirst.add(unusedAll.first())
    315             unusedAll.remove(unusedAll.first())
    316         }
    317         val unused = unusedFirst.toList()
    318         var sum = 0
    319         for (j in 0..cnt) {
    320             sum = add(sum, mul(ans[j][cnt], unused[j]))
    321         }
    322         print("$sum ")
    323     }
    324 }
    325 
    326 fun main() {
    327     val t = 1
    328     repeat(t) {
    329         solve()
    330     }
    331 }
    332 ```
    333 
    334 [2199I - Strange Process](/contest/2199/problem/I "Kotlin Heroes: Episode 14")
    335 
    336 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    337 
    338 **Tutorial**
    339 
    340 Tutorial is loading...
    341 
    342 **Solution (BledDest)**
    343 
    344 ```
    345 import kotlin.math.*
    346 import java.util.*
    347 
    348 const val MOD = 998244353
    349 const val K = 7
    350 const val A = 50
    351 
    352 fun add(x: Int, y: Int): Int {
    353     var result = x + y
    354     while (result >= MOD) result -= MOD
    355     while (result < 0) result += MOD
    356     return result
    357 }
    358 
    359 fun mul(x: Int, y: Int): Int {
    360     return (x.toLong() * y % MOD).toInt()
    361 }
    362 
    363 fun gcd(x: Int, y: Int): Int {
    364     return if (x == 0) y else gcd(y % x, x)
    365 }
    366 
    367 fun solve() {
    368     val scanner = Scanner(System.`in`)
    369     val n = scanner.nextInt()
    370     val m = scanner.nextInt()
    371     val c = IntArray(m) { scanner.nextInt() }
    372     val dist = Array(A + 1) { IntArray(A + 1) }
    373     
    374     for (i in 1..A) {
    375         for (j in 1..A) {
    376             var diff = i * j / gcd(i, j) / gcd(i, j)
    377             for (k in 2..A) {
    378                 while (diff % k == 0) {
    379                     diff /= k
    380                     dist[i][j]++
    381                 }
    382             }
    383         }
    384     }
    385 
    386     val dp = IntArray(1 shl K)
    387     dp[0] = 1
    388     for (i in 0 until m) {
    389         val cur = c[i]
    390         val ndp = IntArray(1 shl K)
    391         for (j in 0 until (1 shl K)) {
    392             var popcount = 0
    393             val shifted = (j shl 1) and ((1 shl K) - 1)
    394             ndp[shifted] = add(ndp[shifted], dp[j])
    395             for (k in 0 until K) {
    396                 if ((j shr k) and 1 == 1) popcount++
    397             }
    398             val unused = n - popcount
    399             if (unused > 0 && i >= dist[1][cur] - 1) {
    400                 ndp[shifted + 1] = add(ndp[shifted + 1], mul(unused, dp[j]))
    401             }
    402             for (k in 0 until K) {
    403                 if ((j shr k) and 1 == 0) continue
    404                 val idx = i - k - 1
    405                 if (idx >= 0 && dist[c[idx]][cur] > k + 1) continue
    406                 var new_mask = shifted + 1
    407                 if (k != K - 1) new_mask -= 1 shl (k + 1)
    408                 ndp[new_mask] = add(ndp[new_mask], dp[j])
    409             }
    410         }
    411         for (k in dp.indices) {
    412             dp[k] = ndp[k]
    413         }
    414     }
    415     var ans = 0
    416     for (x in dp) ans = add(ans, x)
    417     println(ans)
    418 }
    419 
    420 fun main() {
    421     val t = 1
    422     repeat(t) {
    423         solve()
    424     }
    425 }
    426 ```