USACO : Healthy Holsteins

/*
ID: tausiq11
PROG: holstein
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

struct state {
	int arr [25 + 3];
	int step;
	int bitmask;
} a [32768 + 100];

int len;
int finalBitmask;
int finalBitCnt;

void checkBestSolution (int p)
{
	if ( finalBitCnt < a [p].step ) return;
	if ( finalBitCnt > a [p].step ) {
		finalBitCnt = a [p].step;
		finalBitmask = a [p].bitmask;
		return;
	}

	for ( int i = 0; i < 15; i++ ) {
		if ( (finalBitmask & (1 << i)) && !(a [p].bitmask & (1 << i)) ) return;
		if ( !(finalBitmask & (1 << i)) && (a [p].bitmask & (1 << i)) ) {
			finalBitCnt = a [p].step;
			finalBitmask = a [p].bitmask;
			return;
		}
	}
}

int main ()
{
	Rd ("holstein.in");
	Wt ("holstein.out");

	int v; scanf ("%d", &v);

	for ( int i = 0; i < v; i++ ) scanf ("%d", &a [0].arr [i]);
	a [0].step = 0;
	a [0].bitmask = 0;

	int g; scanf ("%d", &g);
	int temp [25 + 3];

	len = 1;
	finalBitCnt = g;
	finalBitmask = (1 << g) - 1;

	for ( int i = 0; i < g; i++ ) {
		for ( int j = 0; j < v; j++ ) scanf ("%d", &temp [j]);

		for ( int j = 0; j < len; j++ ) {

			bool allSet = true;
			a [len + j].step = a [j].step + 1;
			a [len + j].bitmask = a [j].bitmask | (1 << i);

			for ( int k = 0; k < v; k++ ) {
				a [len + j].arr [k] = a [j].arr [k] - temp [k];

				if ( a [len + j].arr [k] > 0 ) allSet = false;
			}

			if ( allSet ) {
				checkBestSolution (len + j);
			}
		}

		len *= 2;
	}

	printf ("%d", finalBitCnt);

	for ( int i = 0; i < g; i++ ) {
		if ( finalBitmask & (1 << i) ) printf (" %d", i + 1);
	}

	printf ("\n");

	return 0;
}

// @END_OF_SOURCE_CODE