分石头

// 更新:下边这种放砝码的思路是不对的，其本质是贪心，这道题应该使用动态规划
// 测试样例9,8,7,5,3正确答案是16,16，贪心得到的答案是17,15
// 放砝码的思路
import java.io.*;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(",");
        int[] arr = new int[strs.length];
        for(int i = 0; i < arr.length; i++)
            arr[i] = Integer.parseInt(strs[i]);
        Arrays.sort(arr);
        int left = 0, right = 0;
        // 从大到小取数
        for(int i = arr.length-1; i >= 0; i--){
            if(left > right) right += arr[i];
            else left += arr[i];
        }
        if(left > right) System.out.println(left+","+right);
        else System.out.println(right+","+left);
    }
}
// 正确做法如下:
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(",");
        br.close();
        int[] arr = new int[strs.length];
        int sum = 0, vol = 0;
        for(int i = 0; i < arr.length; i++)
            sum += arr[i] = Integer.parseInt(strs[i]);
        vol = sum>>1;
        // 求解背包容量为sum/2的背包问题
        int[] memo = new int[vol+1];
        for(int i = 0; i < arr.length; i++)
            for(int j = vol; j >= arr[i]; j--)
                if(arr[i]+memo[j-arr[i]] > memo[j]) memo[j] = arr[i]+memo[j-arr[i]];
        System.out.println((sum-memo[vol])+","+memo[vol]);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        String[] ss=s.split(",");
        int[] arrs=new int[ss.length];
      
        int sum=0;
        for(int i=0;i<ss.length;i++){
            arrs[i]=Integer.valueOf(ss[i]);
            sum+=arrs[i];
        }
        int mid=sum/2;
        boolean[] dp=new boolean[mid+1];
        dp[0]=true;
        for(int i=0;i<arrs.length;i++){
            for(int j=mid;j>=0;j--){
                dp[j]=dp[j]||(j-arrs[i]>=0?dp[j-arrs[i]]:false);
            }
        }
        int res=0;
        for(int i=mid;i>=0;i--){
            if(dp[i]){
                res=i;
                break;
            }
        }
        int y=sum-res;
        System.out.println(y+","+res);
        
    }
}

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> nums = new ArrayList<Integer>() {{add(0);}};
        int ans = 0,max = 0;
        String[] instring = sc.next().split(",");
        for (int i=0; i!=instring.length; i++) {
            int in = Integer.valueOf(instring[i]);
            ans += in;
            max = Math.max(max, in);
            nums.add(in);
        }
        int target = ans / 2, n = nums.size()-1;
        boolean[] dp = new boolean[max + 5];
        dp[0] = true;
        for (int i=1; i<=n; i++) {
            int cur = nums.get(i);
            for (int j=target; j>=cur; j--) {
                dp[j] |= dp[j-cur];
            }
        }
        for (int i=target; i>=0; i--) {
            if (dp[i] == true) {
                System.out.printf("%d,%d\n", Math.max(i, ans-i), Math.min(i, ans-i));
                return;
            }
        }
    }
}

w=[int(x) for x in input().split(',')]
w=sorted(w)
max,m=0,0
for i in range(len(w)-1):
    if w[i+1]-w[i]>=max:
        max=w[i+1]-w[i]
        m=i
L=w[:m+1]
R=w[m+1:]
sumL,sumR=0,0
for x in L:
    sumL+=x
for y in R:
    sumR+=y
if w==[1]:
    print('1,0')
else:
    print("%d,%d"%(sumR,sumL))

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String[] str = input.nextLine().split(",");
        int len = str.length;
        int[] a = new int[len];
        for(int i = 0;i<len;i++){
            a[i] = Integer.valueOf(str[i]);
        }
        Arrays.sort(a);
        int sum = 0;
        for(Integer i:a){
            sum+=i;
            
        }
        int total = 0;
        int index= len-1;
        while(total<sum-total){
            total+=a[index];
            index--;
            }
      System.out.println(total +","+ (sum-total));

    }
}

s = list(map(int, input().split(",")))
s.sort(reverse=True)
a = []
b = [] for i in s:  if sum(a)-sum(b) == 0:
        a.append(i)  else:
        b.append(i)  c=[]
c.append(sum(a))
c.append(sum(b)) print(','.join(str(i) for i in c))

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    vector<int>data;
    for(int i=0;i<s.length();i+=2){
        int x = s[i]-'0';
        data.push_back(x);
    }
    sort(data.begin(),data.end());
    int length=data.size();
    int sum=0;
    for(int i=0;i<length;i++){
        sum+=data[i];
    }
    int ans=0;
    if(length==1){
        cout<<data[0]<<","<<0<<endl;
        return 0;
    }
    else if(length==2){
        cout<<data[1]<<","<<data[0]<<endl;
        return 0;
    }
    else{
        if(data[length-1]>=sum/2){
            ans = data[length-1];
        }
        else{
            int target = sum/2;
            int csum=data[length-1];
            for(int i=0;i<length-1;i++){
                csum+=data[i];
                if(csum==target){
                    ans=sum-target;
                }
                if(csum>target){
                    break;
                }
            }
        }
    }
    cout<<ans<<","<<sum-ans<<endl;
    return 0;
}

arr=list(map(int,input().split(',')))
arr=sorted(arr,reverse=True)
a,b=0
for x in arr:
    if(a==b):
        a+=x
    else:
        if (abs(a + x - b) < abs(b + x - a)):
            a += x
        else:
            b += x
print('{},{}'.format(a,b))

	

int main() {
    vector<int> v;
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i += 2) {
        int temp = s[i] - '0';
        v.push_back(temp);
    }
    sort(v.begin(),v.end());

    if (v.size() == 1) {
        cout << v[0] << "," << 0;
        return 0;
    }
    int left = 0;
    int right = v.size() - 1;
    int sum1 = v[left];
    int sum2 = v[right];
    while(left < right) {
        if(sum1 <= sum2) {
            left++;
            if(left < right)
                sum1 += v[left];
        } else {
            right --;
            if(left < right)
                sum2 += v[right];
        }
    }
    if(sum1 > sum2) {
        cout << sum1 << "," << sum2;
    } else {
        cout << sum2 << "," << sum1;
    }

    return 0;
}