/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P01_DOPI {
  private int n;
  private int k;
  private BitSet w[];
  private int a[][];
  private int p[];
  private BitSet b;

  /////////////////////////////////////////////////////
  P01_DOPI(int n, int k) {
    this.n = n;
    this.k = k;
    // generate words
    Random random = new Random();
    this.w = new BitSet[n];
    for (int i = 0; i < n; i++) {
      BitSet wAux = new BitSet(k);
      for (int j = 0; j < k; j++) {
        wAux.set(j, random.nextBoolean());
      }
      w[i] = wAux;
    }
    // construct matrix
    this.a = new int[n][n];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        a[i][j] = hammingDist(w[i], w[j], k);
      }

    // initialize the permutation and bitstring
    this.p = new int[n];
    this.b = new BitSet(n);
    for(int i=0; i<n; i++){
      p[i]=i;
      b.set(i, false);
    }
  }

  /////////////////////////////////////////////////////
  private static int hammingDist(BitSet w1, BitSet w2, int size) {
    int t = 0;
    for (int i = 0; i < size; i++)
      if (w1.get(i) != w2.get(i))
        t++;
    return t;
  }

  /////////////////////////////////////////////////////
  private void shufflePermutation() {
    for (int idx = p.length - 1; idx > 0; idx--) {
      // Take a random index between 0 and idx.
      int randLoc = (int) (Math.random() * (idx + 1));
      int temp = p[randLoc];
      p[randLoc] = p[idx];
      p[idx] = temp;
    }
  }

  /////////////////////////////////////////////////////
  private int getCostDOP(int perm[]) {
    int t = 0;
    for (int i = 1; i < n; i++)
      t += a[perm[i - 1]][perm[i]];
    return t;
  }

  /////////////////////////////////////////////////////
  int getRandomCostDOP() {
    for (int i = 0; i < n; i++)
      p[i] = i;
    this.shufflePermutation();
    return getCostDOP(p);
  }

  /////////////////////////////////////////////////////
  private int getCostDOPI(int perm[], BitSet bs) {
    if (this.n <= 1)
      return 0;
    int t = 0;
    for (int i = 1; i < n; i++)
      t += (bs.get(i) == bs.get(i - 1)) ? 
           a[perm[i - 1]][perm[i]] : 
           k - a[perm[i - 1]][perm[i]];
    return t;
  }

  /////////////////////////////////////////////////////
  int getRandomCostDOPI() {
    this.b.clear();
    Random rand = new Random();
    for (int i = 0; i < n; i++) {
      p[i] = i;
      this.b.set(i, rand.nextBoolean());
    }
    this.shufflePermutation();
    return getCostDOPI(p, b);
  }

  /////////////////////////////////////////////////////
  private static void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  /////////////////////////////////////////////////////
  private static void reverse(int arr[], int i, int j) {
    int half = (i + j - 1) / 2;
    for (int k = i; k <= half; k++) {
      swap(arr, k, i + j - k);
    }
  }

  ///////////////////////////////////////////////////////
  private static boolean nextPermutation(int[] arr) {
    int k = arr.length - 2;
    while (k >= 0 && arr[k] > arr[k + 1])
      k--;
    if (k >= 0) {
      int t = arr.length - 1;
      while (arr[t] < arr[k])
        t--;
      swap(arr, k, t);
      reverse(arr, k + 1, arr.length - 1);
      return true;
    } else {
      return false;
    }
  }

  /////////////////////////////////////////////////////
  int getExactDOP() {    
    int[] r = new int[n];
    for (int i = 0; i < n; i++){
      r[i] = i; p[i]=i; 
    }
    int t = getCostDOP(p);
    while (nextPermutation(r)) {
      int aux = getCostDOP(r);
      if (aux < t) {
        t = aux;
        System.arraycopy(r, 0, p, 0, n);
      }
    }
    return t;
  }

  /////////////////////////////////////////////////////
  private static boolean nextBitSet(BitSet bs, int numBits) {
    int clearBit = bs.nextClearBit(0);
    if (clearBit < numBits) {
      bs.set(clearBit);
      bs.clear(0, clearBit);
      return true;
    } else {
      return false;
    }
  }

  /////////////////////////////////////////////////////
  int getExactDOPI() {    
    int[] r = new int[n];
    for (int i = 0; i < n; i++){
      r[i] = i; p[i]= i; 
    }
    b.clear();
    int t = getCostDOPI(p, b);
    while (nextPermutation(r)) {
      BitSet bs2 = new BitSet(n);
      do {
        int aux = getCostDOPI(r, bs2);
        if (aux < t) {
          t = aux;
          System.arraycopy(r, 0, p, 0, n);
          b.clear();
          b.or(bs2);     
        }
      } while (nextBitSet(bs2, n));
    }
    return t;
  }

  /////////////////////////////////////////////////////
  int getGMS(boolean isDOPI) {
    int pIdx = -1;
    b.clear();
    int bIdx = -1;

    int i0 = 0, j0 = 1;
    int cost = a[i0][j0];
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++) {
        if (a[i][j] < cost) {
          i0 = i;
          j0 = j;
          cost = a[i0][j0];
        }
        if (isDOPI && k - a[i][j] < cost) {
          i0 = i;
          j0 = j;
          cost = k - a[i0][j0];
        }
      }
    p[++pIdx] = i0;
    p[++pIdx] = j0;
    if (isDOPI) {
      b.clear(++bIdx);
      b.set(++bIdx, a[i0][j0] != cost);
    }
    while (pIdx < n - 1) {
      int next = -1;
      int aux = k + 1;
      for (int i = 0; i < n; i++) {        
        boolean found = false;
        for (int tmpIdx = 0; tmpIdx <= pIdx; tmpIdx++) {
          if (p[tmpIdx] == i) {
            found = true;
            break;
          }
        }
        if (found) {
          if (a[j0][i] < aux) {
            aux = a[j0][i];
            next = i;
          }
          if (isDOPI && k - a[j0][i] < aux) {
            aux = k - a[j0][i];
            next = i;
          }
        }
      }
      p[++pIdx] = next;
      cost += aux;
      if (isDOPI) {
        boolean bLast = b.get(bIdx);
        b.set(++bIdx, !(aux == a[j0][next])^bLast);        
      }
      j0 = next;
    }
    return cost;
  }

  /////////////////////////////////////////////////////
  int getGM(boolean isDOPI) {
    b.clear();
    Deque<Integer> pAux = new ArrayDeque<Integer>();
    Deque<Boolean> bAux = null;
    bAux = new ArrayDeque<Boolean>();
    int i0 = 0, j0 = 1;
    int cost = a[i0][j0];
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++) {
        if (a[i][j] < cost) {
          i0 = i;
          j0 = j;
          cost = a[i0][j0];
        }
        if (isDOPI && k - a[i][j] < cost) {
          i0 = i;
          j0 = j;
          cost = k - a[i0][j0];
        }
      }
    pAux.addLast(i0);
    pAux.addLast(j0);
    if (isDOPI) {
      bAux = new ArrayDeque<Boolean>();
      bAux.addLast(false);
      bAux.addLast(a[i0][j0] != cost);

    }
    while (pAux.size() < n) {
      int next = -1;
      int aux = k + 1;
      for (int i = 0; i < n; i++) {
        Integer iObj = null;
        for (Integer itPAux : pAux) {
          if (itPAux.intValue() == i) {
            iObj = itPAux;
            break;
          }
        }
        if (iObj == null) {
          if (a[j0][i] < aux) {
            aux = a[j0][i];
            next = i;
          }
          if (a[i0][i] < aux) {
            aux = a[i0][i];
            next = i;
          }
          if (isDOPI && k - a[j0][i] < aux) {
            aux = k - a[j0][i];
            next = i;
          }
          if (isDOPI && k - a[i0][i] < aux) {
            aux = k - a[i0][i];
            next = i;
          }
        }
      }

      cost += aux;
      if (a[j0][next] == aux || (isDOPI && k - a[j0][next] == aux)) {
        pAux.addLast(next);
        if (isDOPI) {
          bAux.addLast(!(aux == a[j0][next])^bAux.getLast());
        }
        j0 = next;
      } else {
        pAux.addFirst(next);
        if (isDOPI) {
          bAux.addFirst(!(aux == a[i0][next])^ bAux.getFirst());
        }
        i0 = next;
      }
    }

    Iterator<Integer> pAuxIt = pAux.iterator();
    for (int i = 0; i < n; i++) {
      p[i] = pAuxIt.next();
    }
    if (isDOPI) {
      Iterator<Boolean> bAuxIt = bAux.iterator();
      for (int i = 0; i < n; i++) {
        b.set(i, bAuxIt.next());
      }
    }

    return cost;
  }

  /////////////////////////////////////////////////////
  private static void putInMultimap(TreeMap<Integer, List<int[]>> mmap,
      Integer key, int[] value) {
    List<int[]> values = mmap.get(key);
    if (values == null) {
      values = new ArrayList<int[]>();
      mmap.put(key, values);
    }
    values.add(value);
  }

  /////////////////////////////////////////////////////
  private static class TreeMultimapIterator {
    private Iterator<Map.Entry<Integer, List<int[]>>> mmapIt;
    private ListIterator<int[]> currValuesIt;
    private int[] currValue;

    Map.Entry<Integer, List<int[]>> currEntry;

    TreeMultimapIterator(TreeMap<Integer, List<int[]>> mmap) {
      this.mmapIt = mmap.entrySet().iterator();
    }

    boolean next() {
      if (this.currValuesIt != null && this.currValuesIt.hasNext()) {
        this.currValue = this.currValuesIt.next();
        return true;
      } else if (mmapIt.hasNext()) {
        this.currEntry = this.mmapIt.next();
        this.currValuesIt = this.currEntry.getValue().listIterator();
        this.currValue = this.currValuesIt.next();
        return true;
      } else {
        return false;
      }
    }

    Integer key() {
      return this.currEntry.getKey();
    }

    int[] value() {
      return this.currValue;
    }

    void remove() {
      this.currValuesIt.remove();
      if (this.currEntry.getValue().isEmpty()) {
        this.currValuesIt = null;
        this.mmapIt.remove();
      }
    }
  }

  /////////////////////////////////////////////////////
  int getLB(boolean isDOPI) {
    int cost = 0;
    TreeMap<Integer, List<int[]>> E = new TreeMap<Integer, List<int[]>>();
    for (int i = 0; i < n - 1; i++)
      for (int j = 0; j < n; j++) {
        int[] e = {i, j};
        putInMultimap(E, a[i][j], e);
        if (isDOPI)
          putInMultimap(E, k - a[i][j], new int[]{i,j});
      }
    int C[] = new int[n];
    for (int i = 0; i < C.length; i++)
      C[i] = i;
    TreeMap<Integer, List<int[]>> H = new TreeMap<Integer, List<int[]>>();
    int szH = 0;  
    while (szH < n - 1) {
      TreeMultimapIterator it = new TreeMultimapIterator(E);
      it.next();
      int uu = it.value()[0];
      int vv = it.value()[1];
      while (C[uu] == C[vv]) {
        it.next();
        uu = it.value()[0];
        vv = it.value()[1];
      }

      putInMultimap(H, it.key(), it.value());
      szH++;
      cost += it.key();
      it.remove();
      int mi = Math.min(C[uu], C[vv]);
      int ma = Math.max(C[uu], C[vv]);
      for (int i = 0; i < n; i++)
        if (C[i] == ma)
          C[i] = mi;
    }
    return cost;
  }

  /////////////////////////////////////////////////////
  public static void main(String args[]) throws IOException {
    if (args.length != 6) {
      throw new IOException(
          "Invalid number of parameters ! Required: 6; Provided: "
              + args.length);
    }
    int n1 = Integer.parseInt(args[0]);
    int n2 = Integer.parseInt(args[1]);
    int sn = Integer.parseInt(args[2]);
    int k1 = Integer.parseInt(args[3]);
    int k2 = Integer.parseInt(args[4]);
    int sk = Integer.parseInt(args[5]);
    PrintStream out = new PrintStream(new File("report.txt"));
    try {
      out.printf("%25s%35s%n", " DOP", " DOPI");
      out.printf("%5s%5s |%5s%5s%5s%5s%5s ||%5s%5s%5s%5s%5s%n", 
                 "n", "k",
                 "RAN", "EX", "GMS", "GM", "LB", 
                 "RAN", "EX", "GMS", "GM", "LB");
      
      for (int n = n1; n <= n2; n += sn) {
        for (int k = k1; k <= k2; k += sk) {
          int kk = 3;
          while(kk-->0){
          P01_DOPI dopi = new P01_DOPI(n, k);
          out.printf("%5d%5d |", n, k);
          out.printf("%5d%5d%5d%5d%5d ||", dopi.getRandomCostDOP(), 
                     dopi.getExactDOP(), dopi.getGMS(false), 
                     dopi.getGM(false), dopi.getLB(false));
          out.printf("%5d%5d%5d%5d%5d%n", dopi.getRandomCostDOPI(), 
                     dopi.getExactDOPI(), dopi.getGMS(true), 
                     dopi.getGM(true), dopi.getLB(true));
        }}
      }
    } finally {
      out.close();
    }
  }
}