codeforces-scrape

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

2141.md (26783B)


      1 Source: https://codeforces.com/blog/entry/146347
      2 
      3 I hope you liked the problems! Thank you for participation. I am sorry that the difference between H and I turned out to be that big, I didn't expect that so many people would solve H.
      4 
      5 The contest was prepared by me, [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [FelixArg](/profile/FelixArg "Master FelixArg") and [Roms](/profile/Roms "Master Roms"). I would like to express my gratitude to the testers who helped us improve the contest: [pashka](/profile/pashka "International Grandmaster pashka"), [shnirelman](/profile/shnirelman "International Grandmaster shnirelman") and [awoo](/profile/awoo "Grandmaster awoo").
      6 
      7 See you in the next episode of Kotlin Heroes... sometime in the future (probably near the end of 2025).
      8 
      9 [2141A - Furniture Store](/contest/2141/problem/A "Kotlin Heroes: Episode 13")
     10 
     11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution (Neon)**
     18 
     19 ```
     20 fun main() = repeat(readln().toInt()) {
     21   val n = readln().toInt()
     22   val a = readln().split(" ").map { it.toInt() }
     23   val p = a.runningReduce { x, y -> minOf(x, y) }
     24   val ans = (1..n).filter { i -> a[i - 1] != p[i - 1] }
     25   println(ans.size)
     26   println(ans.joinToString(" "))    
     27 }
     28 ```
     29 
     30 [2141B - Games](/contest/2141/problem/B "Kotlin Heroes: Episode 13")
     31 
     32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution (Neon)**
     39 
     40 ```
     41 fun main() = repeat(readln().toInt()) {
     42   val (n, m) = readln().split(" ").map { it.toInt() }
     43   val a = readln().split(" ").map { it.toInt() }
     44   val b = readln().split(" ").map { it.toInt() }
     45   val k = a.intersect(b).size
     46   println(2 * minOf(n - k, m - k) + if (n > m) 2 else 1)
     47 }
     48 ```
     49 
     50 [2141C - Minimum on Subarrays](/contest/2141/problem/C "Kotlin Heroes: Episode 13")
     51 
     52 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [FelixArg](/profile/FelixArg "Master FelixArg")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (pashka)**
     59 
     60 ```
     61 @file:Suppress("CanBeVal")
     62 
     63 import java.io.BufferedReader
     64 import java.io.InputStreamReader
     65 import java.io.OutputStreamWriter
     66 import java.io.PrintWriter
     67 import java.util.*
     68 import kotlin.math.max
     69 import kotlin.math.min
     70 
     71 private fun solveTest() {
     72     val n = readInt()
     73     val res = emptyList<String>().toMutableList()
     74     for (i in 0..n - 1) {
     75         if (i % 2 == 0) {
     76             for (j in i..n - 1) {
     77                 res.add("pushfront a[" + j + "]")
     78                 res.add("min")
     79             }
     80             res.add("popback")
     81         } else {
     82             for (j in i..n - 1) {
     83                 res.add("min")
     84                 res.add("popfront")
     85             }
     86         }
     87     }
     88     println(res.size)
     89     for (s in res) {
     90         println(s)
     91     }
     92 }
     93 
     94 private fun solve() {
     95 //    repeat(readInt()) {
     96     solveTest()
     97 //    }
     98 }
     99 
    100 // TEMPLATE
    101 fun main(args: Array<String>) {
    102     reader = BufferedReader(InputStreamReader(System.`in`))
    103     out = PrintWriter(OutputStreamWriter(System.out))
    104     solve()
    105     out.close()
    106 }
    107 
    108 private lateinit var out: PrintWriter
    109 private lateinit var reader: BufferedReader
    110 private var tokenizer: StringTokenizer? = null
    111 private fun read(): String {
    112     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    113         tokenizer = StringTokenizer(readLn())
    114     }
    115     return tokenizer!!.nextToken()
    116 }
    117 
    118 private fun readInt() = read().toInt()
    119 private fun readLong() = read().toLong()
    120 private fun readLn() = reader.readLine()!!
    121 private fun readInts() = readLn().split(" ").map { it.toInt() }
    122 private fun readInts(sz: Int) = Array(sz) { readInt() }
    123 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    124 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    125 private fun print(b: Boolean) = out.print(b)
    126 private fun print(i: Int) = out.print(i)
    127 private fun print(d: Double) = out.print(d)
    128 private fun print(l: Long) = out.print(l)
    129 private fun print(s: String) = out.print(s)
    130 private fun print(message: Any?) = out.print(message)
    131 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    132 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    133 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    134 private fun println(b: Boolean) = out.println(b)
    135 private fun println(i: Int) = out.println(i)
    136 private fun println(d: Double) = out.println(d)
    137 private fun println(l: Long) = out.println(l)
    138 private fun println(s: String) = out.println(s)
    139 private fun println() = out.println()
    140 private fun println(message: Any?) = out.println(message)
    141 private fun <T> println(a: Array<out T>) {
    142     a.forEach { print("$it ") }
    143     println()
    144 }
    145 
    146 private fun println(a: IntArray) {
    147     a.forEach { print("$it ") }
    148     println()
    149 }
    150 
    151 private fun println(a: LongArray) {
    152     a.forEach { print("$it ") }
    153     println()
    154 }
    155 
    156 private fun <T> println(a: Collection<T>) {
    157     a.forEach { print("$it ") }
    158     println()
    159 }
    160 
    161 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    162 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    163 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    164 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
    165 private fun <T> init(vararg elements: T) = elements
    166 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    167 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    168 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    169     return Comparator { a, b ->
    170         val res = a.first.compareTo(b.first)
    171         if (res == 0) a.second.compareTo(b.second) else res
    172     }
    173 }
    174 ```
    175 
    176 [2141D - Avoid Minimums](/contest/2141/problem/D "Kotlin Heroes: Episode 13")
    177 
    178 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution (adedalic)**
    185 
    186 ```
    187 fun main() {
    188     repeat(readln().toInt()) {
    189         val (n, k) = readln().split(' ').map { it.toLong() }
    190         val a = readln().split(' ').map { it.toLong() }
    191         // n * resVal - a.sum() <= k
    192         val resVal = (k + a.sum()) / n
    193         if (resVal < a.maxOrNull()!!) {
    194             println(-1)
    195             return@repeat
    196         }
    197         val minEl = a.minOrNull()!!
    198         var ans = a.sumOf { resVal - it } - (resVal - minEl)
    199         if (minEl < resVal)
    200             ans -= a.count { it == minEl } - 1
    201         println(ans)
    202     }
    203 }
    204 ```
    205 
    206 [2141E - Perfect Cut](/contest/2141/problem/E "Kotlin Heroes: Episode 13")
    207 
    208 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    209 
    210 **Tutorial**
    211 
    212 Tutorial is loading...
    213 
    214 **Solution (Neon)**
    215 
    216 ```
    217 const val MOD = 998244353;
    218 
    219 fun main() = repeat(readln().toInt()) {
    220   val s = readln()
    221   var pw = 1
    222   repeat(s.drop(1).count { it == '?' }) {
    223     pw = pw * 2 % MOD
    224   }
    225   var ans = 0
    226   if (s[0] == '1' || s[0] == '?') {
    227     ans = (ans + pw) % MOD
    228   }
    229   if (s[0] == '0' || s[0] == '?') {
    230     val x = if (s.indexOf('0', 1) == -1) 1 else 0 
    231     ans = (ans + pw - x) % MOD
    232   }
    233   println(ans)
    234 }
    235 ```
    236 
    237 [2141F - Array Reduction](/contest/2141/problem/F "Kotlin Heroes: Episode 13")
    238 
    239 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution (pashka)**
    246 
    247 ```
    248 @file:Suppress("CanBeVal")
    249 
    250 import java.io.BufferedReader
    251 import java.io.InputStreamReader
    252 import java.io.OutputStreamWriter
    253 import java.io.PrintWriter
    254 import java.util.*
    255 import kotlin.math.max
    256 import kotlin.math.min
    257 
    258 private fun solveTest() {
    259     val n = readInt()
    260     val a = readInts(n)
    261     val c = intarr(n)
    262     for (x in a) {
    263         c[x - 1]++
    264     }
    265     val res = intarr(n, Int.MAX_VALUE)
    266     c.sort()
    267     var j = 0
    268     for (k in 0..n) {
    269         while (j < n && c[j] <= k) j++
    270         var s = 0
    271         for (i in j..n) {
    272             val d = k + (n - i)
    273             if (s < n)
    274             res[s] = min(res[s], d)
    275             if (i < n) s += (c[i] - k)
    276         }
    277     }
    278     for (i in 1 .. n - 1) {
    279         res[i] = min(res[i], res[i - 1])
    280     }
    281     println(res)
    282 }
    283 
    284 private fun solve() {
    285     repeat(readInt()) {
    286         solveTest()
    287     }
    288 }
    289 
    290 // TEMPLATE
    291 fun main(args: Array<String>) {
    292     reader = BufferedReader(InputStreamReader(System.`in`))
    293     out = PrintWriter(OutputStreamWriter(System.out))
    294     solve()
    295     out.close()
    296 }
    297 
    298 private lateinit var out: PrintWriter
    299 private lateinit var reader: BufferedReader
    300 private var tokenizer: StringTokenizer? = null
    301 private fun read(): String {
    302     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    303         tokenizer = StringTokenizer(readLn())
    304     }
    305     return tokenizer!!.nextToken()
    306 }
    307 
    308 private fun readInt() = read().toInt()
    309 private fun readLong() = read().toLong()
    310 private fun readLn() = reader.readLine()!!
    311 private fun readInts() = readLn().split(" ").map { it.toInt() }
    312 private fun readInts(sz: Int) = Array(sz) { readInt() }
    313 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    314 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    315 private fun print(b: Boolean) = out.print(b)
    316 private fun print(i: Int) = out.print(i)
    317 private fun print(d: Double) = out.print(d)
    318 private fun print(l: Long) = out.print(l)
    319 private fun print(s: String) = out.print(s)
    320 private fun print(message: Any?) = out.print(message)
    321 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    322 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    323 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    324 private fun println(b: Boolean) = out.println(b)
    325 private fun println(i: Int) = out.println(i)
    326 private fun println(d: Double) = out.println(d)
    327 private fun println(l: Long) = out.println(l)
    328 private fun println(s: String) = out.println(s)
    329 private fun println() = out.println()
    330 private fun println(message: Any?) = out.println(message)
    331 private fun <T> println(a: Array<out T>) {
    332     a.forEach { print("$it ") }
    333     println()
    334 }
    335 
    336 private fun println(a: IntArray) {
    337     a.forEach { print("$it ") }
    338     println()
    339 }
    340 
    341 private fun println(a: LongArray) {
    342     a.forEach { print("$it ") }
    343     println()
    344 }
    345 
    346 private fun <T> println(a: Collection<T>) {
    347     a.forEach { print("$it ") }
    348     println()
    349 }
    350 
    351 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    352 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    353 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    354 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
    355 private fun <T> init(vararg elements: T) = elements
    356 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    357 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    358 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    359     return Comparator { a, b ->
    360         val res = a.first.compareTo(b.first)
    361         if (res == 0) a.second.compareTo(b.second) else res
    362     }
    363 }
    364 ```
    365 
    366 [2141G - Good Robot Paths](/contest/2141/problem/G "Kotlin Heroes: Episode 13")
    367 
    368 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [FelixArg](/profile/FelixArg "Master FelixArg")
    369 
    370 **Tutorial**
    371 
    372 Tutorial is loading...
    373 
    374 **Solution (pashka)**
    375 
    376 ```
    377 @file:Suppress("CanBeVal")
    378 
    379 import java.io.BufferedReader
    380 import java.io.InputStreamReader
    381 import java.io.OutputStreamWriter
    382 import java.io.PrintWriter
    383 import java.util.*
    384 import kotlin.collections.HashMap
    385 import kotlin.math.max
    386 import kotlin.math.min
    387 
    388 private fun solveTest() {
    389     val n = readInt()
    390     val p = TreeMap<Int, MutableList<Int>>()
    391     repeat(n) {
    392         val x = readInt()
    393         val y = readInt()
    394         if (!p.containsKey(y)) {
    395             p[y] = mutableListOf()
    396         }
    397         p[y]!!.add(x)
    398     }
    399     var lastY = Int.MIN_VALUE
    400     var lastD = mutableMapOf<Int, Int>()
    401     var res = 0L
    402     for (y in p.keys) {
    403         if (y != lastY + 1) {
    404             lastD.clear()
    405         }
    406         var d = mutableMapOf<Int, Int>()
    407 
    408         val xx = p[y]!!
    409         xx.sort()
    410 
    411         var lastX = Int.MIN_VALUE
    412         val st = mutableListOf<Pair<Int, Int>>()
    413         var sum1 = 0L
    414         var sum2 = 0L
    415         for (x in xx) {
    416             val dd = lastD.getOrDefault(x, 0) + 1
    417             d[x] = dd
    418 
    419             if (x != lastX + 1) {
    420                 st.clear()
    421                 sum1 = 0
    422                 sum2 = 0
    423             }
    424 
    425             var c = 1
    426             while (st.isNotEmpty() && st.last().first > dd) {
    427                 c += st.last().second
    428                 sum1 -= st.last().first * st.last().second
    429                 st.removeLast()
    430             }
    431             sum1 += c * dd
    432             st.add(dd to c)
    433             sum2++
    434 
    435             res += (sum1 - sum2 - dd + 1) * 4
    436             res += (sum2 - 1) * 2
    437             res += (dd - 1) * 2
    438 //            println("" + y + " " + x + " " + dd + " " + sum1 + " " + sum2 + " " + res)
    439             lastX = x
    440         }
    441 
    442         lastY = y
    443         lastD = d
    444     }
    445     println(res)
    446 }
    447 
    448 private fun solve() {
    449     repeat(readInt()) {
    450         solveTest()
    451     }
    452 }
    453 
    454 // TEMPLATE
    455 fun main(args: Array<String>) {
    456     reader = BufferedReader(InputStreamReader(System.`in`))
    457     out = PrintWriter(OutputStreamWriter(System.out))
    458     solve()
    459     out.close()
    460 }
    461 
    462 private lateinit var out: PrintWriter
    463 private lateinit var reader: BufferedReader
    464 private var tokenizer: StringTokenizer? = null
    465 private fun read(): String {
    466     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    467         tokenizer = StringTokenizer(readLn())
    468     }
    469     return tokenizer!!.nextToken()
    470 }
    471 
    472 private fun readInt() = read().toInt()
    473 private fun readLong() = read().toLong()
    474 private fun readLn() = reader.readLine()!!
    475 private fun readInts() = readLn().split(" ").map { it.toInt() }
    476 private fun readInts(sz: Int) = Array(sz) { readInt() }
    477 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    478 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    479 private fun print(b: Boolean) = out.print(b)
    480 private fun print(i: Int) = out.print(i)
    481 private fun print(d: Double) = out.print(d)
    482 private fun print(l: Long) = out.print(l)
    483 private fun print(s: String) = out.print(s)
    484 private fun print(message: Any?) = out.print(message)
    485 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    486 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    487 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    488 private fun println(b: Boolean) = out.println(b)
    489 private fun println(i: Int) = out.println(i)
    490 private fun println(d: Double) = out.println(d)
    491 private fun println(l: Long) = out.println(l)
    492 private fun println(s: String) = out.println(s)
    493 private fun println() = out.println()
    494 private fun println(message: Any?) = out.println(message)
    495 private fun <T> println(a: Array<out T>) {
    496     a.forEach { print("$it ") }
    497     println()
    498 }
    499 
    500 private fun println(a: IntArray) {
    501     a.forEach { print("$it ") }
    502     println()
    503 }
    504 
    505 private fun println(a: LongArray) {
    506     a.forEach { print("$it ") }
    507     println()
    508 }
    509 
    510 private fun <T> println(a: Collection<T>) {
    511     a.forEach { print("$it ") }
    512     println()
    513 }
    514 
    515 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    516 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    517 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    518 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
    519 private fun <T> init(vararg elements: T) = elements
    520 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    521 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    522 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    523     return Comparator { a, b ->
    524         val res = a.first.compareTo(b.first)
    525         if (res == 0) a.second.compareTo(b.second) else res
    526     }
    527 }
    528 ```
    529 
    530 [2141H - Merging Vertices in a Graph](/contest/2141/problem/H "Kotlin Heroes: Episode 13")
    531 
    532 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    533 
    534 **Tutorial**
    535 
    536 Tutorial is loading...
    537 
    538 **Solution (pashka)**
    539 
    540 ```
    541 @file:Suppress("CanBeVal")
    542 
    543 import java.io.BufferedReader
    544 import java.io.InputStreamReader
    545 import java.io.OutputStreamWriter
    546 import java.io.PrintWriter
    547 import java.util.*
    548 import kotlin.collections.HashMap
    549 import kotlin.math.max
    550 import kotlin.math.min
    551 
    552 private fun solveTest() {
    553     val n = readInt()
    554     val m = readInt()
    555     val g = Array(n) { mutableListOf<Int>() }
    556     repeat(m) {
    557         val x = readInt() - 1
    558         val y = readInt() - 1
    559         g[x].add(y)
    560         g[y].add(x)
    561     }
    562     val z = intarr(n, 0)
    563     var a = (0..n - 1).toMutableSet()
    564     var res = Int.MAX_VALUE
    565 
    566     while (!a.isEmpty()) {
    567         var v = a.iterator().next()
    568         a.remove(v)
    569         z[v] = 1
    570         var s = mutableSetOf<Int>()
    571         for (x in g[v]) {
    572             if (z[x] == 0) s.add(x)
    573         }
    574         var k = 0
    575         while (true) {
    576             var ok = false
    577             for (x in a) {
    578                 if (!s.contains(x) && z[x] == 0) {
    579                     z[x] = 1
    580                     a.remove(x)
    581                     var ss = mutableSetOf<Int>()
    582                     for (y in g[x]) {
    583                         if (z[y] == 0 && s.contains(y)) {
    584                             ss.add(y)
    585                         }
    586                     }
    587                     ok = true
    588                     s = ss
    589                     k++
    590                     break
    591                 }
    592             }
    593             if (!ok) {
    594                 res = min(res, k)
    595                 break
    596             }
    597         }
    598     }
    599 
    600     if (res == 0) {
    601         println("" + res + " " + 0)
    602     } else {
    603         println("" + res + " " + (n - 1))
    604     }
    605 }
    606 
    607 private fun solve() {
    608 //    repeat(readInt()) {
    609         solveTest()
    610 //    }
    611 }
    612 
    613 // TEMPLATE
    614 fun main(args: Array<String>) {
    615     reader = BufferedReader(InputStreamReader(System.`in`))
    616     out = PrintWriter(OutputStreamWriter(System.out))
    617     solve()
    618     out.close()
    619 }
    620 
    621 private lateinit var out: PrintWriter
    622 private lateinit var reader: BufferedReader
    623 private var tokenizer: StringTokenizer? = null
    624 private fun read(): String {
    625     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    626         tokenizer = StringTokenizer(readLn())
    627     }
    628     return tokenizer!!.nextToken()
    629 }
    630 
    631 private fun readInt() = read().toInt()
    632 private fun readLong() = read().toLong()
    633 private fun readLn() = reader.readLine()!!
    634 private fun readInts() = readLn().split(" ").map { it.toInt() }
    635 private fun readInts(sz: Int) = Array(sz) { readInt() }
    636 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    637 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    638 private fun print(b: Boolean) = out.print(b)
    639 private fun print(i: Int) = out.print(i)
    640 private fun print(d: Double) = out.print(d)
    641 private fun print(l: Long) = out.print(l)
    642 private fun print(s: String) = out.print(s)
    643 private fun print(message: Any?) = out.print(message)
    644 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    645 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    646 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    647 private fun println(b: Boolean) = out.println(b)
    648 private fun println(i: Int) = out.println(i)
    649 private fun println(d: Double) = out.println(d)
    650 private fun println(l: Long) = out.println(l)
    651 private fun println(s: String) = out.println(s)
    652 private fun println() = out.println()
    653 private fun println(message: Any?) = out.println(message)
    654 private fun <T> println(a: Array<out T>) {
    655     a.forEach { print("$it ") }
    656     println()
    657 }
    658 
    659 private fun println(a: IntArray) {
    660     a.forEach { print("$it ") }
    661     println()
    662 }
    663 
    664 private fun println(a: LongArray) {
    665     a.forEach { print("$it ") }
    666     println()
    667 }
    668 
    669 private fun <T> println(a: Collection<T>) {
    670     a.forEach { print("$it ") }
    671     println()
    672 }
    673 
    674 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    675 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    676 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    677 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
    678 private fun <T> init(vararg elements: T) = elements
    679 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    680 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    681 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    682     return Comparator { a, b ->
    683         val res = a.first.compareTo(b.first)
    684         if (res == 0) a.second.compareTo(b.second) else res
    685     }
    686 }
    687 ```
    688 
    689 [2141I - Color the Tree](/contest/2141/problem/I "Kotlin Heroes: Episode 13")
    690 
    691 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    692 
    693 **Tutorial**
    694 
    695 Tutorial is loading...
    696 
    697 **Solution (BledDest)**
    698 
    699 ```
    700 import kotlin.math.min
    701 
    702 const val K = 17
    703 const val N = K * 2
    704 const val MOD = 998244353
    705 
    706 fun add(x: Int, y: Int): Int {
    707     return ((x + y) % MOD + MOD) % MOD
    708 }
    709 
    710 fun mul(x: Int, y: Int): Int {
    711     return (x.toLong() * y % MOD).toInt()
    712 }
    713 
    714 fun binpow(x: Int, y: Int): Int {
    715     var z = 1
    716     var base = x
    717     var exponent = y
    718     while (exponent > 0) {
    719         if (exponent % 2 == 1) z = mul(z, base)
    720         base = mul(base, base)
    721         exponent /= 2
    722     }
    723     return z
    724 }
    725 
    726 data class State(
    727     var unpaired: Int = 0,
    728     var unpairedLess: Int = 0,
    729     var pairedLess: Int = 0,
    730     var flag: Int = 0,
    731     var ways: Int = 0
    732 )
    733 
    734 fun comp(a: State, b: State): Boolean {
    735     if (a.unpaired != b.unpaired) return a.unpaired < b.unpaired
    736     if (a.unpairedLess != b.unpairedLess) return a.unpairedLess < b.unpairedLess
    737     if (a.pairedLess != b.pairedLess) return a.pairedLess < b.pairedLess
    738     return a.flag < b.flag
    739 }
    740 
    741 fun fix(v: MutableList<State>) {
    742     v.sortWith(compareBy(State::unpaired).thenBy { it.unpairedLess }.thenBy { it.pairedLess }.thenBy { it.flag })
    743     val v2 = mutableListOf<State>()
    744     for (s in v) {
    745         if (s.ways == 0) continue
    746         if (v2.isEmpty() || comp(v2.last(), s)) {
    747             v2.add(s)
    748         } else {
    749             v2.last().ways = add(v2.last().ways, s.ways)
    750         }
    751     }
    752     v.clear()
    753     v.addAll(v2)
    754 }
    755 
    756 val fact = IntArray(N)
    757 val rfact = IntArray(N)
    758 val g = Array(N) { mutableListOf<Int>() }
    759 val dp = Array(N) { mutableListOf<MutableList<State>>() }
    760 var n = 0
    761 
    762 fun choose(x: Int, y: Int): Int {
    763     return mul(fact[x], mul(rfact[y], rfact[x - y]))
    764 }
    765 
    766 fun merge2(x: MutableList<State>, y: MutableList<State>): MutableList<State> {
    767     val res = mutableListOf<State>()
    768     for (a in x) {
    769         for (b in y) {
    770             for (pairLess in 0..min(a.unpairedLess, b.unpairedLess)) {
    771                 for (pairGreater in 0..min(a.unpaired - a.unpairedLess, b.unpaired - b.unpairedLess)) {
    772                     var numOfChoices = mul(fact[pairLess], fact[pairGreater])
    773                     numOfChoices = mul(numOfChoices, choose(a.unpairedLess, pairLess))
    774                     numOfChoices = mul(numOfChoices, choose(a.unpaired - a.unpairedLess, pairGreater))
    775                     numOfChoices = mul(numOfChoices, choose(b.unpairedLess, pairLess))
    776                     numOfChoices = mul(numOfChoices, choose(b.unpaired - b.unpairedLess, pairGreater))
    777                     numOfChoices = mul(numOfChoices, a.ways)
    778                     numOfChoices = mul(numOfChoices, b.ways)
    779                     var flag = 0
    780                     if (a.unpairedLess > 0 || b.unpairedLess > 0) flag = 1
    781                     if (a.unpairedLess < a.unpaired || b.unpairedLess < b.unpaired) flag = 2
    782                     res.add(State(a.unpaired + b.unpaired - 2 * pairLess - 2 * pairGreater, a.unpairedLess + b.unpairedLess - pairLess * 2, a.pairedLess + b.pairedLess + pairLess, maxOf(flag, a.flag), numOfChoices))
    783                 }
    784             }
    785         }
    786     }
    787     fix(res)
    788     return res
    789 }
    790 
    791 fun merge(a: MutableList<MutableList<State>>, b: MutableList<MutableList<State>>): MutableList<MutableList<State>> {
    792     val res = MutableList(2) { mutableListOf<State>() }
    793     for (i in 0..1) {
    794         for (j in 0..1) {
    795             if (i == 1 && j == 1) continue
    796             val cur = merge2(a[i], b[j])
    797             res[i + j].addAll(cur)
    798         }
    799     }
    800     for (i in 0..1) fix(res[i])
    801     return res
    802 }
    803 
    804 fun getDp(s: MutableList<State>, cntLess: Int, flag: Int): Int {
    805     for (x in s) {
    806         if (x.unpaired == 0 && x.pairedLess == cntLess && x.flag == flag) return x.ways
    807     }
    808     return 0
    809 }
    810 
    811 fun forceSpecial(a: MutableList<MutableList<State>>): MutableList<MutableList<State>> {
    812     val res = MutableList(2) { mutableListOf<State>() }
    813     for (x in a[0]) {
    814         when (x.flag) {
    815             0 -> res[1].add(x)
    816             1 -> {
    817                 res[0].add(x.copy())
    818                 res[1].add(x.copy())
    819             }
    820             else -> res[0].add(x)
    821         }
    822     }
    823     for (x in a[1]) {
    824         res[1].add(x)
    825     }
    826     fix(res[0])
    827     fix(res[1])
    828     return res
    829 }
    830 
    831 fun dfs(v: Int, p: Int) {
    832     val children = mutableListOf<Int>()
    833     for (x in g[v]) {
    834         if (x != p) {
    835             dfs(x, v)
    836             children.add(x)
    837         }
    838     }
    839     if (g[v].size == 1 && v != p) {
    840         val s1 = State(1, 1, 0, 0, 1)
    841         val s2 = State(1, 0, 0, 0, 1)
    842         dp[v] = mutableListOf(mutableListOf(s1, s2), mutableListOf())
    843         fix(dp[v][0])
    844         return
    845     }
    846     var aux = MutableList(2) { mutableListOf<State>() }
    847     aux[0].add(State(0, 0, 0, 0, 1))
    848     for (c in children) {
    849         aux = merge(aux, dp[c])
    850     }
    851     dp[v] = forceSpecial(aux)
    852 }
    853 
    854 fun main() {
    855     val reader = System.`in`.bufferedReader()
    856     n = reader.readLine().toInt()
    857     for (i in 0 until n - 1) {
    858         val (x, y) = reader.readLine().split(" ").map { it.toInt() }
    859         g[x - 1].add(y - 1)
    860         g[y - 1].add(x - 1)
    861     }
    862     val leaves = mutableListOf<Int>()
    863     val nonLeaves = mutableListOf<Int>()
    864     for (i in 0 until n) {
    865         if (g[i].size == 1) leaves.add(i) else nonLeaves.add(i)
    866     }
    867     fact[0] = 1
    868     for (i in 1..n) fact[i] = mul(fact[i - 1], i)
    869     for (i in 0..n) rfact[i] = binpow(fact[i], MOD - 2)
    870     var ans = 0
    871     if (leaves.size % 2 == 0) {
    872         val root = nonLeaves[0]
    873         dfs(root, root)
    874         ans = mul(fact[leaves.size / 2], getDp(dp[root][0], 0, 2))
    875         println("${leaves.size / 2} $ans")
    876     } else {
    877         print("${(leaves.size + 1) / 2} ")
    878         for (x in leaves) {
    879             dfs(x, x)
    880             for (j in 0..leaves.size / 2) {
    881                 val cur = getDp(dp[x][1], j, 0)
    882                 ans = add(ans, mul(cur, mul(fact[j], fact[leaves.size / 2 - j])))
    883             }
    884         }
    885         println(ans)
    886     }
    887 }
    888 ```