# C, 16.344 (4 minutes 33 seconds)
### Best moves found so far: D6,D13,R19,D9,D11,R21,D10,R20

Uses a mixture of Monte Carlo and hill climbing. Could be made to run much faster, I'm sure.

    #include <stdio.h>
    #include <stdlib.h>
    
    /*
    
    Best result so far: 16.344
    D6,D13,R19,D9,D11,R21,D10,R20
    
    real    4m33.027s
    user    4m12.787s
    sys 0m1.334s
    
    */
    
    #define GRID_WIDTH   40
    #define GRID_HEIGHT  20
    #define GRID_SIZE    (GRID_WIDTH * GRID_HEIGHT)
    #define NUM_FOLDS    8
    #define MAX_VALUE    (1 << NUM_FOLDS)
    #define TARGET_VALUE (MAX_VALUE / 2)
    
    double score_grid(short *g) {
      int i, sum;
      for (i=sum=0; i<GRID_SIZE; i++) sum += abs(*g++ - TARGET_VALUE);
      return sum * 1.0 / MAX_VALUE;
    }
    
    void h_fold(short *g, int fold_row) {
      int x, y0, y1;
      if (fold_row<1 || fold_row>=GRID_HEIGHT) return;
      y1 = fold_row * GRID_WIDTH;
      y0 = y1 - GRID_WIDTH;
      while (y0>=0 && y1<GRID_SIZE) {
        for (x=0; x<GRID_WIDTH; x++) {
          g[y0+x] = g[y1+x] = (g[y0+x] + g[y1+x]) >> 1;
        }
        y0 -= GRID_WIDTH;
        y1 += GRID_WIDTH;
      }
    }
    
    void v_fold(short *g, int fold_col) {
      int y, x0, x1;
      if (fold_col<1 || fold_col>=GRID_WIDTH) return;
      x1 = fold_col;
      x0 = x1 - 1;
      while (x0>=0 && x1<GRID_WIDTH) {
        for (y=0; y<GRID_SIZE; y+=GRID_WIDTH) {
          g[y+x0] = g[y+x1] = (g[y+x0] + g[y+x1]) >> 1;
        }
        x0--;
        x1++;
      }
    }
    
    void print_grid(short *g) {
      int i=0, checksum=0;
      while (i<GRID_SIZE) {
        checksum += *g;
        printf("%3X",*g++);
        if ((++i) % GRID_WIDTH == 0) putchar('\n');
      }
      if (checksum != GRID_SIZE * TARGET_VALUE) printf("Bad total: %d\n",checksum);
    }
    
    void init_grid(short *g) {
      int i;
      static short *start_grid=0, *sg;
      if (!start_grid) {
        char *src = "11010110100011100000001000110001001101010111000100100100000101100000101111000010"
                    "10110011111011111101101011111001000010101010110111000101000001011111101000011001"
                    "10000111111001111011100101101001101100001110001101001011010011011110101000011100"
                    "00110010100010100010110101001100110001100100111010000110100110001000110000111101"
                    "01000001110000101000110101011011101010111110101010110000001011010010000011101000"
                    "11111011111100100100100010111010111111000101011110000100111111111000110101101101"
                    "00110100010111101111000011011010000110001001101010010101110010110111101001011111"
                    "10110001101100001110010100110100010011011110100110000100100111101101000010011001"
                    "00011100110100111101000000001000010100001101001011000101101001000100111100011010"
                    "00010110001110011111100011101111011100111001110011111011010010000100101111101001";
        start_grid = malloc(GRID_SIZE * sizeof(short));
        for (i=0; i<GRID_SIZE; i++) start_grid[i] = (src[i]&1)<<NUM_FOLDS;
      }
      sg = start_grid;
      for (i=0; i<GRID_SIZE; i++) *g++ = *sg++;
    }
    
    double evaluate(int *moves) {
      short *grid;
      double score;
      int i, f;
      grid = malloc(GRID_SIZE * sizeof(short));
      init_grid(grid);
      for (i=0; i<NUM_FOLDS; i++) {
        f = moves[i];
        if (f>0) v_fold(grid,f);
        else h_fold(grid,-f);
      }
      score = score_grid(grid);
      free(grid);
      return score;
    }
    
    
    double optimize_folding(int *moves, double score) {
      int opt_cycle, i, which_fold, new_move, f1, f2, t;
      double s;
      
      for (opt_cycle=0; opt_cycle<1000; opt_cycle++) {
        for (i=0; i<NUM_FOLDS; i++) {
          which_fold = random() % NUM_FOLDS;
          do {
            if (random()&1) new_move = random() % (GRID_WIDTH-1) + 1;
            else new_move = -(random() % (GRID_HEIGHT-1) + 1);
          } while (moves[which_fold]==new_move);
          t = moves[which_fold];
          moves[which_fold] = new_move;
          s = evaluate(moves);
          if (s>score) moves[which_fold] = t;
          else score = s;
        }
        for (i=0; i<NUM_FOLDS; i++) {
          f1 = random() % NUM_FOLDS;
          do {
            f2 = random() % NUM_FOLDS;
          } while (f2==f1);
          t = moves[f1];
          moves[f1] = moves[f2];
          moves[f2] = t;
          s = evaluate(moves);
          if (s>score) {
            t = moves[f1];
            moves[f1] = moves[f2];
            moves[f2] = t;
          }
          else score = s;
        }
      }
      
      return score;
    }
    
    void show_moves(int *moves) {
      int i, m;
      for (i=0; i<NUM_FOLDS; i++) {
        m = moves[i];
        printf("%c%d%c",(m>0)?'R':'D',abs(m),((i+1)%NUM_FOLDS)?',':'\n');
      }
    }
    
    int main() {
      int i, j, moves[NUM_FOLDS], save_moves[NUM_FOLDS];
      double score, best_score = 1.0E+99;
      
      srandomdev();
      for (i=0; i<400; i++) {
        for (j=0; j<NUM_FOLDS; j++) {
                if (random()&1) moves[j] = random() % (GRID_WIDTH-1) + 1;
                else moves[j] = -(random() % (GRID_HEIGHT-1) + 1);
            }
            score = optimize_folding(moves, 1.0E+99);
            if (score<best_score) {
                best_score = score;
                for (j=0; j<NUM_FOLDS; j++) save_moves[j]=moves[j];
            }
        }
      printf("%.3lf\n",best_score);
      show_moves(save_moves);
      return 0;
    }