Removing chips.

Good day, I need to help with algorithm in program ... The task is

The task is to create a program that will solve the logical game - picking up chips.


The game is played by two players A and B. There are 1 to 100 chips placed on the table. Each token has a written value, the value is an integer (positive, zero, or negative). Players are alternating starting with Player A. The player on the move can take 1 to 2 tokens at his choice. In addition, the player may not take two tokens in two consecutive turns (if the player takes one token in one move, he must take only one token in his next draw). You can only collect tokens from the beginning, the end, or both. The game ends when one of the players takes the last token. The player who has earned the greater sum of their chips wins.


We assume that both players play absolutely efficient. Each player then picks up the chips to get the highest total of their chips. The challenge is to find a sequence of these effective moves and determine who will win.


The input of the program is a sequence of integers. These numbers represent the values ​​of the chips as they are side by side on the table. When we pick up the chips, we refer to their tokens (0 to number-1).


The output of the program is a found sequence of moves of individual players. Each move is on a separate line. The strokes are always based on player ID (A or B, alternate) followed by the token index (the index can be one or two according to the number of chips removed) and ends with the value (s) of the chips taken. The last line of the exit is information about the chip totals of both players.

I'm really sorry but i have no idea what to do ... I got only the begining ..

Code:

---


#include <stdio.h>
#include <stdlib.h>


int compute( int array[], int max ){              /* function, that remove tokens */


    int i = 0, sumA, sumB;
    int *A, *B;                                    /* arrays, where saving variables */
    A = (int*)malloc(max * sizeof(A));
    B = (int*)malloc(max * sizeof(B));


   


}






int main()
{


    int *data;
    int i, k, tokens;
    data = (int*)malloc(sizeof(data));                          /* allocate memory */
    i = 0;


    printf("Zetony\n");


    while( scanf(" %d", &tokens ) != EOF){                      /* Load inputs, while not EOF */
        data[i] = tokens;
        i++;
        data = (int*)realloc(data, (i + 1) * sizeof(data));      /* reallocate memory */
        if ( data == NULL ) {                                    /* if cant allocate */
            free(data);
            printf("Nespravny vstup.\n");
            return 0;
        }
    }


    if(i > 100){
        free(data);
        printf("Nespravny vstup.\n");
        return 0;
    }


    compute(data, i);




    return 0;
}

---

And I dont know, what should be my next move. Please help me to understand this problem and give me some help or advice. Thank you.

Results of this program are

Code:

---


 Chips:-57 87 -75 117 44 96
A [5]: 96
B [4], [3]: 44 + 117
A [0], [1]: -57 + 87
B [2]: -75
A: 126, B: 86


Chips:
73 -7 118 86 11 -11 83
A [6]: 83
B [0]: 73
A [1], [2]: -7 + 118
B [3], [4]: 86 + 11
A [5]: -11
A: 183, B: 170


Chips:
-34 -1 94 111 43 78 -79 13
A [0], [7]: -34 + 13
B [6], [5]: -79 + 78
A [1]: -1
B [2]: 94
A [4], [3]: 43 + 111
A: 132, B: 93


Chips:
-72 36 -2 42 139 116 -59 -31 -34
A [8], [7]: -34 + -31
B [6]: -59
A [5]: 116
B [4]: 139
A [3]: 42
B [2], [1]: -2 + 36
A [0]: -72
A: 21, B: 114


Chips:
131 8 97 -68 -79 135 -93 -61 -4 -61
A [0], [9]: 131 + -61
B [1], [2]: 8 + 97
A [8]: -4
B [3]: -68
A [4], [5]: -79 + 135
B [7]: -61
A [6]: -93
A: 29, B: -24

---

Think, I can do it with recurcsion, if I'll chek all combinations. But have no idea, how to.

I wonder if the 100-chip game tree may be too large for an exhaustive search.
If it can be done then you'll want to use the mini-max procedure.