UVa/uva-10172.cpp at master · debugster/UVa · 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>

using namespace std;

/* typedef starts */

typedef long long ll;
typedef unsigned long long ull;

/* typedef ends */

/* macro starts */

#define PI acos(-1.0)
#define MAX 101

/* macro ends */

/* function starts */

template<typename dataType>
dataType nthGrayCode(dataType n) /// n is 0-based
{
    return (n ^ (n >> 1));
}

/* function ends */

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int test, n, s, q, qi, totalQI, i, j, c, _count, timeTaken;
    stack<int>carrier;
    queue<int>Q[MAX];

    scanf("%d", &test);
    while (test--) {
        scanf("%d%d%d", &n, &s, &q);

        totalQI = 0;
        for (i = 1; i <= n; i++) {
            while (!Q[i].empty()) {
                Q[i].pop();
            }

            scanf("%d", &qi);
            for (j = 1; j <= qi; j++) {
                scanf("%d", &c);
                Q[i].push(c);
            }
            totalQI += qi;
        }

        while (!carrier.empty()) {
            carrier.pop();
        }

        _count = 0;
        timeTaken = 0;
        for (i = 1; i <= n; i++) {

            /// unload carrier
            while (true) {
                if (carrier.empty()) {
                    break;
                }

                c = carrier.top();
                if (c == i) {
                    carrier.pop();
                    timeTaken++;
                    _count++;
                }
                else {
                    if (Q[i].size() < q) {
                        carrier.pop();
                        Q[i].push(c);
                        timeTaken++;
                    }
                    else {
                        break;
                    }
                }
            }

            /// load carrier
            while (true) {
                if (carrier.size() == s || Q[i].empty()) {
                    break;
                }

                c = Q[i].front();
                Q[i].pop();
                carrier.push(c);
                timeTaken++;
            }

            if (_count == totalQI) {
                break;
            }

            if (i == n) {
                i = 0; /// after increment, it will be 1
            }
            timeTaken += 2;
        }

        printf("%d\n", timeTaken);
    }

    return 0;
}