Thread: Removing chips.

  1. #1
    Registered User
    Join Date
    Nov 2017
    Posts
    12

    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

  2. #2
    Registered User
    Join Date
    Nov 2017
    Posts
    12
    Think, I can do it with recurcsion, if I'll chek all combinations. But have no idea, how to.

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    631
    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.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. new amd phenom ii x6 chips =]
    By doubleanti in forum General Discussions
    Replies: 15
    Last Post: 04-29-2010, 09:49 PM
  2. Chips
    By Liger86 in forum A Brief History of Cprogramming.com
    Replies: 40
    Last Post: 06-06-2003, 01:10 AM
  3. SiS chips and Linux
    By windoze victim in forum Tech Board
    Replies: 2
    Last Post: 11-28-2002, 10:11 AM
  4. Chips
    By Fordy in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 10-27-2002, 06:36 PM

Tags for this Thread