daily pastebin goal
10%
SHARE
TWEET

MH

a guest Oct 7th, 2009 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: teh_min1
  3. PROG: checker
  4. LANG: C
  5. Checker Challenge
  6. Done by Teh Ming Han
  7. */
  8.  
  9. /*
  10. Algorithm: Recursion
  11.  
  12. Notes:
  13. If n is even, we can compute half a board and then flip along the x axis to generate the other half of the board.
  14. this means we only need to generate half the board if n is even.
  15.  
  16. If n is odd, we compute half a board and then (half + 1 rows) of the board.
  17. Then we sum then up to get the answer.
  18.  
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <string.h>
  23.  
  24. //#include <iostream.h>
  25.  
  26. int ans[3][14] = {0}, ans_c = 0;
  27.  
  28. int board[14] = {0}, n, size;
  29.  
  30. int recur(int r){
  31.     if (r==size){ //jackpot
  32.         if (ans_c<3) memcpy(ans[ans_c],board,sizeof(int)*size);
  33.         ans_c++;
  34.         return 0;
  35.     }
  36.  
  37.     int a;
  38.     char cans[28] = {'#'};
  39.    
  40.     for (a=1;a<r;a++){
  41.         cans[board[a]] = '@';    
  42.         cans[board[a]-(r-a)] = '@';
  43.         cans[board[a]+(r-a)] = '@';
  44.     }
  45.    
  46.     for (a=1;a<=n;a++) //start checking if position is suitable
  47.         if (cans[a]!='@'){
  48.             board[r] = a;
  49.             recur(r+1);
  50.         }
  51.  
  52.     return 0;
  53. }
  54.  
  55. int main(){
  56.  
  57.     int i,a;
  58.    
  59.     FILE * in = fopen("checker.in","r");
  60.     fscanf(in,"%d",&n);
  61.     fclose(in);
  62.    
  63.     size = n + 1;
  64.    
  65.     int ans_temp,limit;
  66.    
  67.     if (n==6) limit = n;
  68.     else limit = (n+1)/2;
  69.    
  70.     for (i=1;i<=limit;i++){
  71.         ans_temp = ans_c;
  72.        
  73.         board[1] = i;
  74.         recur(2);
  75.     }
  76.    
  77.     if (n%2==0 && n>6) ans_c *= 2;
  78.     else if (n%2==1 && n>6) ans_c = ans_c + ans_temp;
  79.  
  80.     FILE *out = fopen ("checker.out", "w");
  81.    
  82.     for (i=0;i<3;i++){
  83.         for (a=1;a<n;a++)
  84.             fprintf(out,"%d ",ans[i][a]);        
  85.         fprintf(out,"%d\n",ans[i][n]); //solve the spacing prob
  86.     }
  87.     fprintf(out,"%d\n",ans_c);
  88.     printf("%d\n",ans_c);
  89.     fclose(out);
  90.    
  91.     return 0;  
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top