One afternoon your cell phone rings; it’s your cousin Jimmy. "Hi Cuz," he says, "I need your help and I need it fast. I’m in the middle of a programming contest and however hard I try, I can’t get one problem to finish within the two second time limit." "Hmm... well..., isn’t that a bit illegal?", you try to say to him. But he rattles on. "I just snook out of the contest room and managed to send you my code and the sample I/O by email", he continues without pausing. "I will check my mail again in an hour, so please make it work for me." "What about the problem description?", you ask. "Can’t do", he says, "Zoroman the Head Judge is already on my tail, so I got to go. Bye, ... and, eh, thanks." Are you going to help him? Jimmy’s Code #include <stdio.h> #define~MAX_BOLTS~500 #define~MAX_NUTS~~500 /~global~copy~of~the~input~data~/ int~nuts,bolts; int~fits[MAX_BOLTS][MAX_NUTS]; void~read_input_data(void){ int~n,b; scanf("%d%d",&bolts,&nuts); for(b=0;b<bolts;b++){ for(n=0;n<nuts;n++){ scanf("%d",&fits[b][n]); } } } /* data used to match nuts with bolts */ int nut_used[MAX_NUTS]; int bestmatched; void~init_match(void){
2/3 int n; bestmatched=0; for(n=0;n<nuts;n++)~nut_used[n]=0; } void match_bolt(int boltno, int matched){ int n; if(boltno==bolts){ if(matched>bestmatched) bestmatched=matched; return; } /* don't match this bolt / match_bolt(boltno+1,matched); /~match~with~all~unused~nuts~that~fit~this~bolt~*/ for(n=0;n<nuts;n++)~if(!nut_used[n] && fits[boltno][n]){ nut_used[n]=1; match_bolt(boltno+1,matched+1); nut_used[n]=0; } } int~main(){ int~cases,caseno; scanf("%d",&cases); for(caseno=1;caseno<=cases;caseno++){ read_input_data(); init_match(); match_bolt(0,0); printf("Case %d: ",caseno); printf("a maximum of %d nuts and bolts ",bestmatched); printf("can be fitted together\n"); } return~0; } This is the code that Jimmy sent you by email. Input A file similar to the Sample Input below, that you must understand after reading the code. Output The corresponding solution to the input file after running the code corresponding variation (if needed) of Jimmy’s code.
3/3 Sample Input 2 34 0010 1101 0010 55 10011 11000 10000 01100 00001 Sample Output Case 1: a maximum of 2 nuts and bolts can be fitted together Case 2: a maximum of 5 nuts and bolts can be fitted together