Untitled

Game with number

Case #1
26 21
Case #2
20 15
Case #3
19 16
Case #4
20 17
Case #5
30 26
Case #6
38 35
Case #7
20 18
Case #8
38 30
Case #9
40 34
Case #10
192 181
Case #11
167 133
Case #12
180 131
Case #13
234 214
Case #14
244 188
Case #15
204 167
Case #16
213 176
Case #17
253 195
Case #18
195 150
Case #19
211 171
Case #20
496 407
Case #21
497 390
Case #22
597 456
Case #23
535 417
Case #24
673 567
Case #25
609 520
Case #26
690 633
Case #27
597 542
Case #28
797 587
Case #29
809 606
Case #30
1564 1139
Case #31
1453 1206
Case #32
1777 1426
Case #33
1522 1191
Case #34
1554 1155
Case #35
1691 1410
Case #36
1681 1428
Case #37
1710 1182
Case #38
1594 1164
Case #39
2031 1434
Case #40
4386 3269
Case #41
4589 3333
Case #42
4826 3288
Case #43
5278 3670
Case #44
4870 3920
Case #45
5463 3972
Case #46
4682 3357
Case #47
5325 4095
Case #48
6175 4557
Case #49
5342 3706
Case #50
5342 3706




#include <iostream>

#define SIZE 30
using namespace std;

int data[SIZE], MAX[SIZE][SIZE],MIN[SIZE][SIZE];

#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)

int Easy(int i, int j) {
    if (i > j) {
        return 0;
    }

    if (MAX[i][j]) 
        return MAX[i][j];

    int t1 = data[i] + Easy(i + 1, j - 1);
    int t2 = data[i] + Easy(i + 2, j);

    int t3 = data[j] + Easy(i + 1, j - 1);
    int t4 = data[j] + Easy(i, j - 2);

    return MAX[i][j] = Max(Max(t1, t2), Max(t3, t4));
}

int Hard(int i,int j) {
    if (i > j) {
        return 0;
    }

    if (MIN[i][j]) 
        return MIN[i][j];

    int t1 = data[i] + Hard(i + 1, j - 1);
    int t2 = data[i] + Hard(i + 2, j);

    int t3 = data[j] + Hard(i + 1, j - 1);
    int t4 = data[j] + Hard(i, j - 2);

    return MIN[i][j] = Max(Min(t1, t2), Min(t3, t4));
}

int main() {
    int T, K;

    freopen("input.txt", "r", stdin);

	cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> K;
        for (int i = 0; i <K; i++) {
            cin >> data[i];
        }

        for (int i = 0;i <SIZE; i++) {
            for (int j = 0;j <SIZE; j++) {
                MAX[i][j]=0;
                MIN[i][j]=0;
            }
        }

        int Ea = Easy(0, K-1);
        int Ha = Hard(0, K-1);

		cout << "Case #" << tc << endl << Ea << " " << Ha << endl;
    }
    return 0;
}