/*
NAME: Ivan Anev
PROG: setfree
LANG: C


ЕСЕНЕН  ТУРНИР  ПО  ИНФОРМАТИКА ШУМЕН'02 - 16 ноемв░и 2002
ТЕМА 11-12 КЛАС (ГРУПА  А)

Зада╖а 3. ТРОИЧНИ  КАРТИ

В иг░а▓а УМноже▒▓ваФ │╖а▒▓ва▓ 81 ка░▓и. В▒┐ка ка░▓а има 4 а▓░иб│▓а (A, B, C и
D), ка▓о в▒еки а▓░иб│▓ има една о▓ ▓░и в║зможни ▒▓ойно▒▓и (0,1 или 2).

Т░и ка░▓и об░аз│ва▓ множе▒▓во, кога▓о за в▒еки а▓░иб│▓ ▒▓ойно▒▓и▓е на ▓░и▓е
ка░▓и ▒а или еднакви или ░азли╖ни.

Нап░име░ ▒ледни▓е ▓░и ка░▓и об░аз│ва▓ множе▒▓во:

         A   B   C   D
Ка░▓а 1  2   2   1   0
Ка░▓а 2  0   2   1   2
Ка░▓а 3  1   2   1   1

В ▒ледва╣и┐ п░име░ никои ▓░и о▓ по▒о╖ени▓е ка░▓и не об░аз│ва▓ множе▒▓во:

          A   B   C   D
Ка░▓а 1   0   1   0   0
Ка░▓а 2   1   0   0   0
Ка░▓а 3   1   1   0   1
Ка░▓а 4   1   1   1   1
Ка░▓а 5   1   2   1   2
Ка░▓а 6   2   2   0   2
Ка░▓а 7   2   1   1   0

Как║в е мак▒имални┐▓ б░ой ка░▓и, кои▓о не ▒║д║░жа▓ множе▒▓во ?

Да ▒е ▒║здаде ▓ек▒▓ов ┤айл ▒ име  SETFREE.TXT ▒║▒ ▒ледна▓а ▒▓░│к▓│░а:
Ц на п║░ви┐ ░ед ▓░┐бва да е запи▒ано едно ╖и▒ло N Ц наме░ени┐▓ мак▒имален
б░ой;
Ц на ▒ледва╣и▓е N ░еда Ц по ╖е▓и░и ╖и▒ла, ░азделени ▒ ин▓е░вал Ц ▒▓ойно▒▓и▓е
на а▓░иб│▓и▓е за в▒┐ка о▓ N-▓е ка░▓и, кои▓о не ▒║д║░жа▓ множе▒▓во.

П░авила за о╢ен┐ване: То╖ки▓е, кой▓о ╣е пол│╖и▓е ▒а 100*N/Nmax, к║де▓о Nmax е
мак▒имални┐▓ в║зможен б░ой. Анализ на зада╖а 3: Т░ои╖ни ка░▓и


РЕШЕНИЕ:

П░еди в▒и╖ко ▓░┐бва да ▒е каже ╖е най-доб░о▓о ░е╕ение на зада╖а▓а е 20. К║м
зада╖а▓а има два под╡ода. Едини┐▓ е ▒ ползване на комп╛▓║░, д░│ги┐▓ е да ▒е
нами░а ░е╕ение на ░║ка. Н┐кой ╡о░а ▒▓игна╡а до забележи▓елни▓е 18 ка░▓и ▒
░е╕аване на ░║ка, кое▓о ▒ледвайки н┐колко набл╛дение не е ╖ак ▓олкова ▓░│дно.
Аз ли╖но ▒║м по╖и▓а▓ел на ░е╕аване на зада╖и▓е ▒ помо╣▓а на комп╛▓║░.

Под╡од║▓ е н┐как║в вид п║лно из╖е░пване. П║░во гене░и░аме в един ма▒ив в▒и╖ки
ка░▓и ка▓о ▒▓ойно▒▓и за по ле▒на ░або▓а. По▒ле по╖ваме ▒амо▓о ▓║░▒ене.
По▒▓ав┐ме п║░ва▓а ка░▓а в гене░и░ано▓о ░е╕ение (▓ова не ни ог░ани╖ава ▒ ни╣о
▓║й ка▓о ка░▓и▓е ▒а еднакви и ▒ледова▓елно в▒┐ко ░е╕ение, кое▓о не ▒║д║░жа
п║░ва▓а ка░▓а може да ▒е п░еоб░аз│ва в ▓акова ▒║д║░жа╣о п║░ва▓а ка░▓а). По▒ле
п░ове░┐ваме в▒┐ка о▓ ▒ледва╣и▓е ка░▓и дали може да ▒е по▒▓ави в ▓ек│╣о▓о
░е╕ение и за в▒┐ка, ко┐▓о може да ▒е по▒▓ави поо▓делно ┐ по▒▓ав┐ме и на ▒вой
░ед п░ове░┐ваме за в▒┐ка о▓ ▒ледва╣и▓е по аналоги╖ен на╖ин. Така по▒о╖ено▓о
░е╕ение о▓к░ива ░е╕ение за около 5 ▒ек. ░е╕ение ▒ д║лжина 20.
*/

#include <stdio.h>
#include <string.h>

#define MAXC 81

int cards[MAXC][4];
int best, bc[MAXC];
int current[MAXC];
int v[MAXC];

void init(void);
void solve(void);

int main(void) {
	init();
	solve();

	return 0;
}

void init(void) {
	int i, j, k, l, c;

	c = 0;
	for (i = 0; i < 3; ++i)
		for (j = 0; j < 3; ++j)
			for (k = 0; k < 3; ++k)
				for (l = 0; l < 3; ++l) {
					cards[c][0] = i;
					cards[c][1] = j;
					cards[c][2] = k;
					cards[c++][3] = l;
				}
}

void solve(void) {
	void search(int len, int st);

	current[0] = 0;
	v[0] = 1;
	search(1, 1);
}

void search(int len, int st) {
	int i;
	FILE *fout;

	int canadd(int c, int len);

	if (len > best) {
		best = len;
		for (i = 0; i < best; ++i)
			bc[i] = current[i];

		fout = fopen("setfree.txt", "w");
		for (i = 0; i < len; ++i)
			fprintf(fout, "%d %d %d %d\n", cards[current[i]][0], cards[current[i]][1], cards[current[i]][2], cards[current[i]][3]);
		fclose(fout);
	}

	if (MAXC - st + len > best) {
		for (i = st; i < MAXC; ++i)
			if (v[i] == 0)
				if (canadd(i, len)) {
					current[len] = i;
					v[i] = 1;
					search(len + 1, i + 1);
					v[i] = 0;
				}
	}
}

int canadd(int c, int len) {
	int i, j;

	int isset(int a, int b, int c);

	for (i = 0; i < len; ++i)
		for (j = i+1; j < len; ++j)
			if (isset(current[i], current[j], c))
				return 0;

	return 1;
}

int isset(int a, int b, int c) {
	return ((cards[a][0] + cards[b][0] + cards[c][0]) % 3 == 0 &&
		(cards[a][1] + cards[b][1] + cards[c][1]) % 3 == 0 &&
		(cards[a][2] + cards[b][2] + cards[c][2]) % 3 == 0 &&
		(cards[a][3] + cards[b][3] + cards[c][3]) % 3 == 0);
}