Advertisement
Guest User

Turing 10-1

a guest
Dec 4th, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.40 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <memory.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. typedef struct nb {
  7.     int num;
  8.     struct nb *next;
  9. }Nb;
  10.  
  11. int pary,dievcata,chlapci,pos[100][100], count[100], C[2][1024], idx;;
  12. char **inMatrix;
  13.  
  14. void addNb(Nb **head, int data) {
  15.     Nb *curr = *head;
  16.     Nb *new = (Nb *) malloc(sizeof(Nb));
  17.     new->num = data;
  18.     new->next = NULL;
  19.     if(curr != NULL) {
  20.         while(curr -> next != NULL){
  21.             curr = curr -> next;
  22.         }
  23.         curr -> next = new;
  24.     }
  25.     else *head = new;
  26. }
  27.  
  28. int numOfOnes (int subset) {
  29.     int ret = 0, numCpy = subset, mask = 0x1;
  30.     while(numCpy > 0) {
  31.         if(numCpy&mask == 1) ret++;
  32.         numCpy = numCpy >> 1;
  33.     }
  34.     return ret;
  35. }
  36.  
  37. int main() {
  38.  
  39.     int subsets, i, j, k, currNb, p;
  40.  
  41.  
  42.     freopen("/Users/msMac/FIIT 3. semester/DSA/Turing10/in3.txt", "r", stdin);
  43.  
  44.     while(scanf("%d\n",&pary)!=EOF) {
  45.         scanf("%d %d\n",&chlapci,&dievcata);
  46.         subsets = 1 << chlapci;
  47.         memset(count, 0, sizeof(count));
  48.  
  49.         Nb **nbs = (Nb **) malloc(chlapci*sizeof(Nb*));
  50.         inMatrix = (char **) malloc(chlapci * sizeof(char *));
  51.         for(i = 0; i < chlapci; i++) {
  52.             inMatrix[i] = (char *) malloc(dievcata* sizeof(char));
  53.             scanf("%s",inMatrix[i]);
  54.             nbs[i] = NULL;
  55.         }
  56.  
  57.         for(i=0;i<chlapci;i++) {
  58.             for(j=0;j<dievcata;j++) {
  59.                 if(inMatrix[i][j] == 'Y') addNb(&nbs[i],j+1);
  60.             }
  61.         }
  62.  
  63.         for(i=0,p=1;i<chlapci;i++,p<<=1) {
  64.             Nb *curr = nbs[i];
  65.             while(curr!=NULL) {
  66.                 currNb = curr->num;
  67.                 pos[currNb][count[currNb]++] = p;
  68.                 curr = curr->next;
  69.             }
  70.         }
  71.         memset(C[0], 0, sizeof(C[0]));
  72.         C[0][0] = 1;
  73.         idx = 0;
  74.         for(i=0;i<10;i++) {
  75.             idx = !idx;
  76.             for(j=0;j<subsets;j++)
  77.                 C[idx][j] = C[!idx][j];
  78.             for(j=0;j<count[i];j++) {
  79.                 for(k=0;k<subsets;k++) {
  80.                     if (C[!idx][k] && !(k&pos[i][j])) {
  81.                         C[idx][k|pos[i][j]] = (C[!idx][k]+ C[idx][k|pos[i][j]]);
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.         int sum = 0;
  87.         for(i = subsets ; i>0 ; i --) {
  88.             if(numOfOnes(i)==pary) sum += C[idx][i];
  89.         }
  90.         printf("%d\n", sum);
  91.     }
  92.  
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement