problem A
Alice has 𝑛 books. The 1-st book contains \(𝑎_1\) pages, the 2-nd book contains \(𝑎_2\) pages, …, the 𝑛-th book contains \(𝑎_𝑛\) pages. Alice does the following:
- She divides all the books into two non-empty piles. Thus, each book ends up in exactly one of the two piles.
- Alice reads one book with the highest number in each pile.
Alice loves reading very much. Help her find the maximum total number of pages she can read by dividing the books into two piles.
Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡 (1≤𝑡≤500) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer 𝑛 (2≤𝑛≤100) — the number of books Alice has.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛 (1≤𝑎_𝑖≤10^9)\) — the number of pages in each book.
Output
For each test case, output a single integer — the maximum number of pages Alice can read.
Example
input
5
2
1 1
4
2 3 3 1
5
2 2 3 2 2
2
10 3
3
1 2 3
output
2
4
5
13
5
Note
In the first test case, Alice can put book number 1 in the first pile, and book number 2 in the second pile. Then she will read \(𝑎_1+𝑎_2=1+1=2\) pages.
In the second test case, Alice can put books with numbers 2 and 3 in the first pile, and books with numbers 1 and 4 in the second pile. Then she will read the book with the highest number 3 from the first pile, and the book with the highest number 4 from the second pile. Then she will read \(𝑎_3+𝑎_4=3+1=4\) pages.
solution
fun main() {
repeat(readln().toInt()) {
println(solve())
}
}
fun solve(): Int {
val n = readln().toInt()
val a = readln().split(' ').map(String::toInt)
var max = 0
repeat(n - 1) {
max = max.coerceAtLeast(a[it])
}
return max + a[n - 1]
}
problem B
Bob decided to open a bakery. On the opening day, he baked 𝑛 buns that he can sell. The usual price of a bun is 𝑎 coins, but to attract customers, Bob organized the following promotion:
- Bob chooses some integer 𝑘 (0≤𝑘≤min(𝑛,𝑏)).
- Bob sells the first 𝑘 buns at a modified price. In this case, the price of the 𝑖-th (1≤𝑖≤𝑘) sold bun is (𝑏−𝑖+1) coins.
- The remaining (𝑛−𝑘) buns are sold at 𝑎 coins each.
Note that 𝑘 can be equal to 0. In this case, Bob will sell all the buns at 𝑎 coins each.
Help Bob determine the maximum profit he can obtain by selling all 𝑛 buns.
Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡 \((1≤𝑡≤10^4)\) — the number of test cases. The description of the test cases follows.
The only line of each test case contains three integers 𝑛, 𝑎, and 𝑏 \((1≤𝑛,𝑎,𝑏≤10^9)\) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.
Output
For each test case, output a single integer — the maximum profit that Bob can obtain.
Example
input
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000
output
17
35
100
45
1000000000000000000
1000000000000000000
500500
Note
In the first test case, it is optimal for Bob to choose 𝑘=1. Then he will sell one bun for 5 coins, and three buns at the usual price for 4 coins each. Then the profit will be 5+4+4+4=17 coins.
In the second test case, it is optimal for Bob to choose 𝑘=5. Then he will sell all the buns at the modified price and obtain a profit of 9+8+7+6+5=35 coins.
In the third test case, it is optimal for Bob to choose 𝑘=0. Then he will sell all the buns at the usual price and obtain a profit of 10⋅10=100 coins.
solution
fun main() {
repeat(readln().toInt()) {
println(solve())
}
}
fun solve(): Long {
val (n, a, b) = readln().split(' ').map(String::toLong)
val cnt = (b - a + 1).coerceAtMost(n).coerceAtLeast(0)
return (n - cnt) * a + (2 * b - cnt + 1) * cnt / 2
}
problem C
Let’s call the Manhattan value of a permutation 𝑝 the value of the expression \(\vert𝑝_1−1\vert+\vert𝑝_2−2\vert+…+\vert𝑝_𝑛−𝑛\vert\).
For example, for the permutation [1,2,3], the Manhattan value is \(\vert1−1\vert+\vert2−2\vert+\vert3−3\vert=0\), and for the permutation [3,1,2], the Manhattan value is \(\vert3−1\vert+\vert1−2\vert+\vert2−3\vert=2+1+1=4\).
You are given integers 𝑛 and 𝑘. Find a permutation 𝑝 of length 𝑛 such that its Manhattan value is equal to 𝑘, or determine that no such permutation exists.
A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 1 to 𝑛 in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (𝑛=3 but there is 4 in the array).
Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡 \((1≤𝑡≤10^4)\) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers 𝑛 and 𝑘 \((1≤𝑛≤2⋅10^5,0≤𝑘≤10^{12})\) — the length of the permutation and the required Manhattan value.
It is guaranteed that the sum of 𝑛 over all test cases does not exceed \(2⋅10^5\).
Output
For each test case, if there is no suitable permutation, output “No”. Otherwise, in the first line, output “Yes”, and in the second line, output 𝑛 distinct integers \(𝑝_1,𝑝_2,…,𝑝_𝑛 (1≤𝑝_𝑖≤𝑛)\) — a suitable permutation.
If there are multiple solutions, output any of them.
You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as a positive answer).
Example
input
8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2
output
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5
Note
In the first test case, the permutation [3,1,2] is suitable, its Manhattan value is \(\vert3−1\vert+\vert1−2\vert+\vert2−3\vert=2+1+1=4\).
In the second test case, it can be proven that there is no permutation of length 4 with a Manhattan value of 5.
In the third test case, the permutation [1,2,3,4,5,6,7] is suitable, its Manhattan value is \(\vert1−1\vert+\vert2−2\vert+\vert3−3\vert+\vert4−4\vert+\vert5−5\vert+\vert6−6\vert+\vert7−7\vert=0\).
solution
fun main() {
repeat(readln().toInt()) {
solve()
}
}
fun solve() {
var (m, k) = readln().split(' ').map(String::toLong)
val n = m.toInt()
val ans = IntArray(n) { it + 1 }
var l = 0
var r = n - 1
while (l < r && k > 0) {
val d = 2 * (r - l)
if (k >= d) {
k -= d
ans[l] = r + 1
ans[r] = l + 1
l++
r--
} else {
l++
}
}
if (k == 0L) {
println("Yes")
println(ans.joinToString(" "))
} else {
println("No")
}
}
problem D
Elections are taking place in Berland. There are 𝑛 candidates participating in the elections, numbered from 1 to 𝑛. The 𝑖-th candidate has \(𝑎_𝑖\) fans who will vote for him. Additionally, there are 𝑐 people who are undecided about their favorite candidate, let’s call them undecided. Undecided people will vote for the candidate with the lowest number.
The candidate who receives the maximum number of votes wins the elections, and if multiple candidates receive the same maximum number of votes, the candidate with the lowest number among them wins.
You found these elections too boring and predictable, so you decided to exclude some candidates from them. If you do not allow candidate number 𝑖 to participate in the elections, all \(𝑎_𝑖\) of his fans will become undecided, and will vote for the candidate with the lowest number.
You are curious to find, for each 𝑖 from 1 to 𝑛, the minimum number of candidates that need to be excluded from the elections for candidate number 𝑖 to win the elections.
Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡 \((1≤𝑡≤2⋅10^4)\) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers 𝑛 and 𝑐 \((1≤𝑛≤2⋅10^5, 0≤𝑐≤10^9)\) — the number of candidates in the elections and the number of undecided people.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛 (0≤𝑎_𝑖≤10^9)\) — the number of fans for each candidate.
It is guaranteed that the sum of 𝑛 over all test cases does not exceed \(2⋅10^5\).
Output
For each test case, output 𝑛 integers, the 𝑖-th of which should be equal to the minimum number of candidates that need to be excluded from the elections for candidate number 𝑖 to win.
Example
input
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3
output
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5
Note
In the first test case:
- If all candidates are allowed, candidate number 1 will receive 3 votes (1 undecided person will vote for him), candidate number 2 will receive 0 votes, and candidate number 3 will receive 3 votes. Therefore, candidate number 1 wins (he received the same number of votes as candidate 3, but his number is lower), so the answer for him is 0.
- If candidate number 1 is not allowed, his 2 fans will become undecided. Then candidate number 2 will receive 3 votes (3 undecided people will vote for him) and candidate number 3 will receive 3 votes. Therefore, candidate number 2 wins (he received the same number of votes as candidate 3, but his number is lower), so the answer for him is 1.
- If candidates with numbers 1 and 2 are not allowed, candidate number 3 wins, so the answer for him is 2.
In the second test case, candidate number 1 will win if candidate number 2 is not allowed to participate.
solution
fun main() {
repeat(readln().toInt()) {
println(solve().joinToString(" "))
}
}
fun solve(): IntArray {
val (n, c) = readln().split(' ').map(String::toInt)
val a = readln().split(' ').map(String::toInt).toIntArray()
a[0] += c
var max = 0
var maxIndex = 0
repeat(n) {
if (a[it] > max) {
max = a[it]
maxIndex = it
}
}
val ans = IntArray(n) { it }
a.foldIndexed(0L) { index, acc, num ->
if (acc + num < max) ans[index] += 1
acc + num
}
ans[maxIndex] = 0
return ans
}
problem E
Sasha has two binary strings 𝑠 and 𝑡 of the same length 𝑛, consisting of the characters 0 and 1.
There is also a computing machine that can perform two types of operations on binary strings 𝑎 and 𝑏 of the same length 𝑘:
- If \(𝑎_𝑖=𝑎_{𝑖+2}=0\), then you can assign \(𝑏_{𝑖+1}:=1 (1≤𝑖≤𝑘−2)\).
- If \(𝑏_𝑖=𝑏_{𝑖+2}=1\), then you can assign \(𝑎_{𝑖+1}:=1 (1≤𝑖≤𝑘−2)\).
Sasha became interested in the following: if we consider the string \(𝑎=𝑠_𝑙𝑠_{𝑙+1}…𝑠_𝑟\) and the string \(𝑏=𝑡_𝑙𝑡_{𝑙+1}…𝑡_𝑟\), what is the maximum number of 1 characters in the string 𝑎 that can be obtained using the computing machine. Since Sasha is very curious but lazy, it is up to you to answer this question for several pairs \((𝑙_𝑖,𝑟_𝑖)\) that interest him.
Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡 \((1≤𝑡≤10^4)\) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer 𝑛 \((1≤𝑛≤2⋅10^5)\) — the length of the strings 𝑠 and 𝑡.
The second line of each test case contains a binary string 𝑠 of length 𝑛, consisting of the characters 0 and 1.
The third line of each test case contains a binary string 𝑡 of length 𝑛, consisting of the characters 0 and 1.
The fourth line of each test case contains a single integer 𝑞 \((1≤𝑞≤2⋅10^5)\) — the number of queries.
The 𝑖-th of the following lines contains two integers 𝑙𝑖 and 𝑟𝑖 \((1≤𝑙_𝑖≤𝑟_𝑖≤𝑛)\) — the boundaries of the 𝑖-th pair of substrings that interest Sasha.
It is guaranteed that the sum of 𝑛 over all test cases does not exceed \(2⋅10^5\) and the sum of 𝑞 over all test cases does not exceed \(2⋅10^5\).
Output
For each test case, output 𝑞 integers — the answers to all queries.
Example
input
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6
output
2
3
2
3
1
4
3
1
2
Note
In the first test case:
- In the first query, 𝑎=11, so the maximum number of 1 characters is 2.
- In the second query, 𝑎=111, so the maximum number of 1 characters is 3.
In the second test case:
- In the first query, 𝑎=101 and 𝑏=110. No operations can be performed, so the maximum number of 1 characters is 2.
- In the second query, 𝑎=1010 and 𝑏=1101. Since 𝑎2=𝑎4=0, we can assign 𝑏3:=1. Now 𝑏1=𝑏3=1, so we can assign 𝑎2:=1. The string 𝑎 becomes 1110, so the maximum number of 1 characters is 3.
solution
fun main() {
repeat(readln().toInt()) { solve() }
}
fun solve() {
val n = readln().toInt()
val s = readln().toCharArray().map { it - '0' }.toIntArray()
val t = readln().toCharArray().map { it - '0' }.toIntArray()
val q = readln().toInt()
val a = s.clone()
val b = t.clone()
val sum = IntArray(n) { 0 }
repeat(n - 2) { if (a[it] == 0 && a[it + 2] == 0) b[it + 1] = 1 }
repeat(n - 2) { if (b[it] == 1 && b[it + 2] == 1) a[it + 1] = 1 }
a.foldIndexed(0) { index, acc, num -> (acc + num).also { sum[index] = it } }
repeat(q) {
val (left, right) = readln().split(" ").map(String::toInt)
val l = left - 1
val r = right - 1
var ans = 0
if (r - l < 4) {
(l..r).forEach { ans += check(s, t, l, r, it) }
} else {
ans += sum[r - 2] - sum[l + 1]
listOf(l, l + 1, r - 1, r).forEach { ans += check(s, t, l, r, it) }
}
println(ans)
}
}
fun check(s: IntArray, t: IntArray, l: Int, r: Int, i: Int): Int {
if (s[i] == 1) return 1
if (i !in l + 1..<r) return 0
val conditionLeft = (t[i - 1] == 1 || (i - 2 >= l && s[i - 2] == 0))
val conditionRight = (t[i + 1] == 1 || (i + 2 <= r && s[i + 2] == 0))
return if (conditionLeft && conditionRight) 1 else 0
}