↵
The problems were prepared by
↵
Задачи вместе со мной готовили [user:Neon,2026-03-03], [user:adedalic,2026-03-03]
↵
Huge shoutout to the testers
↵
Я хотел бы поблагодарить тестеров: [user:awoo,2026-03-03], [user:FelixArg,2026-03-03]
↵
Now, the editorial inself
↵
Теперь сам разбор:↵
↵
[problem:2199A]↵
↵
↵
<spoiler summary="
[tutorial:2199A]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
fun main() {↵
val t = readLine()!!.toInt()↵
repeat(t) {↵
val k = readLine()!!.toInt()↵
val (a1, b1) = readLine()!!.split(" ").map { it.toInt() }↵
val (a2, b2) = readLine()!!.split(" ").map { it.toInt() }↵
println(if (a1 - b1 + a2 - b2 >= k) "NO" else "YES")↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199B]↵
↵
↵
<spoiler summary="
[tutorial:2199B]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
fun main() = repeat(readln().toInt()) {↵
var (a, b, c, d) = readln().split(" ").map { it.toInt() }↵
if (a > b) a = b.also { b = a }↵
if (c > d) c = d.also { d = c }↵
println(d - a - maxOf(0, b - c))↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199C]↵
↵
↵
<spoiler summary="
[tutorial:2199C]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
fun printAns(n : Int, pos: MutableList<Int>) {↵
if (n == 0) {↵
println("NO")↵
return↵
}↵
println("YES")↵
println(n)↵
val a = CharArray(n) { '.' }↵
println(a.joinToString(""))↵
for (i in pos) {↵
a[i] = '*'↵
}↵
println(a.joinToString(""))↵
}↵
↵
fun main() = repeat(readln().toInt()) {↵
var k = readln().toInt()↵
if (k == 1) {↵
printAns(1, mutableListOf(0))↵
return@repeat↵
}↵
var n = 0↵
val pos = mutableListOf<Int>()↵
if (k % 5 == 1 || k % 5 == 3) {↵
n += 2↵
pos.add(0)↵
k -= 3↵
}↵
while (k >= 5) {↵
n += 3↵
pos.add(n - 2)↵
k -= 5↵
}↵
if (k % 5 == 3) {↵
n += 2↵
pos.add(n - 1)↵
k -= 3↵
}↵
printAns(if (k == 0) n else 0, pos)↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199D]↵
↵
↵
<spoiler summary="
[tutorial:2199D]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
import java.util.StringTokenizer↵
↵
fun main() {↵
val t = readLine()!!.toInt()↵
repeat(t) {↵
val st = StringTokenizer(readLine())↵
st.nextToken()↵
st.nextToken()↵
↵
val a = readLine()!!.split(" ").map { it.toInt() }↵
val b = readLine()!!.split(" ").map { it.toInt() }↵
↵
val aTrimmed =↵
if (a.size > 1) a.subList(1, a.size - 1) else a↵
val bTrimmed =↵
if (b.size > 1) b.subList(1, b.size - 1) else b↵
↵
val ok = aTrimmed.toSet().intersect(bTrimmed.toSet()).isNotEmpty()↵
println(if (ok) "Yes" else "No")↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199E]↵
↵
↵
<spoiler summary="
[tutorial:2199E]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
import kotlin.math.abs↵
↵
fun main() {↵
val (n, q) = readln().split(" ").map { it.toInt() }↵
val a = readln().split(" ").map { it.toInt() }↵
val xs = readln().split(" ").map { it.toLong() }↵
val bl = IntArray(2 * n - 1) { 1 }↵
for (i in 1 until n) {↵
if (a[i] != a[i - 1]) bl[2 * i - 1] = abs(a[i] - a[i - 1]) - 1↵
}↵
val s = bl.scan(0L) { x, y -> x + y }↵
↵
fun getVal(x : Long) : Int {↵
if (x > s.last()) return -1↵
val i = s.binarySearch { if (it < x) -1 else 1 }.inv() - 1↵
val j = i / 2↵
if (i % 2 == 0) return a[j]↵
if (a[j] == a[j + 1]) return 0↵
val d = (a[j + 1] - a[j]) / abs(a[j + 1] - a[j])↵
return a[j] + d * (x - s[i]).toInt()↵
}↵
↵
println(xs.map { getVal(it) }.joinToString(" "))↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199F]↵
↵
↵
<spoiler summary="
[tutorial:2199F]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
const val MOD = 998244353;↵
↵
fun add(x: Int, y: Int): Int {↵
return ((x + y) % MOD + MOD) % MOD↵
}↵
↵
fun mul(x: Int, y: Int): Int {↵
return (x.toLong() * y % MOD).toInt()↵
}↵
↵
fun main() = repeat(readln().toInt()) {↵
val n = readln().toInt()↵
val a = readln().split(" ").map { it.toInt() }↵
val pw = generateSequence(1, { mul(it, 2) }).take(n + 1).toList()↵
val cnt = a.scan(0) { x, y -> x + if (y == 0) 1 else 0 }↵
val sum = mutableMapOf<Int, Int>()↵
var ans = pw[cnt[n]]↵
for (i in 0 until n) {↵
if (a[i] == 0) continue↵
val cur = sum.getOrDefault(a[i], 0)↵
ans = add(ans, mul(cur, pw[cnt[n] - cnt[i]]))↵
sum[a[i]] = add(cur, pw[cnt[i]]) ↵
}↵
println(ans)↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199G]↵
↵
↵
<spoiler summary="
[tutorial:2199G]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
import kotlin.math.*↵
↵
fun main() {↵
fun isqrt(a : Long) : Long {↵
var s = max(0L, sqrt(a.toDouble()).toLong() - 2)↵
while ((s + 1) * (s + 1) <= a)↵
s++↵
return s↵
}↵
repeat(readln().toInt()) {↵
var (n, m, r) = readln().split(' ').map { it.toLong() }↵
if (n > m)↵
n = m.also { m = n }↵
var ans = 0L↵
for (i in 0..n) {↵
val lf = if (i <= r) 1 + isqrt(r * r - i * i) else max(0L, m - r)↵
val rg = if (n - i <= r) m - 1 - isqrt(r * r - (n - i) * (n - i)) else min(m, r)↵
ans += max(0L, rg - lf + 1)↵
}↵
println(ans)↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199H]↵
↵
↵
<spoiler summary="
[tutorial:2199H]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
import java.util.*↵
↵
const val MOD = 998244353↵
↵
fun add(x: Int, y: Int): Int {↵
var result = x + y↵
while (result >= MOD) result -= MOD↵
while (result < 0) result += MOD↵
return result↵
}↵
↵
fun mul(x: Int, y: Int): Int {↵
return ((x.toLong() * y) % MOD).toInt()↵
}↵
↵
fun solve() {↵
val scanner = Scanner(System.`in`)↵
val n = scanner.nextInt()↵
val a = IntArray(n) { scanner.nextInt() }↵
var k = 0↵
for (i in 0 until n) if (a[i] == -1) k++↵
val ans = Array(k + 1) { IntArray(k + 1) }↵
↵
for (mex in 0..k) {↵
val dp = Array(k + 1) { IntArray(mex + 1) }↵
dp[0][0] = 1↵
for (i in 0 until k) {↵
for (j in 0..mex) {↵
if (dp[i][j] == 0) continue↵
val inc = mex - j↵
val same = n - inc↵
if (inc > 0) {↵
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(inc, dp[i][j]))↵
}↵
dp[i + 1][j] = add(dp[i + 1][j], mul(same, dp[i][j]))↵
}↵
}↵
for (i in 0..k) {↵
ans[mex][i] = dp[i][mex]↵
}↵
}↵
↵
val unusedFirst = mutableSetOf<Int>()↵
val unusedAll = mutableSetOf<Int>()↵
for (i in 0..n) unusedAll.add(i)↵
var cnt = 0↵
for (i in 0 until n) {↵
if (a[i] == -1) {↵
cnt++↵
} else {↵
unusedFirst.remove(a[i])↵
unusedAll.remove(a[i])↵
}↵
while (unusedFirst.size <= cnt) {↵
unusedFirst.add(unusedAll.first())↵
unusedAll.remove(unusedAll.first())↵
}↵
val unused = unusedFirst.toList()↵
var sum = 0↵
for (j in 0..cnt) {↵
sum = add(sum, mul(ans[j][cnt], unused[j]))↵
}↵
print("$sum ")↵
}↵
}↵
↵
fun main() {↵
val t = 1↵
repeat(t) {↵
solve()↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:2199I]↵
↵
↵
<spoiler summary="
[tutorial:2199I]↵
</spoiler>↵
↵
<spoiler summary="
↵
~~~~~↵
import kotlin.math.*↵
import java.util.*↵
↵
const val MOD = 998244353↵
const val K = 7↵
const val A = 50↵
↵
fun add(x: Int, y: Int): Int {↵
var result = x + y↵
while (result >= MOD) result -= MOD↵
while (result < 0) result += MOD↵
return result↵
}↵
↵
fun mul(x: Int, y: Int): Int {↵
return (x.toLong() * y % MOD).toInt()↵
}↵
↵
fun gcd(x: Int, y: Int): Int {↵
return if (x == 0) y else gcd(y % x, x)↵
}↵
↵
fun solve() {↵
val scanner = Scanner(System.`in`)↵
val n = scanner.nextInt()↵
val m = scanner.nextInt()↵
val c = IntArray(m) { scanner.nextInt() }↵
val dist = Array(A + 1) { IntArray(A + 1) }↵
↵
for (i in 1..A) {↵
for (j in 1..A) {↵
var diff = i * j / gcd(i, j) / gcd(i, j)↵
for (k in 2..A) {↵
while (diff % k == 0) {↵
diff /= k↵
dist[i][j]++↵
}↵
}↵
}↵
}↵
↵
val dp = IntArray(1 shl K)↵
dp[0] = 1↵
for (i in 0 until m) {↵
val cur = c[i]↵
val ndp = IntArray(1 shl K)↵
for (j in 0 until (1 shl K)) {↵
var popcount = 0↵
val shifted = (j shl 1) and ((1 shl K) - 1)↵
ndp[shifted] = add(ndp[shifted], dp[j])↵
for (k in 0 until K) {↵
if ((j shr k) and 1 == 1) popcount++↵
}↵
val unused = n - popcount↵
if (unused > 0 && i >= dist[1][cur] - 1) {↵
ndp[shifted + 1] = add(ndp[shifted + 1], mul(unused, dp[j]))↵
}↵
for (k in 0 until K) {↵
if ((j shr k) and 1 == 0) continue↵
val idx = i - k - 1↵
if (idx >= 0 && dist[c[idx]][cur] > k + 1) continue↵
var new_mask = shifted + 1↵
if (k != K - 1) new_mask -= 1 shl (k + 1)↵
ndp[new_mask] = add(ndp[new_mask], dp[j])↵
}↵
}↵
for (k in dp.indices) {↵
dp[k] = ndp[k]↵
}↵
}↵
var ans = 0↵
for (x in dp) ans = add(ans, x)↵
println(ans)↵
}↵
↵
fun main() {↵
val t = 1↵
repeat(t) {↵
solve()↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
