/*
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);
}