//
//
import java.io.*;

import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.cp.solver.search.integer.varselector.StaticVarOrder;
import choco.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerVariable;

public class Optimize {

  
  public static void main(String[] args) throws FileNotFoundException, IOException {
      MyIo fin            = new MyIo(args[0]);
      int n               = fin.getNextInt(); // number of numbers
      Model m             = new CPModel();
      IntegerVariable L[] = new IntegerVariable[n];
      IntegerVariable R[] = new IntegerVariable[n];
      IntegerVariable D[] = new IntegerVariable[n];
      int w[]             = new int[n];
      int tot             = 0;                // sum of w[i]
      for (int i=0;i<n;i++){
	  w[i] = fin.getNextInt();
	  L[i] = makeIntVar("L[" + i + "]",0,w[i]);
	  R[i] = makeIntVar("R[" + i + "]",0,w[i]);
	  D[i] = makeIntVar("D[" + i + "]",0,1);
	  tot  = tot + w[i];
      }

      fin.close();

      for (int i=0;i<n;i++){
	  m.addConstraint(ifOnlyIf(eq(D[i],0),and(eq(L[i],w[i]),eq(R[i],0))));
	  m.addConstraint(ifOnlyIf(eq(D[i],1),and(eq(R[i],w[i]),eq(L[i],0))));
      }
      
      IntegerVariable absDiff = makeIntVar("diff",0,tot);
      m.addConstraint(eq(absDiff,abs(minus(sum(L),sum(R))))); // absDiff = |sum(L) - sum(R)| 

      Solver s = new CPSolver(); 
      s.read(m); 
      s.setVarIntSelector(new StaticVarOrder(s.getVar(D)));
      s.minimize(s.getVar(absDiff),false);                   // minimize (false?)
      s.printRuntimeSatistics();
      System.out.println("feasible: " + s.isFeasible());

      if (s.isFeasible()){
	  for (int i=0;i<n;i++)
	      System.out.print(w[i] + ":" + s.getVar(D[i]).getVal() + " ");
	  System.out.println();
      }

  }
}
//
// Questions
// (1) Could we increase the amount of propagation?
// (2) What would we get with s.minimize(s.getVar(absDiff),true)?
// (3) np40 ... anyone? 
// (4) Can we put a limit on search, i.e sacrafice completeness?
//