Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <memory.h>
- #include <stdlib.h>
- typedef struct nb {
- int num;
- struct nb *next;
- }Nb;
- int pary,dievcata,chlapci,pos[100][100], count[100], C[2][1024], idx;;
- char **inMatrix;
- void addNb(Nb **head, int data) {
- Nb *curr = *head;
- Nb *new = (Nb *) malloc(sizeof(Nb));
- new->num = data;
- new->next = NULL;
- if(curr != NULL) {
- while(curr -> next != NULL){
- curr = curr -> next;
- }
- curr -> next = new;
- }
- else *head = new;
- }
- int numOfOnes (int subset) {
- int ret = 0, numCpy = subset, mask = 0x1;
- while(numCpy > 0) {
- if(numCpy&mask == 1) ret++;
- numCpy = numCpy >> 1;
- }
- return ret;
- }
- int main() {
- int subsets, i, j, k, currNb, p;
- freopen("/Users/msMac/FIIT 3. semester/DSA/Turing10/in3.txt", "r", stdin);
- while(scanf("%d\n",&pary)!=EOF) {
- scanf("%d %d\n",&chlapci,&dievcata);
- subsets = 1 << chlapci;
- memset(count, 0, sizeof(count));
- Nb **nbs = (Nb **) malloc(chlapci*sizeof(Nb*));
- inMatrix = (char **) malloc(chlapci * sizeof(char *));
- for(i = 0; i < chlapci; i++) {
- inMatrix[i] = (char *) malloc(dievcata* sizeof(char));
- scanf("%s",inMatrix[i]);
- nbs[i] = NULL;
- }
- for(i=0;i<chlapci;i++) {
- for(j=0;j<dievcata;j++) {
- if(inMatrix[i][j] == 'Y') addNb(&nbs[i],j+1);
- }
- }
- for(i=0,p=1;i<chlapci;i++,p<<=1) {
- Nb *curr = nbs[i];
- while(curr!=NULL) {
- currNb = curr->num;
- pos[currNb][count[currNb]++] = p;
- curr = curr->next;
- }
- }
- memset(C[0], 0, sizeof(C[0]));
- C[0][0] = 1;
- idx = 0;
- for(i=0;i<10;i++) {
- idx = !idx;
- for(j=0;j<subsets;j++)
- C[idx][j] = C[!idx][j];
- for(j=0;j<count[i];j++) {
- for(k=0;k<subsets;k++) {
- if (C[!idx][k] && !(k&pos[i][j])) {
- C[idx][k|pos[i][j]] = (C[!idx][k]+ C[idx][k|pos[i][j]]);
- }
- }
- }
- }
- int sum = 0;
- for(i = subsets ; i>0 ; i --) {
- if(numOfOnes(i)==pary) sum += C[idx][i];
- }
- printf("%d\n", sum);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement