CMED01 - Editorial

Problem Name:

Coin Game

Author: Uttam Singh
Tester: Vivek Solanki
Editorialist: Uttam Singh

DIFFICULTY:

Simple - Easy

PREREQUISITES:

Math, Array

PROBLEM:

There are n piles of coins, where the i_t pile has a_i coins. You need to collect the maximum number of coins from these piles, but you must fulfill the following condition:

Let’s say you pick x_i coins from the i_t pile, then:

  • x1+x3+x5… = x2+x4+x6
  • 0 \leq x_i \leq a_i

For example, if n=3 and, a=[2,3,2], you can pick the coins as x= [1,2,1] becuase x1+x3=1+1=2 and x2=2
Find the maximum total number of coins you can pick.

EXPLANATION:

We need to collect the maximum number of coins from the piles but we have to keep in mind that the sum of the odd position coins should be equal to the sum of the even position coins in the piles.
So the simplest way to solve this problem is to get the sum of odd positions(say odd) and even(say even) positions coins individually then print out the minimum of those two. (Minimum - (odd, even))

SOLUTIONS:

#include <iostream>
using namespace std;

int main() {
    int n, even_sum=0, odd_sum=0;
    cin>>n;
    int *a = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if((i+1)%2==0){
            even_sum += a[i];
        }
        else{
            odd_sum += a[i];
        }
    }

    int min_ans = (even_sum<odd_sum)?even_sum:odd_sum;
    cout << 2*min_ans << endl;
    return 0;
}

where it is told that we have to find odd = even sum