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