problem A
Mocha likes arrays, so before her departure, Bazoka gave her an array 𝑎 consisting of 𝑛 positive integers as a gift.
Now Mocha wants to know whether array 𝑎 could become sorted in non-decreasing order after performing the following operation some (possibly, zero) times:
- Split the array into two parts — a prefix and a suffix, then swap these two parts. In other words, let 𝑎=𝑥+𝑦. Then, we can set 𝑎:=𝑦+𝑥. Here + denotes the array concatenation operation.
For example, if 𝑎=[3,1,4,1,5], we can choose 𝑥=[3,1] and 𝑦=[4,1,5], satisfying 𝑎=𝑥+𝑦. Then, we can set 𝑎:=𝑦+𝑥=[4,1,5,3,1]. We can also choose 𝑥=[3,1,4,1,5] and 𝑦=[], satisfying 𝑎=𝑥+𝑦. Then, we can set 𝑎:=𝑦+𝑥=[3,1,4,1,5]. Note that we are not allowed to choose 𝑥=[3,1,1] and 𝑦=[4,5], neither are we allowed to choose 𝑥=[1,3] and 𝑦=[5,1,4], as both these choices do not satisfy 𝑎=𝑥+𝑦.
Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤1000). The description of the test cases follows.
The first line of each test case contains a single integer 𝑛 (2≤𝑛≤50) — the length of the array 𝑎.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛(0≤𝑎_𝑖≤10^6)\) — the elements of array 𝑎.
Output
For each test case, output “Yes” if 𝑎 could become non-decreasing after performing the operation any number of times, and output “No” if not.
You can output “Yes” and “No” in any case (for example, strings “yEs”, “yes”, “Yes” and “YES” will be recognized as a positive response).
Example
input
3
6
1 1 4 5 1 4
5
7 9 2 2 3
3
1 2 3
output
No
Yes
Yes
Note
In the first test case, it can be proven that 𝑎 cannot become non-decreasing after performing the operation any number of times.
In the second test case, we can perform the following operations to make 𝑎 sorted in non-decreasing order:
- Split the array into two parts: 𝑥=[7] and 𝑦=[9,2,2,3], then swap these two parts. The array will become 𝑦+𝑥=[9,2,2,3,7].
- Split the array into two parts: 𝑥=[9] and 𝑦=[2,2,3,7], then swap these two parts. The array will become 𝑦+𝑥=[2,2,3,7,9], which is non-decreasing.
solution
fun main() {
repeat(readln().toInt()) {
println(if (solve()) "YES" else "NO")
}
}
fun solve(): Boolean {
val n = readln().toInt()
val a = readln().split(' ').map(String::toInt).toIntArray()
var cnt = 0
repeat(n - 1) {
cnt += if (a[it + 1] < a[it]) 1 else 0
}
cnt += if (a[0] < a[n - 1]) 1 else 0
return cnt <= 1
}
problem B
Mocha likes arrays, so before her departure, 378QAQ gave her an array 𝑎 consisting of 𝑛 positive integers as a gift.
Mocha thinks that 𝑎 is beautiful if there exist two numbers 𝑖 and 𝑗 (1≤𝑖,𝑗≤𝑛, 𝑖≠𝑗) such that for all 𝑘 (1≤𝑘≤𝑛), \(𝑎_𝑘\) is divisible by either \(𝑎_i\) or \(𝑎_j\).
Determine whether 𝑎 is beautiful.
𝑥 is divisible by 𝑦 if there exists an integer 𝑧 such that 𝑥=𝑦⋅𝑧.
Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤500). The description of the test cases follows.
The first line of each test case contains a single integer 𝑛 \((3≤𝑛≤10^5)\) — the length of the array 𝑎.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛 (1≤𝑎_𝑖≤10^9)\) — the elements of the array 𝑎.
It is guaranteed that the sum of 𝑛 over all test cases does not exceed \(10^5\).
Output
For each test case, output “Yes” if array 𝑎 is beautiful, and output “No” otherwise.
You can output “Yes” and “No” in any case (for example, strings “yEs”, “yes”, “Yes” and “YES” will be recognized as a positive response).
Example
input
4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 49 9 3 1000000000
output
No
Yes
Yes
No
Note
In the first test case, any two numbers in the array are coprime, so the answer is “No”.
In the second test case, we can pick 𝑖=2 and 𝑗=1. Since every number in the array is divisible by \(𝑎_𝑖=1\), the answer is “Yes”.
In the third test case, we can pick 𝑖=3 and 𝑗=5. 2 and 4 is divisible by \(𝑎_𝑖=2\) while 3, 6 and 12 is divisible by \(𝑎_𝑗=3\), so the answer is “Yes”.
solution 1
fun main() {
repeat(readln().toInt()) {
println(if (solve()) "YES" else "NO")
}
}
fun solve(): Boolean {
readln()
val array = readln().split(' ').map(String::toInt).toIntArray()
val min = array.min()
val a = array.filter { it.mod(min) != 0 }
if (a.isEmpty()) return true
val m = a.min()
return a.all { it.mod(m) == 0 }
}
solution 2
fun main() {
repeat(readln().toInt()) {
readln()
val a = readln().split(' ').map(String::toInt).toIntArray()
println(if (solve(a, 2)) "YES" else "NO")
}
}
fun solve(array: IntArray, i: Int): Boolean {
if (array.isEmpty()) return true
if (i <= 0) return false
val min = array.min()
val a = array.filter { it.mod(min) != 0 }.toIntArray()
return solve(a, i - 1)
}
problem C
Mocha likes arrays, so before her departure, Chamo gave her an array 𝑎 consisting of 𝑛 positive integers as a gift.
Mocha doesn’t like arrays containing different numbers, so Mocha decides to use magic to change the array. Mocha can perform the following three-step operation some (possibly, zero) times:
- Choose indices 𝑙 and 𝑟 (1≤𝑙<𝑟≤𝑛)
- Let 𝑥 be the median of the subarray \([𝑎_𝑙,𝑎_{𝑙+1},…,𝑎_𝑟]\)
- Set all values \(𝑎_𝑙,𝑎_{𝑙+1},…,𝑎_𝑟\) to 𝑥
Suppose 𝑎=[1,2,3,4,5] initially:
- If Mocha chooses (𝑙,𝑟)=(3,4) in the first operation, then 𝑥=3, the array will be changed into 𝑎=[1,2,3,3,5].
- If Mocha chooses (𝑙,𝑟)=(1,3) in the first operation, then 𝑥=2, the array will be changed into 𝑎=[2,2,2,4,5].
Mocha will perform the operation until the array contains only the same number. Mocha wants to know what is the maximum possible value of this number.
The median in an array 𝑏 of length 𝑚 is an element that occupies position number ⌊\(\tfrac{m+1}{2}\)⌋ after we sort the elements in non-decreasing order. For example, the median of [3,1,4,1,5] is 3 and the median of [5,25,20,24] is 20.
Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤500). The description of the test cases follows.
The first line of each test case contains a single integer 𝑛 \((2≤𝑛≤10^5)\) — the length of the array 𝑎.
The second line of each test case contains 𝑛 integers \(𝑎_1,𝑎_2,…,𝑎_𝑛 (1≤𝑎_𝑖≤10^9)\) — the elements of the array 𝑎.
It is guaranteed that the sum of 𝑛 over all test cases does not exceed \(10^5\).
Output
For each test case, output the maximum value of the number.
Example
input
2
2
1 2
5
1 2 3 4 5
output
1
4
Note
In the first test case, 𝑎=[1,2]. Mocha can only choose the interval (𝑙,𝑟)=(1,2). The array will be changed to 𝑎=[1,1].Therefore, the answer is 1.
In the second test case, Mocha can perform the following operations:
- Choose the interval (𝑙,𝑟)=(4,5), then 𝑎=[1,2,3,4,4].
- Choose the interval (𝑙,𝑟)=(3,5), then 𝑎=[1,2,4,4,4].
- Choose the interval (𝑙,𝑟)=(1,5), then 𝑎=[4,4,4,4,4].
The array contains only the same number, which is 4. It can be proven that the maximum value of the final number cannot be greater than 4.
solution
import kotlin.math.max
import kotlin.math.min
fun main() {
repeat(readln().toInt()) {
println(solve())
}
}
fun solve(): Int {
val n = readln().toInt()
val a = readln().split(' ').map(String::toInt).toIntArray()
var res = 0
repeat(n - 1) {
res = max(res, min(a[it], a[it + 1]))
if (it < n - 2) res = max(res, min(a[it], a[it + 2]))
}
return res
}