Problem

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 1 to n . 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 5 bribes person 4, the queue will look like this: 1,,2,3,5,4,6,7,8 . Only 1 bribe is required. Print 1.

Person 4 had to bribe 3 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 2 people.

Input Format

The first line contains an integer t, the number of test cases.

Each of the next t pairs of lines are as follows:

  • The first line contains an integer t, the number of people in the queue
  • The second line has n space-separated integers describing the final state of the queue.

Constraints

  • Subtasks

For score

For score <!– s

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

Solution

  • For each element to the number of elements greater than it is in front of it, this is simply understood that the person in the back wants to move forward.

  • If the position after shifting forward 3 units, the printout is too chaotic.

    Code

void minimumBribes(vector<int> q) 
{
    int total=0;
    for (int i = q.size()-1;i>=0;i--)
    {
        if (q[i]-i-1 > 2)
        {
            cout << "Too chaotic \n";
            return;
        }
        for (int j = max(0,q[i]-2);j<i;j++)
        {
            if (q[j]>q[i])
                total++;
        }
    }
    cout << total << "\n";
}