1170.md (15057B)
1 Source: https://codeforces.com/blog/entry/67280 2 3 [1170A - Three Integers Again](/contest/1170/problem/A "Kotlin Heroes: Episode 1") 4 5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 6 7 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 fun main() { 17 val q = readLine()!!.toInt() 18 repeat(q) { 19 val (x, y) = readLine()!!.split(" ").map { it.toInt() }.sorted() 20 println("1 ${x - 1} ${y - x + 1}") 21 } 22 } 23 ``` 24 25 [1170B - Bad Days](/contest/1170/problem/B "Kotlin Heroes: Episode 1") 26 27 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 28 29 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution** 36 37 ``` 38 fun main() { 39 val n = readLine()!!.toInt() 40 val a = readLine()!!.split(" ").map { it.toInt() } 41 var m1 = 0 42 var m2 = 0 43 var c = 0 44 for (x in a) { 45 if (m2 > x) { 46 c++ 47 } 48 when { 49 x > m1 -> { 50 m2 = m1 51 m1 = x 52 } 53 x > m2 -> { 54 m2 = x 55 } 56 } 57 } 58 println(c) 59 } 60 ``` 61 62 [1170C - Minus and Minus Give Plus](/contest/1170/problem/C "Kotlin Heroes: Episode 1") 63 64 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 65 66 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 67 68 **Tutorial** 69 70 Tutorial is loading... 71 72 **Solution** 73 74 ``` 75 fun main() { 76 val k = readLine()!!.toInt() 77 repeat(k) { 78 val s = readLine()!! 79 val t = readLine()!! 80 println(if (solve(s, t)) "YES" else "NO") 81 } 82 } 83 84 private fun solve(s: String, t: String): Boolean { 85 var i = 0 86 var j = 0 87 while (i < s.length && j < t.length) { 88 when (s[i]) { 89 t[j] -> {} 90 '+' -> return false 91 else -> { // '-' -> '+' 92 i++ 93 if (i >= s.length || s[i] != '-') return false 94 } 95 } 96 i++ 97 j++ 98 } 99 return i == s.length && j == t.length 100 } 101 ``` 102 103 [1170D - Decoding of Integer Sequences](/contest/1170/problem/D "Kotlin Heroes: Episode 1") 104 105 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 106 107 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 108 109 **Tutorial** 110 111 Tutorial is loading... 112 113 **Solution** 114 115 ``` 116 import java.util.* 117 118 fun main() { 119 val m = readLine()!!.toInt() 120 val b = readLine()!!.split(" ").map { it.toInt() } 121 val n = b.count { it == -1 } 122 val a = Array(n) { ArrayList<Int>() } 123 val ix = LinkedList<Int>((0 until n).toList()) 124 var iter = ix.iterator() 125 for (x in b) { 126 if (!iter.hasNext()) iter = ix.iterator() 127 val i = iter.next() 128 if (x == -1) { 129 iter.remove() 130 } else { 131 a[i].add(x) 132 } 133 } 134 println(n) 135 println(a.joinToString("\n") { 136 "${it.size} ${it.joinToString(" ")}" 137 }) 138 } 139 ``` 140 141 [1170E - Sliding Doors](/contest/1170/problem/E "Kotlin Heroes: Episode 1") 142 143 Idea: [adedalic](/profile/adedalic "International Master adedalic") 144 145 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 146 147 **Tutorial** 148 149 Tutorial is loading... 150 151 **Solution** 152 153 ``` 154 fun main() { 155 val (n, m) = readInts() 156 val a = readInts().toIntArray() 157 val q = readInt() 158 val b = IntArray(4 * a.size) 159 160 fun buildTree(il: Int, ir: Int, p: Int): Int { 161 val s = if (il == ir) { 162 a[il] 163 } else { 164 val im = (il + ir) / 2 165 buildTree(il, im, 2 * p + 1) + buildTree(im + 1, ir, 2 * p + 2) 166 } 167 b[p] = s 168 return s 169 } 170 171 buildTree(0, n - 1, 0) 172 val ans = List(q) { 173 val w = readInts().drop(1) + (m + 1) // sentinel 174 if (solveDoors(n, m, b, w)) "YES" else "NO" 175 }.joinToString("\n") 176 println(ans) 177 } 178 179 private fun solveDoors(n: Int, m: Int, b: IntArray, w: List<Int>): Boolean { 180 var pp = 0 181 var i = 0 182 var rem = 0 183 184 fun queryTree(il: Int, ir: Int, p: Int, i: Int): Int { 185 if (il == i && rem >= b[p]) { 186 rem -= b[p] 187 return ir + 1 188 } 189 if (il == ir) return i 190 val im = (il + ir) / 2 191 if (i > im) return queryTree(im + 1, ir, 2 * p + 2, i) 192 val j = queryTree(il, im,2 * p + 1, i) 193 if (j <= im) return j 194 return queryTree(im + 1, ir,2 * p + 2, im + 1) 195 } 196 197 for (cp in w) { 198 rem = cp - pp - 1 199 i = queryTree(0, n - 1, 0, i) 200 if (i >= n) return true 201 pp = cp 202 } 203 return false 204 } 205 206 private fun readInt() = readLine()!!.toInt() 207 private fun readInts() = readLine()!!.split(" ").map { it.toInt() } 208 ``` 209 210 [1170F - Wheels](/contest/1170/problem/F "Kotlin Heroes: Episode 1") 211 212 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [vovuh](/profile/vovuh "Candidate Master vovuh"), [pashka](/profile/pashka "Grandmaster pashka") 213 214 Solution: [Benq](/profile/Benq "Legendary Grandmaster Benq") 215 216 **Tutorial** 217 218 Tutorial is loading... 219 220 **Solution** 221 222 ``` 223 import java.util.* 224 225 fun next() = readLine()!! 226 fun nextInt() = next().toInt() 227 fun nextInts() = next().split(" ").map { it.toInt() } 228 fun nextLongs() = next().split(" ").map { it.toLong() } 229 230 fun solve() { 231 val (n,m,k) = nextInts() 232 var A = nextLongs() 233 var a = arrayListOf<Long>() 234 a.addAll(A) 235 a.sort() 236 var ans = (1e18).toLong() 237 var ind = 0 238 var above:Long = 0 239 var below:Long = 0 240 for (i in 0..m-1) above += a[i]-a[0] 241 for (i in 0..n-m) { 242 val des = i+(m-1)/2 243 while (ind < des) { // try to get closer to median if possible 244 if (below+(a[ind+1]-a[ind])*(ind+1-i) <= k) { 245 below += (a[ind+1]-a[ind])*(ind+1-i) 246 above -= (a[ind+1]-a[ind])*(i+m-1-ind) // ind+1 to i+m-1 247 ind ++ 248 } else break 249 } 250 assert (k >= below) 251 if (ind < des) { 252 var oops: Long = (k-below)/(ind+1-i) 253 ans = minOf(ans,below+above-(i+m-1-ind)*oops+(ind+1-i)*oops) 254 assert(i+m-1-ind >= ind+1-i) 255 } else ans = minOf(ans,above+below) 256 if (i < n-m) { 257 below -= a[ind]-a[i] 258 above += a[i+m]-a[ind] 259 } 260 } 261 print(ans) 262 } 263 264 fun main(args: Array<String>) { 265 val t = 1 266 for (i in 0..t-1) solve() 267 } 268 ``` 269 270 [1170G - Graph Decomposition](/contest/1170/problem/G "Kotlin Heroes: Episode 1") 271 272 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 273 274 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov") 275 276 **Tutorial** 277 278 Tutorial is loading... 279 280 **Solution** 281 282 ``` 283 fun main() { 284 solveEuler() 285 } 286 287 class E( 288 val y: Int, 289 var c: Int = 0 290 ) 291 292 class Edges { 293 private val e = HashMap<Int, E>(2) 294 private val c = ArrayList<E>(2) 295 private var first = 0 296 297 fun degree() = c.sumBy { it.c } 298 299 fun add(y: Int) { 300 val cur = e.getOrPut(y) { E(y) } 301 if (cur.c == 0) c.add(cur) 302 cur.c++ 303 } 304 305 fun first() = c[first].y 306 307 fun hasNext() = first < c.size 308 309 fun rem(y: Int) { 310 val cur = e.getValue(y) 311 if (--cur.c == 0) { 312 while (first < c.size && c[first].c == 0) first++ 313 } 314 } 315 } 316 317 private fun solveEuler() { 318 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 319 val g = Array(n) { Edges() } 320 repeat(m) { 321 val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 } 322 g[x].add(y) 323 g[y].add(x) 324 } 325 if (!g.all { it.degree() % 2 == 0 }) { 326 println("NO") 327 } else { 328 val c = ArrayList<List<Int>>() 329 var start = 0 330 val v = IntArray(n) { -1 } 331 while (true) { 332 while (start < n && !g[start].hasNext()) start++ 333 if (start >= n) break 334 val list = ArrayList<Int>() 335 var x = start 336 while (true) { 337 v[x] = list.size 338 list.add(x) 339 val y = g[x].first() 340 g[x].rem(y) 341 g[y].rem(x) 342 if (y == start) break 343 if (v[y] >= 0) { 344 val d = list.subList(v[y], list.size) 345 c.add(d.toList()) 346 for (z in d) v[z] = -1 347 d.clear() 348 } 349 x = y 350 } 351 c.add(list) 352 for (z in list) v[z] = -1 353 } 354 println("YES") 355 println(c.size) 356 val ans = c.joinToString("\n") { list -> 357 "${list.size + 1} ${list.joinToString(" ") { (it + 1).toString() }} ${list[0] + 1}" 358 } 359 println(ans) 360 } 361 } 362 ``` 363 364 [1170H - Longest Saw](/contest/1170/problem/H "Kotlin Heroes: Episode 1") 365 366 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 367 368 Solution: [pashka](/profile/pashka "Grandmaster pashka") 369 370 **Tutorial** 371 372 Tutorial is loading... 373 374 **Solution** 375 376 ``` 377 import java.io.BufferedReader 378 import java.io.IOException 379 import java.io.InputStreamReader 380 import java.io.PrintWriter 381 import java.util.* 382 383 /** 384 * @author: pashka 385 */ 386 387 fun solve(a: IntArray): IntArray { 388 val n = a.size 389 var l = 0 390 var r = a.size + 1 391 var best = IntArray(0) 392 while (r > l + 1) { 393 var m = (l + r) / 2 394 val c = IntArray(m) 395 for (i in 0 until m) { 396 if (i % 2 == 0) { 397 c[i] = a[i / 2] 398 } else { 399 c[i] = a[n - m / 2 + i / 2] 400 } 401 } 402 var ok = true 403 for (i in 0 until m - 1) { 404 if (c[i] == c[i + 1]) { 405 ok = false 406 } 407 } 408 if (!ok && m % 2 == 0) { 409 for (i in 0 until m step 2) { 410 val t = c[i] 411 c[i] = c[i + 1] 412 c[i + 1] = t 413 } 414 ok = true 415 for (i in 0 until m - 1) { 416 if (c[i] == c[i + 1]) { 417 ok = false 418 } 419 } 420 } 421 if (ok) { 422 l = m 423 best = c 424 } else { 425 r = m 426 } 427 } 428 return best 429 } 430 431 private fun solveTest() { 432 val n = readLine()!!.toInt() 433 val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray() 434 a.sort() 435 val best1 = solve(a) 436 a.reverse() 437 val best2 = solve(a) 438 val best = if (best1.size > best2.size) best1 else best2 439 println(best.size) 440 println(best.joinToString(" ")) 441 } 442 443 fun main() { 444 val n = readLine()!!.toInt() 445 for (i in 0 until n) { 446 solveTest() 447 } 448 } 449 ``` 450 451 [1170I - Good Subsets](/contest/1170/problem/I "Kotlin Heroes: Episode 1") 452 453 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 454 455 Solution: [pashka](/profile/pashka "Grandmaster pashka") 456 457 **Tutorial** 458 459 Tutorial is loading... 460 461 **Solution** 462 463 ``` 464 import java.io.BufferedReader 465 import java.io.IOException 466 import java.io.InputStreamReader 467 import java.io.PrintWriter 468 import java.util.* 469 470 /** 471 * @author: pashka 472 */ 473 474 val MOD = 998244353L 475 476 internal class SegmentTree(private val size: Int) { 477 478 private val sum = LongArray(4 * size) 479 private val add = LongArray(4 * size) 480 private val mult = LongArray(4 * size) 481 482 public fun add(l: Int, r: Int, c: Long) { 483 add(0, 0, size, l, r, c) 484 } 485 486 private fun add(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) { 487 push(n, ll, rr) 488 if (ll >= l && rr <= r) { 489 add[n] += c 490 sum[n] += c * (rr - ll) 491 add[n] %= MOD 492 sum[n] %= MOD 493 } else if (ll >= r || l >= rr) { 494 return 495 } else { 496 val m = (ll + rr) / 2 497 add(n * 2 + 1, ll, m, l, r, c) 498 add(n * 2 + 2, m, rr, l, r, c) 499 sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD 500 } 501 } 502 503 public fun mult(l: Int, r: Int, c: Long) { 504 mult(0, 0, size, l, r, c) 505 } 506 507 private fun mult(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) { 508 push(n, ll, rr) 509 if (ll >= l && rr <= r) { 510 mult[n] *= c 511 add[n] *= c 512 sum[n] *= c 513 mult[n] %= MOD 514 add[n] %= MOD 515 sum[n] %= MOD 516 } else if (ll >= r || l >= rr) { 517 return 518 } else { 519 val m = (ll + rr) / 2 520 mult(n * 2 + 1, ll, m, l, r, c) 521 mult(n * 2 + 2, m, rr, l, r, c) 522 sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD 523 } 524 } 525 526 private fun push(n: Int, ll: Int, rr: Int) { 527 if (rr - ll > 1) { 528 val m = ll + rr shr 1 529 for (i in 1..2) { 530 mult[2 * n + i] *= mult[n] 531 add[2 * n + i] *= mult[n] 532 sum[2 * n + i] *= mult[n] 533 add[2 * n + i] += add[n] 534 sum[2 * n + i] += add[n] * (if (i == 1) (m - ll) else (rr - m)) 535 mult[2 * n + i] %= MOD 536 add[2 * n + i] %= MOD 537 sum[2 * n + i] %= MOD 538 } 539 } 540 add[n] = 0 541 mult[n] = 1 542 } 543 544 public fun sum(l: Int, r: Int): Long { 545 return sum(0, 0, size, l, r) 546 } 547 548 private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Long { 549 push(n, ll, rr) 550 if (ll >= l && rr <= r) { 551 return sum[n] 552 } else if (ll >= r || l >= rr) { 553 return 0 554 } else { 555 val m = (ll + rr) / 2 556 return (sum(n * 2 + 1, ll, m, l, r) + sum(n * 2 + 2, m, rr, l, r)) % MOD 557 } 558 } 559 } 560 561 private fun solve() { 562 val n = nextInt() 563 val l = IntArray(n) 564 val r = IntArray(n) 565 for (i in 0 until n) { 566 l[i] = nextInt() 567 r[i] = nextInt() 568 } 569 var all = l + r 570 all.sort() 571 var m = 1 572 for (i in 1 until all.size) { 573 if (all[i] != all[m - 1]) { 574 all[m] = all[i] 575 m++ 576 } 577 } 578 all = all.copyOf(m) 579 for (i in 0 until n) { 580 l[i] = all.binarySearch(l[i]) 581 r[i] = all.binarySearch(r[i]) 582 } 583 val c = IntArray(2 * m) 584 for (i in 0 until n) { 585 c[l[i] * 2]++ 586 c[r[i] * 2 + 1]-- 587 } 588 for (i in 1 until 2 * m) { 589 c[i] += c[i - 1] 590 } 591 val q = IntArray(2 * m) 592 var mm = 0 593 for (i in 0 until 2 * m) { 594 if (c[i] > 0) { 595 q[i] = mm 596 mm++ 597 } 598 } 599 m = mm 600 for (i in 0 until n) { 601 l[i] = q[2 * l[i]] 602 r[i] = q[2 * r[i]] 603 } 604 var p = List(n) { x: Int -> x }.sortedBy { x: Int -> r[x] } 605 val st = SegmentTree(m + 1) 606 st.add(0, 1, 1) 607 for (i in p) { 608 st.mult(0, l[i], 2) 609 val x = st.sum(l[i], r[i] + 2) 610 st.add(r[i] + 1, r[i] + 2, x) 611 } 612 out.println(st.sum(m, m + 1)) 613 } 614 615 fun main() { 616 solve() 617 out.close() 618 } 619 620 private var br = BufferedReader(InputStreamReader(System.`in`)) 621 private var st: StringTokenizer? = null 622 private var out = PrintWriter(System.out) 623 624 @Throws(IOException::class) 625 private fun next(): String { 626 while (st == null || !st!!.hasMoreTokens()) { 627 st = StringTokenizer(br.readLine()) 628 } 629 return st!!.nextToken() 630 } 631 632 @Throws(IOException::class) 633 private fun nextInt(): Int { 634 return Integer.parseInt(next()) 635 } 636 ```