import java.math.BigInteger fun main() = contest274b() @OptIn(ExperimentalStdlibApi::class) fun contest274b() = Messiah_contest274b().exec { val d = readLong() fun calcD(initialVelocity: BigInteger): BigInteger { var D = BigInteger.ZERO var currVelocity = initialVelocity while (currVelocity > BigInteger.ZERO) { D += currVelocity currVelocity /= BigInteger.TWO } return D } // 飛距離 D 以上にする最小値 fun lowerBound(key: Long): BigInteger { var ng = (-1).toBigInteger() var ok = Long.MAX_VALUE.toBigInteger() while ((ok - ng).abs() > BigInteger.ONE) { val mid = (ok + ng) / BigInteger.TWO if (calcD(mid) >= key.toBigInteger()) ok = mid else ng = mid } return ok } val lowerBound = lowerBound(d).toLong() fun distances(initialVelocity: Long): Set { val distances = mutableSetOf() var D = 0L var currVelocity = initialVelocity while (currVelocity > 0) { D += currVelocity distances += D currVelocity /= 2 } return distances } val distances = distances(lowerBound) val answer = distances.let { if (d in it) lowerBound else d } println(answer) } // region kokokara template dayo (^o^) @Suppress("MemberVisibilityCanBePrivate", "ClassName", "FunctionName", "PropertyName", "unused") private class Messiah_contest274b(private val separator: String = System.lineSeparator()) { ////////////////////////////////////////////////// // IO ////////////////////////////////////////////////// private val input = System.`in` private val buffer = ByteArray(1024) private var pointer = 0 private var bufferLength = 0 private val sb = StringBuilder() private fun Byte.isPrintable() = this in 33..126 private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte() private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric") private val enableDebugMode = "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv() private fun hasNextByte(): Boolean { return if (pointer < bufferLength) true else { pointer = 0 bufferLength = input.read(buffer) bufferLength > 0 } } private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1 private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ } private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() } private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit fun readString(): String { hasNextOrError() val sb = StringBuilder() var b = readByte() while (b.isPrintable()) { sb.appendCodePoint(b.toInt()) b = readByte() } return sb.toString() } fun readLong(): Long { hasNextOrError() var n = 0L var negative = false var b = readByte() if (b == '-'.toByte()) { negative = true b = readByte() } if (!b.isNumeric()) error("$b is not numeric.") while (true) { when { b.isNumeric() -> n = n * 10 + b.toNumVal() b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n else -> error("failed to parse. [n=$n, b=$b]") } b = readByte() } } fun readInt() = readLong() .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") } fun readIntAsIndex() = readInt().dec() fun readDouble(): Double { var n = 0.0 var div = 1.0 var negative = false var b = readByte() if (b == '-'.toByte()) { negative = true b = readByte() } do n = n * 10 + b.toNumVal() while (run { b = readByte() }.run { b.isNumeric() }) if (b == '.'.toByte()) { while (run { b = readByte() }.run { b.isNumeric() }) n += b.toNumVal() / (run { div *= 10 }.run { div }) } return if (negative) -n else n } fun readString(size: Int): Array = Array(size) { readString() } fun readChars2D(height: Int): Array = Array(height) { readString().toCharArray() } fun readLong(size: Int): LongArray = LongArray(size) { readLong() } fun readLong2D(height: Int, width: Int): Array = Array(height) { LongArray(width) { readLong() } } fun readInt(size: Int): IntArray = IntArray(size) { readInt() } fun readInt2D(height: Int, width: Int): Array = Array(height) { IntArray(width) { readInt() } } fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() } fun readIntAsIndex2D(height: Int, width: Int): Array = Array(height) { IntArray(width) { readIntAsIndex() } } fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() } fun println(): Unit = run { sb.append(separator) } fun print(any: Any): Unit = run { sb.append(any.toString()) } fun println(any: Any): Unit = run { sb.append(any.toString() + separator) } fun flush() = run { kotlin.io.println(sb); sb.clear() } fun debug(any: Any): Unit = run { if (enableDebugMode) System.err.println(any) } fun debug(action: () -> Unit): Unit = run { if (enableDebugMode) action() } fun exec(action: Messiah_contest274b.() -> Unit) { var t: Throwable? = null Thread(null, { action() }, "solve", 128 * 1024 * 1024) .apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } } .apply { start() }.join() t?.let { throw it } kotlin.io.print(sb) } fun readLine(): Nothing = error("readLine is disabled.") ////////////////////////////////////////////////// // Misc ////////////////////////////////////////////////// /** * `[index] in [this]` is sugar syntax of `index in 0 until [this]`. */ operator fun Int.contains(index: Int) = index in this.indices() /** * `[this].indices()` is sugar syntax of `0 until [this]`. */ fun Int.indices() = 0 until this fun YesNo(b: Boolean): String = if (b) Yes else No val Yes = "Yes" val No = "No" fun YES_NO(b: Boolean): String = if (b) YES else NO val YES = "YES" val NO = "NO" } // endregion kokomade template dayo (^o^)