/* file : timetables.c */ /* author : Oscar MirĂ³ (o.miro.i.lopez.feliu@student.rug.nl) */ /* Description: * Receives input n, then n lines of inputs. Each of these receiving 3 ints each. * Forms a matrix with these, then finds if its possible to select a different number * from each row, then outputs how many rows could have their first column chosen. */ #include int rec (int size, int assigned[size], int input[size][3], int position, int count, int arr[]) { // checks if on end of the branch if (position == size) { // returns 1 and stores count to the pointer if (arr[0] < count) arr[0] = count; return 1; } // iterates 3 times, for every number in input. If unselected, branches out and selects int n = 0; for (int i = 0; i < 3; i++) { if (assigned[input[position][i]] == 0) { if (i == 0) count++; assigned[input[position][i]]++; n+= rec(size, assigned, input, position + 1, count, arr); if (i == 0) count--; assigned[input[position][i]]--; } } return n; } int main (int argc, char *argv[]) { // declaration and assigning int size; scanf("%d", &size); int input[size][3], assigned[size], arr[1] = {0}; // initializes array and scans for (int i = 0; i < size; i++) { assigned[i] = 0; scanf("%d %d %d", &input[i][0], &input[i][1], &input[i][2]); } // prints appropiate output int max = rec(size, assigned, input, 0, 0, arr); if (max) { printf("%d\n", arr[0]); } else { printf("IMPOSSIBLE\n"); } }