Sharing and odd pizza

Question

Here is a classical problem, which every mathematician will have seen at least onece in their life:

Anne and Ben are sharing a pizza. The pizza is divided into an even number of pieces of unequal sizes. Anne takes the first slice, and then she and Ben alternate, always taking slices adjacent to the created hole (so that the remaining part of the pizza remains connected). Can Anne always guarantee that she gets at least as much pizza as Ben?

If you haven't seen this one yet, you might want to give it a minute's thought. Hint: the solution is simple and elegant. It's useful to separate the pizza into "even" and "odd" pieces.

Question: What happens when the pizza is divided into an odd number of pieces?

Clearly, for $3$ pieces Alice can guarantee to eat $\geq 1/2$ of pizza (but can't in general do better). Does this remain true in general?

Answer 1

Maybe this helps: You give it the pizza slices and it gives you the max pizza amount that player $A$ can guarantee.

#include <bits/stdc++.h>
using namespace std;

int A[100];

int maxline( vector <int> V){ //this solves the problem when the slices are in a line
    int N=V.size();
    int M[100][100]; //M[i][j] stores the max pizza amount 
                    //when we only consider slices i,i+1...i+j-1
    for(int i=1;i<=N;i++){
        for(int j=0;j+i-1<N;j++){ //here we fill the matrix recursively with linear programming
            if(i==1) M[j][i]=V[j];
            if(i==2) M[j][i]= max(V[j],V[j+1]);
            if(i>2) M[j][i]= max( V[j] + min(M[j+2][i-2],M[j+1][i-2]), V[j+i-1]+min(M[j][i-2],M[j+1][i-2]));
        }
    }
    return(M[0][N]);
}

int main(){
    int N,T=0,res=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
        T+=A[i];
    }
    for(int i=0;i<N;i++){ // this just iterates over all possible first picks.
        vector <int> V;
        for(int j=(i+1)%N;j!=i;j=(j+1)%N){
            V.push_back(A[j]);
        }
        res=max(res,T-maxline(V));
    }
    printf("%d\n",res);
}