problem A
In Berland, coins of worth 1, 3 and 5 burles are commonly used (burles are local currency).
Eva has to pay exactly 𝑛 burles in a shop. She has an infinite amount of coins of all three types. However, she doesn’t like to pay using coins worth 1 burle — she thinks they are the most convenient to use.
Help Eva to calculate the minimum number of coins worth 1 burle she has to use, if she has to pay exactly 𝑛 burles. Note that she can spend any number of coins worth 3 and/or 5 burles.
Input
The first line contains one integer 𝑡(1≤𝑡≤100) — the number of test cases.
Each test case consists of one line, containing one integer 𝑛(1≤𝑛≤100).
Output
For each test case, print one integer — the minimum number of 1-burle coins Eva has to use.
Example
input
5
7
8
42
2
11
output
1
0
0
2
0
Note
In the first test case, Eva should use 1 coin worth 1 burle, and 2 coins worth 3 burles.
In the second test case, Eva should use 1 coin worth 3 burles and 1 coin worth 5 burles.
In the third test case, Eva should use 14 coins worth 3 burles.
In the fourth test case, Eva should use 2 coins worth 1 burle.
In the fifth test case, Eva should use 2 coins worth 3 burles and 1 coin worth 5 burles.
solution
fun main() {
repeat(readln().toInt()) { println(solve()) }
}
fun solve() = when (readln().toInt()) {
1, 4, 7 -> 1
2 -> 2
else -> 0
}
problem B
You are swimming in the pool, and you need to control the time of swimming.
The pool has a clock that cycles between three different modes: showing water temperature, showing air temperature, and showing time. At the start of the 0-th second it starts showing water temperature, at the start of the 𝑘-th second it switches to air temperature. At the start of the 2𝑘-th second, it switches to showing time.
At the start of the 3𝑘-th second the clock starts showing water temperature again, at the start of the 4𝑘-th second — air temperature, and so on.
You looked at the clock during the 𝑚-th second to check the time, but it may be that the clock is not showing time right now. How much time do you have to wait to see the time on the clock?
Answer 𝑡 independent test cases.
Input
The first line contains a single integer \(𝑡(1≤𝑡≤10^4)\) — the number of test cases. Next 𝑡 cases follow.
The first and only line of each test case contains two integers 𝑘 and 𝑚\((1≤𝑘≤10^8;1≤𝑚≤10^9)\) — the length of the period of the clock and the moment of time you check the clock.
Output
For each test case, print a single integer — the time you have to wait from the moment 𝑚 until the moment the clock starts showing the time.
You can assume that you are able to read the time instantly the moment it displays on the clock.
Example
input
5
1 1
5 14
5 15
10 110
99999999 1000000000
output
1
0
10
0
99999989
Note
In the first test case, the clock will start showing time during the 2-nd second, so you have to wait 2−1=1 second.
In the second test case, the clock shows time from the 10-th until the 15-th second, so during the 14-th second it shows time, and you don’t have to wait.
In the third test case, during the 15-th second, the clock is already showing water temperature. So you have to wait till the 25-th second, when the clock starts showing time again. You’ll wait 25−15=10 seconds.
In the fourth test case, the clock will start showing time at the start of the 110-th second, so you’ll wait 110−110=0 seconds.
solution
fun main() {
repeat(readln().toInt()) { println(solve()) }
}
fun solve(): Int {
var (k, m) = readln().split(' ').map(String::toInt)
m %= 3 * k
return (2 * k - m).coerceAtLeast(0)
}
problem C
It’s pretty cold in Berland (yes, even in May). So Monocarp has to light his fireplace.
Monocarp has a big log of wood, which weighs \(2^𝑛\) grams. Monocarp has watched the weather forecast and decided that he has to burn 𝑘 grams of wood in the fireplace today, and the remaining \(2^𝑛−𝑘\) grams of wood will be used tomorrow.
In one minute, Monocarp can use his saw to split one of his logs in half. Initially he has only one log, but of course, after splitting a log, he gets two new logs. If the weight of the log is 𝑥, then each of the resulting logs has weight equal to \(\tfrac{𝑥}{2}\). Monocarp can’t split logs of weight 1 gram.
Monocarp has to cut his log in such a way that some of the resulting logs weigh exactly 𝑘 grams in total (and since the total weight of wood doesn’t change, the remaining logs will have a total weight equal to exactly \(2^𝑛−𝑘\)). Help him to calculate the minimum number of minutes he has to spend cutting the logs.
Input
The first line contains one integer \(𝑡(1≤𝑡≤10^4)\) — the number of test cases.
Each test case consists of one line containing two integers 𝑛 and 𝑘\((1≤𝑛≤60; 1≤𝑘≤2^𝑛−1)\).
Output
For each test case, print one integer — the minimum number of minutes Monocarp has to spend splitting the wood.
Example
input
4
2 2
2 1
10 3
50 36679020707840
output
1
2
10
16
Note
In the first test case, Monocarp has to cut his log exactly once. Then he will have two logs weighing 2 grams each.
In the second test case, Monocarp has to cut his log of 4 grams once, then cut one of the resulting logs. He will have one log of weight 2 and two logs of weight 1, so he can use two logs to get exactly 3 grams.
solution 1
fun main() {
repeat(readln().toInt()) { println(solve()) }
}
fun solve(): Long {
var (n, k) = readln().split(' ').map(String::toLong)
while (k.and(1) == 0L) {
k = k.shr(1)
n--
}
return n
}
solution 2
fun main() {
repeat(readln().toInt()) { println(solve()) }
}
fun solve(): Long {
val (n, k) = readln().split(' ').map(String::toLong)
return n - k.countTrailingZeroBits()
}
problem D
There is a staircase consisting of 𝑛 steps. Each step is either intact, or broken. For each broken step, an integer \(𝑎_𝑖\) is given denoting the difficulty of repairing it.
Every day, you can either:
- repair an arbitrary broken step. The effort it takes to repair the 𝑖-th step is equal to 𝑎𝑖;
- or repair two adjacent broken steps. The effort it takes to repair both the 𝑖-th step and the (𝑖+1)-th step is equal to \(2⋅(𝑎_𝑖+𝑎_{𝑖+1})\).
You want to repair all broken steps of the staircase, and you want to do it in the minimum possible number of days. What is the minimum total effort it will take to repair all broken steps in the minimum number of days?
Input
The first line contains one integer \(𝑡(1≤𝑡≤10^4)\) — the number of test cases.
Each test case consists of two lines:
- the first line contains one integer \(𝑛(1≤𝑛≤3⋅10^5)\) — the number of steps;
- the second line contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛(0≤𝑎_𝑖≤10^8)\). If \(𝑎_𝑖=0\), then the 𝑖-th step does not need to be repaired; otherwise, the 𝑖-th step is broken and 𝑎𝑖 is the difficulty of repairing it.
Additional constraint on the input: the sum of values of 𝑛 does not exceed \(3⋅10^5\).
Output
For each test case, print one integer — the minimum possible total effort it will take to repair all broken steps in the minimum number of days.
Example
input
6
5
0 0 0 0 0
4
0 13 15 8
4
13 15 0 8
8
1 2 3 4 5 6 7 8
5
99999999 100000000 99999999 99999999 99999999
5
2 3 4 3 2
output
0
59
64
72
899999993
24
Note
In the first test case, you don’t have to do anything.
In the second test case, you can repair the 3-rd and the 4-th step during the first day, and the 2-nd step during the second day. The total effort will be 2⋅(15+8)+13=59.
In the third test case, you can repair the 4-th step during the first day, and two first steps during the second day. The total effort will be 8+2⋅(13+15)=64.
solution
fun main() {
repeat(readln().toInt()) { println(solve()) }
}
fun solve(): Long {
readln()
val list = readln().split(' ').map(String::toLong)
var sum = list.sum().shl(1)
var max = 0L
var count = 0
list.forEach {
if (it != 0L) {
if (count.and(1) == 0 && it > max) max = it
count++
} else {
if (count.and(1) != 0) sum -= max
max = 0L
count = 0
}
}
if (count.and(1) != 0) sum -= max
return sum
}
problem E
Yet Another Permutation Constructive
Suppose you have a permutation 𝑝 of 𝑛 integers — an array where each element is an integer from 1 to 𝑛, and every integer from 1 to 𝑛 appears exactly once.
In one operation, you remove every element of this permutation which is less than at least one of its neighbors. For example, when you apply the operation to [3,1,2,5,4], you get [3,5]. If you apply an operation again, you get [5].
It’s easy to see that after applying a finite number of operations, you get an array consisting of a single integer 𝑛.
You are given two integers 𝑛 and 𝑘. Find a permutation of 𝑛 integers such that it becomes an array consisting of a single element 𝑛 after exactly 𝑘 operations (and not earlier).
Input
The first line contains one integer 𝑡(1≤𝑡≤2000) — the number of test cases.
Each test case consists of one line containing two integers 𝑛 and 𝑘(2≤𝑛≤100; 1≤𝑘≤𝑛−1).
Output
For each test case, print the answer as follows:
- if a permutation of size 𝑛 which becomes an array consisting of a single element 𝑛 after exactly 𝑘 operations does not exist, print −1;
- otherwise, print 𝑛 distinct integers from 1 to 𝑛 — the requested permutation. If there are multiple such permutations, print any of them.
Example
input
4
5 2
5 4
2 1
3 2
output
3 1 2 5 4
-1
1 2
2 1 3
solution 1
fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map(String::toInt)
// 另一种 hack 判断方法
// if (k < 32 - Integer.numberOfLeadingZeros(n - 1)) {
if (k < 32 && (n - 1).shr(k - 1) > 0) {
println(solve(n, k).joinToString(" "))
} else {
println(-1)
}
}
}
fun solve(n: Int, k: Int): IntArray {
val res = IntArray(n) { n - it }
var s = 2
repeat(k - 1) {
s = s.shl(1) - 1
(s - 1 downTo 0).forEach { i ->
// 待插入的元素从小到大插入
// res[i] = if (i and 1 == 0) res[i.shr(1)] else n - s + i.inc().shr(1)
// 待插入的元素从大到小插入
res[i] = if (i and 1 == 0) res[i.shr(1)] else n - (s + i).shr(1)
}
}
return res
}
solution 2
fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map(String::toInt)
// 另一种 hack 判断方法
// if (k < 32 - Integer.numberOfLeadingZeros(n - 1)) {
if (k < 32 && (n - 1).shr(k - 1) > 0) {
println(solve(n, k).joinToString(" "))
} else {
println(-1)
}
}
}
fun solve(n: Int, k: Int): IntArray {
// val a = IntArray(k + 1) { if (it > 0) 1.shl(it - 1) + 1 else 1 }
val a = intArrayOf(1, 2, 3, 5, 9, 17, 33, 65)
val res = IntArray(n) { n - it }
var start = 1
repeat(k) {
repeat(a[k - it] - a[k - it - 1]) { i ->
// 待插入的元素从小到大插入
// res[i.shl(1).inc().times(start)] = n - a[k - it] + i + 1
// 待插入的元素从大到小插入
res[i.shl(1).inc().times(start)] = n - a[k - it - 1] - i
}
start *= 2
}
return res
}
solution 3
fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map(String::toInt)
if (k < 32 && (n - 1).shr(k - 1) > 0) {
println(solve(n, k).joinToString(" "))
} else {
println(-1)
}
}
}
fun solve(n: Int, k: Int): IntArray {
// val a = IntArray(k + 1) { if (it > 0) 1.shl(it - 1) + 1 else 1 }
val a = intArrayOf(1, 2, 3, 5, 9, 17, 33, 65)
val res = IntArray(n) { n - it }
(1 until a[k]).forEach {
val i = it.countTrailingZeroBits() + 1
res[it] = n - a[k - i] - it.shr(i)
}
return res
}
solution 4
fun main() {
val a = intArrayOf(1, 2, 3, 5, 9, 17, 33, 65)
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map(String::toInt)
if (k < a.size && (n - 1).shr(k - 1) > 0) {
IntArray(n) {
if (it in 1 until a[k]) {
val i = it.countTrailingZeroBits() + 1
n - a[k - i] - it.shr(i)
} else {
n - it
}
}.joinToString(" ").apply(::println)
} else {
println(-1)
}
}
}