Solution Notes: The problem is solved by "brute force", by enumerating through all possible subsets of cows and keeping track of the largest one that fits on the raft. One way to do this enumeration is recursively, shown in the code below, where we consider cow #1 and then recursively enumerate all solutions that do contain cow #1, and then all solutions that do not contain cow #1. Along the way, we prune the search and backtrack if we ever notice that our current solution is infeasible (i.e., if it generates a carry), or if the number of cows remaining plus the number of cows we have used so far cannot possibly do better than the best solution we have generated thus far.

Another nice "trick" for enumerating all 2^20 subsets of cows for this problem is to simply count from 0 up to 2^20-1. The 0s and 1s in the binary representation of our integer counter tell us a particular subset, and we will generate every possible subset as we count. For example, if the counter is (in binary) 10011000000000000000, then this means we are considering a subset that includes cows 1, 4, and 5 (the positions of the 1 bits).

#include <fstream>

using namespace std;
int n, w[20], best=0;

/* Can x and y be added with no carries? */
int check(int x, int y)
{
   for ( ; x>0 && y>0; x/=10,y/=10)
      if (x%10+y%10>=10) return 0;
   return 1;
}

/* 
   x = index into w array we're currently considering (i.e., we have already 
   added a subset of w[1...x-1] and are considering whether to add w[x]).
   sum = cumulative sum of subset added so far.
   count = number of elements in subset added so far.
*/
void rec(int x, int sum, int count)
{
   if (count>best) best=count;
   if (x>=n || count+n-x<=best) return;
   if (check(sum,w[x]))
      rec(x+1,sum+w[x],count+1);
   rec(x+1,sum,count);
}

int main()
{
   ifstream fin("escape.in");
   ofstream fout("escape.out");

   fin >> n;
   for (int i=0; i<n; i++)
      fin >> w[i];
   fin.close();

   rec(0,0,0);

   fout << best << endl;
   fout.close();
   return 0;
}