// oeis.org/A056971
// Lab 4 Spring 2018, count minHeaps
// Maintains array of open heap positions that have all ancestors with priorities

#include <stdlib.h>
#include <stdio.h>
// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

double CPUtime()
{
struct rusage rusage;

getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
       + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

int increment;

int n,heap[18],count=0;
char avail[17]; // array of open heap positions that have all ancestors recorded

void trace(char *s,int k,int availCount) {
  int i;

  return;

  for (i=0;i<k;i++)
    printf(".");
  printf("%s backtrack(%d,[",s,k);
  for (i=0;i<availCount-1;i++)
    printf("%d,",avail[i]);
  if (availCount>0)
    printf("%d",avail[availCount-1]);
  printf("])\n");
  }

void backtrack(int k,int availCount) {
  int i;
  char indexSave,indexSave2;

  trace("Enter",k,availCount);

  if (k==n) {
    // availCount must be 1
    count++;
    if (increment>0 && count%increment==0) {
      heap[avail[0]]=n;
      printf("%d: ",count);
      for (i=1;i<=n;i++)
        printf("%d ",heap[i]);
      printf("\n");
      }
    trace("Exit",k,availCount);
    return;
    }

  // Save k at each available slot in turn and make any
  // descendants available.
  for (i=0;i<availCount;i++) {
    indexSave=avail[i]; // For backtracking
    heap[indexSave]=k;
    if (2*indexSave>n) { // Already at leaf of heap
      avail[i]=avail[availCount-1]; // Replace with last entry's index
      backtrack(k+1,availCount-1);
      }
    else if (2*indexSave==n) { // Will only have a left child
      avail[i]=2*indexSave; // Replace with left child's index
      backtrack(k+1,availCount);
      }
    else { // Have both left and right child
      avail[i]=2*indexSave; // Replace with left child's index
      indexSave2=avail[availCount]; // For backtracking
      avail[availCount]=2*indexSave+1; // Extend array with right child's index
      backtrack(k+1,availCount+1);
      avail[availCount]=indexSave2; // Backtrack
      }
    avail[i]=indexSave; // Backtrack
    }

  trace("Exit",k,availCount);
  }

int main() {
  double startCPU,stopCPU;
  int i;

  scanf("%d %d",&n,&increment);
  if (n<0 || n>17)
    exit(0);
  if (increment<0)
    exit(0);
  startCPU=CPUtime();
  avail[0]=1; // Root of heap will take the lowest priority
  backtrack(1,1);
  stopCPU=CPUtime();
  printf("%d heaps for n=%d, CPU=%5.2f\n",count,n,stopCPU-startCPU);
  }