#include <stdio.h>
#include <stdlib.h>

int length;
int **a;

void createArray(int h, int w){
   int i;
   a = (int**) malloc(h*sizeof(int*));
   if(a == NULL){
     fprintf(stderr, "out of memory");
     exit(1);
   }
   length = h;
   for(i = 0; i < h; i++){
     a[i] = (int*) malloc(w*sizeof(int));
     if(a[i] == NULL){
       fprintf(stderr, "out of memory");
       exit(1);
     }
   }
}

void destroyArray(){
   int i;
   for(i = 0; i < length; i++){
     free(a[i]);
   }
   free(a);
}

void copyAdd(int fi, int fj, int ti, int tj, int h, int w, int add){
   int i; int j;
   for(i = 0; i < h; i++){
     for(j = 0; j < w; j++){
       a[ti+i][tj+j] = a[fi+i][fj+j]+add;
     }
   }
}

void createPermutation(int si, int sj, int len, int add, int d){
   int i; int j;
   for(i = 0; i < len; i++){
     a[si+i][sj] = add+i;
   }
   for(j = 1; j < len; j++){
     for(i = 0; i < len; i++){
       a[si+i][sj+j] = a[si+(i+len+d)%len][sj+j-1];
     }
   }
}

int **createTable(int n){
   if(n < 1){
     fprintf(stderr, "call function createTable() negative argument n = %d", n);
     exit(1);
   }
    
   int m;
   int k;
   k = 1 << n;
   createArray(k, k-1);
    
   a[0][0] = 2;
   a[1][0] = 1;
   for(m = 1; m < n; m++){
     k = 1<<m;
     copyAdd(0, 0, k, 0, k, k-1, k);
     createPermutation(0, k-1, k, k+1, 1);
     createPermutation(k, k-1, k, 1, -1);
      
   }
    
   return a;

}

void printTable(int n){
   int i; int j; int k;
   k = 1 << n;
   for(i = 0; i < k; i++){
     for(j = 0; j < (k-1); j++){
       printf("%d ", a[i][j]);
     }
     printf("\n");
   }
}

int main(int argc, char **argv){
   int n;
   scanf("%d", &n);
   createTable(n);
   printTable(n);
   destroyArray();
   return 0;
}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int binary_search(int x, int length, int *array){
   int i, j, k;

   if(length <= 0 || x < array[0]){
    return -1;
   }
   if(length <= 1 || array[length-1] <= x){
    return length;
   }

   i = 0;
   j = length-1;
   while(i != (j-1)){
    k = (i+j)/2;
    if(array[k] <= x){
     i = k;
    }else{
     j = k;
    }
   }
   return i;
}

int *selection_sort(int length, int*array){
   int i, j, pointer;
   int tmp;
     
   for(i = 0; i < (length-1); i++){
    pointer = i;
    for(j = i+1; j < length; j++){
     if(array[pointer] > array[j]){
      pointer = j;
     }
    }
    tmp = array[i];
    array[i] = array[pointer];
    array[pointer] = tmp;
   }

   return array;
}

int *input_array(int length, int *array){
   int i;
   int elem;
   int tmp;
     
   for(i = 0; i < length; i++){
    tmp = scanf("%d", &elem);
    if(tmp <= 0 || tmp == EOF){
     fprintf(stderr, "error: can't read array's elements \n");
     return NULL;
    }
    array[i] = elem;
   }
   return array;
}

int n;
int *a;
int num;
int haveNumValue;

void print_help(void){
   printf("Usage: PROGRAMM_NAME [-k ELEMENT] -l ARRAY_SIZE \n");
   printf("Then input array's elements (integer numbers). \n");
   printf("Programm find ELEMENT index in array. \n");
   printf("You can also input ELEMENT after inputing the array's elements. \n");
   printf("\n Attention! Programm work with sorted arrays (like [1, 2, 5, 8, 8, 34]). You can input non-sorted array and programm sort it before start element searching. \n");
   printf("Specification: R = ((i = −1 ∧ x < b[0]) ∨ (0 <= i < n − 1 ∧ b[i] x < b[i + 1]) ∨ (i = n ∧ b[n − 1] x)) \n");
   exit(0);
}

void try_input_num(void){
   int status;
   status = scanf("%d", &num);
   haveNumValue = !(status <= 0 || status == EOF);
}

void process_keys(int argc, char **argv){
   int i;
   for(i = 0; i < argc; i++){
    if(strcmp(argv[i], "-k") == 0 && i < (argc-1)){
     printf("-k");
     num = atoi(argv[i+1]);
     haveNumValue = 1;
    } else if(strcmp(argv[i], "-l") == 0 && i < (argc-1)){
     n = atoi(argv[i+1]);
    } else if(strcmp(argv[i], "--help") == 0){
     print_help();
    }
   }
}

int main(int argc, char **argv){
   n = 0; num = 0; haveNumValue = 0;

   process_keys(argc, argv);
     
   a = (int*)malloc(n*sizeof(int));

   a = input_array(n, a);
   a = selection_sort(n, a);

   if(!haveNumValue){
    try_input_num();
   }
   while(haveNumValue){
    printf("element %d have index %d in the array \n", num, binary_search(num, n, a));
    try_input_num();
   }

   free(a);
   return 0;
}