Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
when (val n = readLine()!!.toInt()) {
in 0..999 -> println(n)
in 1000..999_499 -> println("${(n + 500) / 1000}K")
else -> println("${(n + 500_000) / 1_000_000}M")
}
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
class M(val a: Int, val b: Int)
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val ms = Array(n) {
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) }
}
var ans = -1
fun check(x: Int) {
if (ms.count { m -> x in m.a..m.b } == 1) ans = x
}
for (m in ms) {
for (d in -1..1) {
check(m.a + d)
check(m.b + d)
}
}
println(ans)
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val s = a.withIndex().sortedByDescending { it.value }
val i = s.indexOfLast { it.value > 0 }
val j = s.indexOfFirst { it.value < 0 }
val c = CharArray(n) { '0' }
for (k in 0 until i) c[s[k].index] = '1'
if (j >= 0 && -s[j].value < s[i].value) {
c[s[i].index] = '1'
c[s[j].index] = '1'
}
val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 }
println(sum)
println(c.joinToString(""))
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }
val s = a.withIndex().sortedByDescending { it.value }
val d = IntArray(n)
var rem = k
for (p in 1 until n) {
val i = s[p - 1].index
val j = s[p].index
d[j] = minOf(a[i] + d[i] - a[j] - 1, rem)
rem -= d[j]
}
val add = rem / n
val ext = rem % n
for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0
println(d.joinToString(" "))
}
}
1297E - Modernization of Treeland
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
// readLine() // skip empty line
solveCase()
}
}
private fun solveCase() {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val gf = IntArray(n) { -1 }
val gy = IntArray(2 * n)
val gn = IntArray(2 * n)
var ec = 0
fun edge(x: Int, y: Int) {
gy[ec] = y
gn[ec] = gf[x]
gf[x] = ec++
}
repeat(n - 1) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
edge(x, y)
edge(y, x)
}
val v = BooleanArray(n)
val q = IntArray(n)
var h = 0
var t = 0
fun enqueue(x: Int) {
q[t++] = x
v[x] = true
}
enqueue(0)
var lc = 1
while (lc < k && h < t) {
val x = q[h++]
var i = gf[x]
var cc = 0
while (i >= 0 && lc < k) {
val y = gy[i]
if (!v[y]) {
enqueue(y)
if (cc++ > 0) lc++
}
i = gn[i]
}
if (x == 0 && cc == 1) lc++
}
if (lc < k) {
println("No")
return
}
println("Yes")
println(v.count { it })
println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() })
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
import java.util.*
fun main() {
repeat(readLine()!!.toInt()) {
// readLine() // skip empty line
solveCase()
}
}
private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> {
override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i)
}
private fun solveCase() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val d = Array(n) { i ->
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) }
}
d.sortBy { it.a }
var t = 0
val w = TreeSet<Mv>()
fun advance(to: Int) {
while (t < to && !w.isEmpty()) {
repeat(minOf(w.size, m)) {
val v = w.first()
v.t = t
w -= v
}
t++
}
t = to
}
for (v in d) {
advance(v.a)
w += v
}
advance(Int.MAX_VALUE)
d.sortBy { it.i }
println(maxOf(0, d.map { it.t - it.b }.max()!!))
println(d.joinToString(" ") { it.t.toString() })
}
Authors: MikeMirzayanov, Stepavly
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
val (m, k) = readLine()!!.split(" ").map { it.toInt() }
val f = factor(m) ?: run {
println(-1)
return
}
val dp = HashMap<Long,Long>()
val dig = IntArray(100_000)
fun count(nd: Int, p: Long = -1): Long {
val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20)
if (nd == 0) return if (e == 0L) 1 else 0
if (p == -1L) dp[e]?.let { return it }
var cnt = 0L
for (d in 1..9) {
dig[nd - 1] = d
val df = factors[d]
for (i in 0..3) f[i] -= df[i]
if (f.all { it >= 0 }) {
val nc = count(nd - 1)
if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt)
cnt += nc
}
for (i in 0..3) f[i] += df[i]
}
dp[e] = cnt
return cnt
}
var num = 1L
var nd = 1
while (count(nd) <= k - num) num += count(nd++)
check(count(nd, k - num) == 1L)
println(dig.take(nd).reversed().joinToString(""))
}
private val pr = listOf(2, 3, 5, 7)
private val factors = Array(10) { factor(it)!! }
private fun factor(m: Int): IntArray? {
val f = IntArray(4)
if (m <= 1) return f
var rem = m
for ((i, p) in pr.withIndex()) {
while (rem % p == 0) {
rem /= p
f[i]++
}
}
return f.takeIf { rem == 1 }
}
Authors: MikeMirzayanov, antontrygubO_o
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
class Ans(val a: String, val m: String)
repeat(readLine()!!.toInt()) {
val s = readLine()!!
val n = s.length
val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) }
dp[0][0] = Ans(s.substring(0, 1), "R")
var best = Ans(s, "")
fun updateBest(p: Ans) {
if (p.a <= best.a) best = p
}
fun updateDP(i: Int, j: Int, p: Ans) {
val cur = dp[i][j]
if (cur == null || p.a < cur.a) dp[i][j] = p
}
for (i in 1 until n) {
for (j in 0 until i) {
val p = dp[i - 1][j] ?: continue
updateDP(i, j, Ans(p.a + s[i], p.m + "R"))
if (j >= i - j) continue
if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B"))
if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i)))
}
}
for (p in dp[n - 1]) if (p != null) updateBest(p)
println(best.m)
}
}
Authors: FieryPhoenix, dragonslayerintraining
Editorial
Tutorial is loading...
Solution (elizarov)
import java.util.*
private class Block(val l: Int, val r: Int) : Comparable<Block> {
fun cover(c: Block) = l <= c.l && r >= c.r
override fun compareTo(other: Block): Int = l.compareTo(other.l)
}
fun main() {
val (n, d) = readLine()!!.split(" ").map { it.toInt() }
val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height
// Segment tree
val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree
val th = IntArray(4 * d) // max height in this segment
tt[0] = true
// Segment tree functions
fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int {
if (tt[i] || b.l <= tl && b.r >= tr) return th[i]
val tm = (tl + tr) / 2
return maxOf(
if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0,
if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0
)
}
fun setLeaf(i: Int, h: Int) {
tt[i] = true
th[i] = h
}
fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) {
if (b.l <= tl && b.r >= tr) return setLeaf(i, h)
val tm = (tl + tr) / 2
val j1 = 2 * i + 1
val j2 = 2 * i + 2
if (tt[i]) { // split node
tt[i] = false
setLeaf(j1, th[i])
setLeaf(j2, th[i])
}
if (b.l <= tm) place(b, h, j1, tl, tm)
if (b.r > tm) place(b, h, j2, tm + 1, tr)
th[i] = maxOf(th[j1], th[j2])
}
// Simulate each incoming block & print answer
var bc = 0
repeat(n) {
val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) }
var maxH = findMax(b, 0, 1, d)
while (true) {
val bs = bh[maxH] ?: break
var floor = bs.floor(b)
if (floor != null && floor.r < b.l) floor = bs.higher(floor)
if (floor == null) floor = bs.first()
check(floor.l <= b.r)
val list = bs.tailSet(floor).takeWhile { it.l <= b.r }
if (!b.cover(list.first()) || !b.cover(list.last())) break
for (c in list) bs -= c // don't use bs.removeAll(list)
bc -= list.size
maxH--
}
val h = maxH + 1
place(b, h, 0, 1, d)
val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } }
bs += b
println(++bc)
}
}