problem A
Define the range of a non-empty array to be the maximum value minus the minimum value. For example, the range of [1,4,2] is 4−1=3.
You are given an array \(𝑎_1,𝑎_2,…,𝑎_𝑛\) of length 𝑛≥3. It is guaranteed 𝑎 is sorted.
You have to color each element of 𝑎 red or blue so that:
- the range of the red elements does not equal the range of the blue elements, and
- there is at least one element of each color.
If there does not exist any such coloring, you should report it. If there are multiple valid colorings, you can print any of them.
Input
The first line contains a single integer 𝑡 (1≤𝑡≤100) — the number of test cases.
The first line of each test case contains an integer 𝑛 (3≤𝑛≤50) — the length of the array.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛 (1≤𝑎_𝑖≤10^9)\). It is guaranteed \(𝑎_1≤𝑎_2≤…≤𝑎_{𝑛−1}≤𝑎_𝑛\).
Output
For each test case, if it is impossible to color 𝑎 to satisfy all the constraints, output 𝙽𝙾.
Otherwise, first output 𝚈𝙴𝚂.
Then, output a string 𝑠 of length 𝑛. For 1≤𝑖≤𝑛, if you color \(𝑎_𝑖\) red, \(𝑠_𝑖\) should be 𝚁. For 1≤𝑖≤𝑛, if you color \(𝑎_𝑖\) blue, \(𝑠_𝑖\) should be 𝙱.
Example
input
7
4
1 1 2 2
5
1 2 3 4 5
3
3 3 3
4
1 2 2 2
3
1 2 2
3
1 1 2
3
1 9 84
output
YES
RBRR
YES
BBRBB
NO
YES
RBBR
YES
RRB
YES
BRR
YES
BRB
Note
In the first test case, given the array [1,1,2,2], we can color the second element blue and the remaining elements red; then the range of the red elements [1,2,2] is 2−1=1, and the range of the blue elements [1] is 1−1=0.
In the second test case, we can color the first, second, fourth and fifth elements [1,2,4,5] blue and the remaining elements [3] red.
The range of the red elements is 3−3=0 and the range of the blue elements is 5−1=4, which are different.
In the third test case, it can be shown there is no way to color 𝑎=[3,3,3] to satisfy the constraints.
solution
fun main() {
repeat(readln().toInt()) {
solve()
}
}
fun solve() {
val n = readln().toInt()
val a = readln().split(' ').map(String::toInt)
if (a[n - 1] == a[0]) {
println("NO")
} else {
println("YES")
val chars = CharArray(n) { if (it != 1) 'R' else 'B' }
println(String(chars))
}
}
problem B
A digit is large if it is between 5 and 9, inclusive. A positive integer is large if all of its digits are large.
You are given an integer 𝑥. Can it be the sum of two large positive integers with the same number of digits?
Input
The first line contains a single integer 𝑡 \((1≤𝑡≤10^4)\) — the number of test cases.
The only line of each test case contains a single integer 𝑥 \((10≤𝑥≤10^{18})\).
Output
For each test case, output 𝚈𝙴𝚂 if 𝑥 satisfies the condition, and 𝙽𝙾 otherwise.
You can output 𝚈𝙴𝚂 and 𝙽𝙾 in any case (for example, strings 𝚢𝙴𝚂, 𝚢𝚎𝚜, and 𝚈𝚎𝚜 will be recognized as a positive response).
Example
input
11
1337
200
1393938
1434
98765432123456789
11111111111111111
420
1984
10
69
119
output
YES
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
Note
In the first test case, we can have 658+679=1337.
In the second test case, it can be shown that no numbers of equal length and only consisting of large digits can add to 200.
In the third test case, we can have 696969+696969=1393938.
In the fourth test case, we can have 777+657=1434.
solution
fun main() {
repeat(readln().toInt()) {
println(if (solve()) "YES" else "NO")
}
}
fun solve(): Boolean {
val a = readln().toCharArray().map { it - '0' }.toIntArray()
a.forEachIndexed { i, n ->
when (i) {
0 -> if (n != 1) return false
a.size - 1 -> if (n == 9) return false
else -> if (n == 0) return false
}
}
return true
}
problem C1
You are given an array 𝑎 of length 𝑛. Start with 𝑐=0. Then, for each 𝑖 from 1 to 𝑛 (in increasing order) do exactly one of the following:
- Option 1: set 𝑐 to \(𝑐+𝑎_𝑖\).
- Option 2: set 𝑐 to
|\(𝑐+𝑎_𝑖\)|, where|𝑥|is the absolute value of 𝑥.
Let the maximum final value of 𝑐 after the procedure described above be equal to 𝑘. Find 𝑘.
Input
The first line contains a single integer 𝑡 \((1≤𝑡≤10^4)\) — the number of test cases.
The first line of each test case contains a single integer 𝑛 \((2≤𝑛≤2⋅10^5)\).
The second line of each case contains 𝑛 integers \(𝑎_1, 𝑎_2, 𝑎_3, …, 𝑎_𝑛 (−10^9≤𝑎_𝑖≤10^9)\).
The sum of 𝑛 over all test cases does not exceed \(3⋅10^5\).
Output
For each test case, output a single integer — the value of 𝑘.
Example
input
5
4
10 -9 -3 4
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4
output
6
24
6
4000000000
22
Note
In the first test case, if we set 𝑐 to its absolute value every time we add to it, we end up with 6. It can be shown that this is the maximum result.
In the second test case, taking the absolute value will never change anything, so we can just sum the array without doing anything to get 24.
In the third test case, it is optimal to wait until the end to set 𝑐 to its absolute value, resulting in an answer of 6.
solution 1
fun main() {
repeat(readln().toInt()) {
println(solve())
}
}
fun solve(): Long {
val n = readln().toInt()
val a = readln().split(' ').map(String::toLong).toLongArray()
var min = 0L
var max = 0L
a.forEach {
min += it
max += it
max = max.coerceAtLeast(-min)
}
return max
}
solution 2
fun main() {
repeat(readln().toInt()) {
println(solve())
}
}
fun solve(): Long {
val n = readln().toInt()
val a = readln().split(' ').map(String::toLong).toLongArray()
var min = 0L
return a.fold(0L) { max, l ->
min += l
(max + l).coerceAtLeast(-min)
}
}