It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from to . Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.
Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.
Example
If person bribes person , the queue will look like this: . Only bribe is required. Print 1.
Person had to bribe people to get to the current position. Print Too chaotic.
Function Description
Complete the function minimumBribes in the editor below.
minimumBribes has the following parameter(s):
- int q[n]: the positions of the people after all bribes
Returns
- No value is returned. Print the minimum number of bribes necessary or Too chaotic if someone has bribed more than people.
Input Format
The first line contains an integer , the number of test cases.
Each of the next pairs of lines are as follows:
- The first line contains an integer , the number of people in the queue
- The second line has space-separated integers describing the final state of the queue.
Constraints
Subtasks
For score
For score
Sample Input
STDIN Function
----- --------
2 t = 2
5 n = 5
2 1 5 3 4 q = [2, 1, 5, 3, 4]
5 n = 5
2 5 1 3 4 q = [2, 5, 1, 3, 4]
Sample Output
3
Too chaotic
Explanation
Test Case 1
The initial state:
After person moves one position ahead by bribing person :
Now person moves another position ahead by bribing person :
And person moves one position ahead by bribing person :
So the final state is after three bribing operations.
Test Case 2
No person can bribe more than two people, yet it appears person has done so. It is not possible to achieve the input state.
문제 풀이를 위한 설명
각 숫자의 index + 1 이 원래 그 숫자의 값이 되어야 하기 때문에, index + 1 과 현재 위치(index)에 위치한 실제 숫자값을 비교한다.
비교한 값은 범위가 +2 ~ -x 까지 나올 수 있다. 양수가 나오는 케이스는 숫자를 왼쪽으로 이동시켰기 때문이므로, +2를 넘어가면 두 번을 초과해서 움직인 것이므로 +2까지 나올 수 있고, 음수가 나오는 케이스는 왼쪽으로 이동한 숫자값의 개수에 따라 -2 이상도 가능하므로 -x로 표기하였다.
전략은 다음과 같다.
- 배열의 끝에서부터 0까지 반복한다. 이동한 횟수를 moveCount라고 명명한다.
- 숫자값과 index + 1을 비교하고, 그 값을 sum이라고 명명하고 비교한 값을 sum에 계속 더한다. sum의 시작은 음수가 될 것이고, sum이 0이 되는 순간까지 하나의 [그룹]이라고 칭한다.
- 양수값이 나올 경우 +2를 초과하는지 검사한다.
- 음수값이 나올 경우 [그룹]이 형성될 때까지 이전 숫자값과 현재 숫자값을 비교해 이전 숫자값이 더 크면 moveCount를 증가시킨다.
그렇게 반복하게 되면 최종 이동 횟수를 구할 수 있다.
이동 횟수는 정상적으로 계산되는데 문제는, 10000 개가 넘어가는 테스트 케이스는 timeout이 발생하더라. 2-2번의 연산 횟수를 줄여야 할 듯 한데 딱히 생각나는 좋은 방법이 없어 여기서 마무리 한다. 이 문제로 너무 오랜 시간을 소비했다.
import java.io.*
import java.math.*
import java.security.*
import java.text.*
import java.util.*
import java.util.concurrent.*
import java.util.function.*
import java.util.regex.*
import java.util.stream.*
import kotlin.collections.*
import kotlin.comparisons.*
import kotlin.io.*
import kotlin.jvm.*
import kotlin.jvm.functions.*
import kotlin.jvm.internal.*
import kotlin.ranges.*
import kotlin.sequences.*
import kotlin.text.*
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
*/
fun minimumBribes(q: Array<Int>): Unit {
// Write your code here
var moveCount = 0
for(i in q.lastIndex downTo 0) {
val n = i + 1
if(q[i] > n) {
if((q[i] - n) > 2) {
println("Too chaotic")
return
}
} else { // v < n
try {
var sum = q[i] - n
var j = i - 1
while(sum != 0 || j > 0) {
if(q[j] > q[i]) {
moveCount++
}
sum += j - q[j]
j -= 1
if(j < 0) {
break
}
}
} catch(e: Exception) {
}
}
}
println(moveCount)
}
fun main(args: Array<String>) {
val t = readLine()!!.trim().toInt()
for (tItr in 1..t) {
val n = readLine()!!.trim().toInt()
val q = readLine()!!.trimEnd().split(" ").map{ it.toInt() }.toTypedArray()
minimumBribes(q)
}
}
댓글