DS-Algo-Problem-Solving/Bribe.cpp at main · RajB07/DS-Algo-Problem-Solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//  link https://www.hackerrank.com/challenges/new-year-chaos/problem
#include <iostream>
#include <vector>

using namespace std;

void check(vector<int> a, int n)
{
    int bribe = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] - (i + 1) > 2)
        {
            cout << "Too chaotic" << endl;
            return;
        }
        for (int j = 0; j < i; j++)
            if (a[j] > a[i])
                bribe++;
    }
    cout << bribe << endl;
}

void check2(vector<int> a, int n)
{
    int f = 1, s = 2, t = 3, bribe = 0;

    for (int i = 0; i < n; i++)
    {
        if (a[i] == f)
        {
            f = s;
            s = t;
            t++;
        }

        else if (a[i] == s)
        {
            bribe++;
            s = t;
            t++;
        }
        else if (a[i] == t)
        {
            bribe += 2;
            t++;
        }
        else
        {
            cout << "Too chaotic" << endl;
            return;
        }
    }
    cout << bribe << endl;
}
int main()
{
    int N, n, i;
    cin >> N;
    while (N--)
    {
        cin >> n;
        vector<int> a(n, 0);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        // check(a,n);
        check2(a, n);
    }
}