A1.

#include <stdio.h> void main() { // read possible guard couples from file FILE * fp=fopen("schedule.in","r"); if(fp==NULL) { printf("schedule.in doesn't exist\n"); return; } int guard_num; // first scan in order to know how many possible couples fscanf(fp,"%d\n",&guard_num); int length=0; int temp1,temp2; while(fscanf(fp,"%d %d\n",&temp1,&temp2)!=EOF) length++; int * a=new int [length]; int * b=new int [length]; rewind(fp); // second scan in order to read and save data fscanf(fp,"%d\n",&guard_num); int i=0; while(fscanf(fp,"%d %d\n",a+i,b+i)!=EOF) i++; // show all the possible couples /* printf("the possible couples:\n"); for(i=0;i<length;i++) printf("%d %d\n",a[i],b[i]); */ fclose(fp); // find the best schedule to arrange couples int * guard=new int [guard_num+1]; for(i=1;i<=guard_num;i++) guard[i]=0; // a flag array indicating whether a guard was arranged or not // guard[0] is useless int top=-1, top_max=-1; int * stack=new int[length]; int * history=new int[length]; i=0; while(top>=0 || i<length) { while(i<length) { if(guard[a[i]]==0 && guard[b[i]]==0) { // push this couple guard[a[i]]=1; guard[b[i]]=1; top++; stack[top]=i; } i++; } if(top>top_max) { top_max=top; for(i=0;i<=top_max;i++) history[i]=stack[i]; // save stack } i=stack[top]+1; guard[a[stack[top]]]=0; guard[b[stack[top]]]=0; top--; } // output the result printf("%d\n",2*(top_max+1)); for(i=0;i<=top_max;i++) printf("%d %d\n",a[history[i]],b[history[i]]); delete[] a,b,guard,stack,history; }

A2.

#include <stdio.h> #include <math.h> // split b according to a // b is the index of a, range is from head to tail int split(int * a, int * b, int len, int head, int tail) { while(head<tail) { while(a[b[tail]]>=a[b[head]] && tail>head) tail--; if(tail>head) { int temp=b[head]; b[head]=b[tail]; b[tail]=temp; head++; } while(a[b[head]]<=a[b[tail]] && head<tail) head++; if(head<tail) { int temp=b[tail]; b[tail]=b[head]; b[head]=temp; tail--; } } return head; } // quick sort b according to a // b is the index of a, range is from head to tail void quick_sort(int * a, int * b, int len, int head, int tail) { if(head>=0 && tail<len && head<tail) { int mid=split(a,b,len,head,tail); quick_sort(a,b,len,head,mid-1); quick_sort(a,b,len,mid+1,tail); } } // Is it a valid movement ? bool is_valid(int lx,int ly,int nx,int ny,int kk) { if((lx==nx && abs(ly-ny)<=kk)||(ly==ny && abs(lx-nx)<=kk)) return true; else return false; } void main() { // read the scotch from file FILE * fp=fopen("hopscotch.in","r"); if(fp==NULL) { printf("hopscotch.in doesn't exist\n"); return; } int case_num; fscanf(fp,"%d\n",&case_num); for(int case_cnt=0;case_cnt<case_num;case_cnt++) { int n,k,i,j; fscanf(fp,"%d%d\n",&n,&k); int * a=new int [n*n]; // a saves the scotch for(i=0;i<n;i++) { for(j=0;j<n;j++) fscanf(fp,"%d",a+i*n+j); fscanf(fp,"\n"); } // show the scotch /* printf("the scotch is:\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d ",*(a+i*n+j)); printf("\n"); } */ int * b=new int [n*n]; for(i=0;i<n*n;i++) b[i]=i; // b saves the index of a // find the start point int start=split(a,b,n*n,0,n*n-1); // quick sort b quick_sort(a,b,n*n,start+1,n*n-1); // hop int * stack=new int [n*n]; int * history=new int [n*n]; int top=-1,h_top; top++; stack[top]=start; // stack saves the index of b int local_x,local_y,next_x,next_y; int money_sum=a[0],money_max=-1; i=start+1; while(top>=0) { while(i<n*n) { if(a[b[i]]>a[b[stack[top]]]) // there is more money { next_x=b[i]/n; next_y=b[i]-n*next_x; // get the next position local_x=b[stack[top]]/n; local_y=b[stack[top]]-n*local_x; // get the local position if(is_valid(local_x,local_y,next_x,next_y,k)) { // if it is a valid movement .. top++; stack[top]=i; money_sum+=a[b[i]]; } } i++; } if(money_sum>money_max) { // it is the best hop then ever h_top=top; money_max=money_sum; for(i=0;i<=h_top;i++) history[i]=stack[i]; // save the stack } i=stack[top]+1; money_sum-=a[b[stack[top]]]; top--; } // show money_max printf("%d\n\n",money_max); // show the hop trace /* printf("the hop trace is:\n"); for(i=0;i<=h_top;i++) { local_x=b[history[i]]/n; local_y=b[history[i]]-n*local_x; printf("(%d,%d) ",local_x,local_y); } printf("\n"); */ delete[] a,b,stack,history; } fclose(fp); }

A4.

#include <stdio.h> // permute the Harry Potter's fans bool permute(int m,int n,int * array) { if(m==0 || n==0) return false; // all the fans have 50 dollars or 100 dollars // return false implies it is no need to perform next permutation for(int i=m+n-1;i>0;i--) if(array[i]==100 && array[i-1]==50) break; // find the last adjacent 50 100 if(i==0) return false; // no adjacent 50 100 exists int temp=array[i-1]; array[i-1]=array[i]; array[i]=temp; // swap them // inverse the fans from i+1 to the end of queue i++; int j=m+n-1; for(;i<j && array[i]>array[j];i++,j--) { temp=array[i]; array[i]=array[j]; array[j]=temp; } return true; } // Is it a valid queue ? bool valid_queue(int m,int n,int * array) { int dollar_50=0,dollar_100=0; for(int i=0;i<m+n;i++) if(array[i]==50) dollar_50++; else { if(dollar_50==0) // can not make change return false; else { dollar_100++; dollar_50--; } } return true; } // calculate factorial long factorial(int n) { if(n==0) return 1; int f=1; for(int i=2;i<=n;i++) f=f*i; return f; } void main() { // read m n from file FILE * fp=fopen("ticket.in","r"); if(fp==NULL) { printf("ticket.in doesn't exist\n"); return; } // first scan in order to know how many cases int temp1,temp2,case_num=0; while(fscanf(fp,"%d %d\n",&temp1,&temp2)!=EOF) { if(temp1==0 && temp2==0) break; case_num++; } int * m=new int [case_num]; int * n=new int [case_num]; int * number=new int [case_num]; // second scan in order to read and save data rewind(fp); for(int i=0;i<case_num;i++) fscanf(fp,"%d %d\n",m+i,n+i); fclose(fp); // show m and n /* printf("cases:\n"); for(i=0;i<case_num;i++) printf("%d %d\n",m[i],n[i]); */ // find all the possible queues for(int case_cnt=0;case_cnt<case_num;case_cnt++) { number[case_cnt]=0; int * array=new int [m[case_cnt]+n[case_cnt]]; // initiate the queue // 50 in front of 100 for(i=0;i<m[case_cnt];i++) array[i]=50; for(;i<m[case_cnt]+n[case_cnt];i++) array[i]=100; do { if(valid_queue(m[case_cnt],n[case_cnt],array)) number[case_cnt]++; } while(permute(m[case_cnt],n[case_cnt],array)); number[case_cnt]*=factorial(m[case_cnt])*factorial(n[case_cnt]); delete [] array; } // output the results for(case_cnt=0;case_cnt<case_num;case_cnt++) { printf("test #%d:\n",case_cnt+1); printf("%d\n",number[case_cnt]); } }