hacker rank Test Solutions-26

               hacker rank  Test Solutions-26

LINK: https://www.hackerrank.com/contests/ece-coding-test-26



1)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
typedef long long LLG;

#ifndef DEBUG
static char* debug;
#endif

int LLGqsort( const void* lArg, const void* rArg ) {
LLG* lhs = (LLG*) lArg;
LLG* rhs = (LLG*) rArg;
# ifndef DEBUG
  if (debug) fprintf(stderr,".");
# endif
  return *lhs<*rhs ? -1 : (*lhs>*rhs ? 1 : 0);
}

LLG LLGGCD( LLG a, LLG b) {
  if (!b) return a;
  return LLGGCD( b, a%b );
}

int main() {
LLG N, K, Ksave, Fs[100][2], f, df;
LLG U;
int nFs = 0;
int iFs;
int iUs;
int dumy;
LLG n;
LLG nDivs;
LLG *pDiv0, *pDivEnd, *pDiv;
LLG step;
LLG gcd;

# ifndef DEBUG
  debug = getenv( "DEBUG" );
# endif

  dumy = fscanf( stdin, "%Ld", &N);
  dumy = fscanf( stdin, "%Ld", &K);

  Ksave = K;

  memset( Fs, 0, sizeof Fs );

  if ( K==1LL ) {
    fprintf( stdout, "0\n" );
    return 0;
  }

  if ( !(K&1LL) ) {
    while (!(K&1LL) ) {
      K >>= 1LL;
      ++Fs[nFs][1];
    }
    Fs[nFs++][0] = 2LL;
  }

  if ( !(K%3) ) {
    while (!(K%3LL)) {
      K /= 3LL;
      ++Fs[nFs][1];
    }
    Fs[nFs++][0] = 3;
  }

  f = 5;
  df = 2;
  while ( (f*f) <= K) {
    if ( !(K%f) ) {
      Fs[nFs][1] = 1;
      K /= f;
      while ( !(K%f) ) {
        Fs[nFs][1] += 1;
        K /= f;
      }
      Fs[nFs++][0] = f;
    }
    f += df;
    df ^= 6;
  }

  if ( K>1 ) {
    Fs[nFs][0] = K;
    Fs[nFs++][1] = 1;
  }

  if ( !nFs ) {
    fprintf( stdout, "0\n" );
    return 0;
  }

  nDivs = 1LL;
# ifndef DEBUG
  for (iFs=0; iFs<nFs; ++iFs) {
    if (debug) fprintf( stderr, "%Ld %Ld\n", Fs[iFs][0], Fs[iFs][1] );
    nDivs *= (Fs[iFs][1]+1LL);
  }
# endif
  pDiv0 = (LLG*) malloc( nDivs * sizeof(LLG) );
  pDivEnd = pDiv0 + nDivs;

  step = 1;
  for (iFs=0; iFs<nFs; ++iFs) {
  int i,j;
  LLG f;
  LLG fCt;
    pDiv = pDiv0;
    f = Fs[iFs][0];
    fCt = Fs[iFs][1];
    while ( pDiv < pDivEnd ) {
      if (!iFs) *pDiv = 1LL;
      pDiv += step;
      for (i=0; i<fCt; ++i ) {
        for ( j=0; j<step; ++j, ++pDiv ) {
          *pDiv = pDiv[-step] * f;
        }
      }
    }
    step *= (fCt+1LL);
  }

  ++pDiv0;

# ifndef DEBUG
  if (debug) {
    for (pDiv=pDiv0; pDiv<pDivEnd; ++pDiv) fprintf( stderr, " %Ld", *pDiv);
    fprintf( stderr, "; %Ld=nDivs\n", nDivs);
  }
# endif

  qsort( pDiv0, nDivs-1, sizeof(LLG), LLGqsort);

# ifndef DEBUG
  if (debug) {
    fprintf( stderr, "\n");
    for (pDiv=pDiv0; pDiv<pDivEnd; ++pDiv) fprintf( stderr, " %Ld", *pDiv);
    fprintf( stderr, "\n");
  }
# endif

  for (iUs=0LL; iUs<N; ++iUs) {
    dumy = fscanf( stdin, "%Ld", &U);
    gcd = LLGGCD( U, Ksave);
    if (gcd==Ksave) {
      fprintf( stdout, "0\n" );
      return 0;
    }
    for (pDiv=pDiv0; pDiv<pDivEnd; ++pDiv) {
      if (! *pDiv) continue;
      if ( *pDiv > gcd ) break;
      if ( !(U%*pDiv) ) {
        *pDiv = 0LL;
        if (pDiv==pDiv0) {
          while (!*pDiv0 && pDiv0<pDivEnd) pDiv = ++pDiv0;
          pDiv = pDiv0 - 1;
        }
      }
    }
  }

# ifndef DEBUG
  if (debug) {
    for (pDiv=pDiv0; pDiv<pDivEnd; ++pDiv) fprintf( stderr, " %Ld", *pDiv);
    fprintf( stderr, "\n");
  }
# endif

  n = 0LL;
  for (pDiv=pDiv0; pDiv<pDivEnd; ++pDiv) if (*pDiv) ++n;

  fprintf( stdout, "%Ld\n", n);
  return 0;
}

2) 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define LIM 32100
#define NUM 123456
typedef struct _node{
  int x;
  int id;
  struct _node *next;
} node;
typedef struct _list_node{
  int x;
  struct _list_node *next;
} list_node;
typedef struct _list{
  int size;
  list_node *head;
} list;
node **hash;
int *p,hash_size=0,*A,*B,*ALength,**AD,*BLength,**BD,*MA,*MB,*VA,*VB;
int match(int u,int vi);
void getp(long long N,int *prim);
int findid(int x,int iflag);
void freehash();
void insert(list *l,int x);
void freelist(list *l);

int main(){
  p=(int*)malloc(LIM*sizeof(int));
  hash=(node**)malloc(NUM*sizeof(node*));
  memset(hash,0,NUM*sizeof(node*));
  getp(LIM,p);
  int i,j,ans=0,n,t;
  scanf("%d",&n);
  A=(int*)malloc(n*sizeof(int));
  B=(int*)malloc(n*sizeof(int));
  int *Alist=(int*)malloc(13*sizeof(int));
  ALength=(int*)malloc(n*sizeof(int));
  AD=(int**)malloc(n*sizeof(int*));
  list_node *temp;
  for(i=0;i<n;i++)
    scanf("%d",A+i);
  for(i=0;i<n;i++)
    scanf("%d",B+i);
  for(i=0;i<n;i++){
    Alist[0]=0;
    for(j=0;p[j]*p[j]<=A[i];j++)
      if(A[i]%p[j]==0){
        Alist[++Alist[0]]=findid(p[j],1);
        while(A[i]%p[j]==0)
          A[i]/=p[j];
      }
    if(A[i]!=1)
      Alist[++Alist[0]]=findid(A[i],1);
    ALength[i]=Alist[0];
    AD[i]=(int*)malloc(Alist[0]*sizeof(int));
    for(j=0;j<Alist[0];j++)
      AD[i][j]=Alist[Alist[0]-j];
  }
  free(A);
  free(Alist);
  list *Blist=(list*)malloc(hash_size*sizeof(list));
  BLength=(int*)malloc(hash_size*sizeof(int));
  BD=(int**)malloc(hash_size*sizeof(int*));
  memset(Blist,0,hash_size*sizeof(list));
  for(i=0;i<n;i++){
    for(j=0;p[j]*p[j]<=B[i];j++)
      if(B[i]%p[j]==0){
        t=findid(p[j],0);
        if(t!=-1)
          insert(Blist+t,i);
        while(B[i]%p[j]==0)
          B[i]/=p[j];
      }
    if(B[i]!=1){
      t=findid(B[i],0);
      if(t!=-1)
        insert(Blist+t,i);
    }
  }





  for(i=0;i<hash_size;i++){
    BD[i]=(int*)malloc(Blist[i].size*sizeof(int));
    BLength[i]=Blist[i].size;
    j=Blist[i].size-1;
    temp=Blist[i].head;
    while(temp){
      BD[i][j]=temp->x;
      temp=temp->next;
      j--;
    }
    freelist(Blist+i);
  }
  free(B);
  free(Blist);
  free(p);
  freehash();
  MA=(int*)malloc(n*sizeof(int));
  MB=(int*)malloc(n*sizeof(int));
  VA=(int*)malloc(n*sizeof(int));
  VB=(int*)malloc(hash_size*sizeof(int));
  memset(MA,-1,n*sizeof(int));
  memset(MB,-1,n*sizeof(int));
  memset(VA,-1,n*sizeof(int));
  memset(VB,-1,hash_size*sizeof(int));
  for(i=0;i<n;i++)
    if(match(i,i))
      ans++;
  printf("%d",ans);
  return 0;
}
int match(int u,int vi){
  int i,j,v;
  if(VA[u]==vi)
    return 0;
  VA[u]=vi;
  int *FA=AD[u];
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MB[v]==-1){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    VB[FA[i]]=vi;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MA[u]!=v && match(MB[v],vi)){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  return 0;
}
void getp(long long N,int *prim){
  long long i,j,index=2,flag;
  prim[0]=2;
  prim[1]=3;
  for(i=5;i<=N;i=i+2)
    {
      for(j=1,flag=1;prim[j]<=sqrt(i);j++)
        {
          if(i%prim[j]==0){
            flag=0;
            break;}
        }
      if(flag==1)
        {prim[index]=i;
          index++;}
    }
  prim[index]=0;
  return;
}
int findid(int x,int iflag){
  int b=x%NUM;
  node *t=hash[b];
  while(t){
    if(t->x==x)
      return t->id;
    t=t->next;
  }
  if(iflag){
    t=(node*)malloc(sizeof(node));
    t->x=x;
    t->id=hash_size++;
    t->next=hash[b];
    hash[b]=t;
    return t->id;
  }
  return -1;
}
void freehash(){
  int i;
  node *t,*p;
  for(i=0;i<NUM;i++){
    t=hash[i];
    while(t){
      p=t->next;
      free(t);
      t=p;
    }
  }
  free(hash);
  return;
}
void insert(list *l,int x){
  list_node *t=(list_node*)malloc(sizeof(list_node));
  t->x=x;
  t->next=l->head;
  l->head=t;
  l->size++;
  return;
}
void freelist(list *l){
  list_node *t,*p;
  t=l->head;
  while(t){
    p=t->next;
    free(t);
    t=p;
  }
  return;
}







3)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct State State;

typedef struct {
    State **data;
    int count;
    int capacity;
} List;

List *list_create(int capacity) {
    List *list = (List *)malloc(sizeof(List));
    list->capacity = (capacity > 0) ? capacity : 8;
    list->count = 0;    
    list->data = (State **)malloc(list->capacity*sizeof(State *));
    assert(list->data);
    return list;
}

void list_destroy(List *list) {
    if (list && list->data) {
        for (int i = 0; i < list->count; i++) free(list->data[i]);
        free(list->data);
    }
    free(list);
}
        
void list_append(List *list, State *item) {
    if (list->count >= list->capacity) {
        list->capacity = 1.5*list->capacity + 1;
        list->data = (State **)realloc(list->data, list->capacity*sizeof(State *));
        assert(list->data);
    }
    list->data[list->count++] = item;
}

/**********************************************************************/

#define TURN_WHITE 0
#define TURN_BLACK 1

#define PIECE_NONE 0

#define COLOR_MASK   0xf0

#define PIECE_MASK   0x0f
#define QUEEN  0x01
#define ROOK   0x02
#define BISHOP 0x03
#define KNIGHT 0x04

#define COLOR_WHITE  0x10
#define WHITE_QUEEN  0x11
#define WHITE_ROOK   0x12
#define WHITE_BISHOP 0x13
#define WHITE_KNIGHT 0x14

#define COLOR_BLACK  0x20
#define BLACK_QUEEN  0x21
#define BLACK_ROOK   0x22
#define BLACK_BISHOP 0x23
#define BLACK_KNIGHT 0x24

struct State {
    char turn;
    unsigned char board[4][4];
};

State *state_new(void) {
    State *s = (State *)malloc(sizeof(State));
    s->turn = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            s->board[i][j] = PIECE_NONE;
        }
    }
    return s;
}

State *state_copy(State *orig) {
    State *copy = (State *)malloc(sizeof(State));
    copy->turn = orig->turn;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            copy->board[i][j] = orig->board[i][j];
        }
    }
    return copy;
}

State *move_piece(State *orig, int i0, int j0, int i1, int j1) {
    State *copy = state_copy(orig);
    copy->turn++;
    copy->board[i1][j1] = copy->board[i0][j0];
    copy->board[i0][j0] = 0;
    return copy;
}

// Returns 1 if winning state for white (meaning black queen has been captured).
// Returns -1 if winning state for black (meaning white queen has been captured).
// Returns 0 for any other state.
int state_utility(State *s) {
    int whiteQueen = 0, blackQueen = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (s->board[i][j] == WHITE_QUEEN) {
                whiteQueen = 1;
                if (blackQueen) return 0;
            } else if (s->board[i][j] == BLACK_QUEEN) {
                blackQueen = 1;
                if (whiteQueen) return 0;
            }
        }
    }
    if (whiteQueen && !blackQueen) return 1;
    if (!whiteQueen && blackQueen) return -1;
    return 0;
}





void state_print(State *s) {
    if (s->turn % 2 == 0) printf("---white's turn (%d)---\n", s->turn);
    else printf("---black's turn (%d)---\n", s->turn);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            unsigned char piece = s->board[i][j];
            if (!piece) printf(". ");
            else if (piece == WHITE_QUEEN) printf("Q ");
            else if (piece == WHITE_ROOK) printf("R ");
            else if (piece == WHITE_BISHOP) printf("B ");
            else if (piece == WHITE_KNIGHT) printf("N ");
            else if (piece == BLACK_QUEEN) printf("q ");
            else if (piece == BLACK_ROOK) printf("r ");
            else if (piece == BLACK_BISHOP) printf("b ");
            else if (piece == BLACK_KNIGHT) printf("n ");
            else printf("? ");
        }
        printf("\n");
    }
}

List *get_successors(State *s) {
    int color = (s->turn % 2 == 0) ? COLOR_WHITE : COLOR_BLACK;
    List *list = list_create(37);
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            unsigned char piece = s->board[i][j];
            if ((piece & COLOR_MASK) != color) continue;
            if ((piece & PIECE_MASK) == QUEEN) {
                for (int ii = i-1; ii >= 0; ii--) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1; ii < 4; ii++) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);                    
                    if (prev) break;                    
                }
                for (int jj = j-1; jj >= 0; jj--) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int jj = j+1; jj < 4; jj++) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }                
            } else if ((piece & PIECE_MASK) == ROOK) {
                for (int ii = i-1; ii >= 0; ii--) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1; ii < 4; ii++) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);                    
                    if (prev) break;                    
                }
                for (int jj = j-1; jj >= 0; jj--) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int jj = j+1; jj < 4; jj++) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
            } else if ((piece & PIECE_MASK) == BISHOP) {
                for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
            } else if ((piece & PIECE_MASK) == KNIGHT) {
                int moves[8][2] = {{-2,-1}, {-2,1}, {2,-1}, {2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}};
                for (int k = 0; k < 8; k++) {
                    int ii = i + moves[k][0], jj = j + moves[k][1];
                    if (ii < 0 || ii >= 4 || jj < 0 || jj >= 4) continue; // stay within board
                    if ((s->board[ii][jj] & COLOR_MASK) == color) continue; // can't capture own pieces
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                }
            }
        }
    }

    return list;
}

int minimax_value(State *s, int maxPly) {
    int u = state_utility(s);
    if (u != 0 || s->turn >= maxPly) return u;
    if (s->turn % 2 == 0) { // white's turn to move
        int maxValue = -100;
        List *list = get_successors(s);
        for (int i = 0; i < list->count; i++) {
            int v = minimax_value(list->data[i], maxPly);
            if (v > maxValue) {
                maxValue = v;
                if (maxValue == 1) break; // can't do any better.
            }
        }
        list_destroy(list);
        return maxValue;
    } else { // black's turn to move
        int minValue = 100;
        List *list = get_successors(s);
        for (int i = 0; i < list->count; i++) {
            int v = minimax_value(list->data[i], maxPly);
            if (v < minValue) {
                minValue = v;
                if (minValue == -1) break; // can't do any better
            }
        }
        list_destroy(list);
        return minValue;
    }
}

int main(void) {
    int g, w, b, m;
    scanf("%d", &g);
    while (g--) {
        scanf("%d %d %d", &w, &b, &m);
        State *s = state_new();
        for (int i = 0; i < w; i++) {
            char t, c, r;
            scanf(" %c %c %c", &t, &c, &r);
            int i = r-'1', j = c-'A';
            if (t == 'Q') s->board[i][j] = WHITE_QUEEN;
            else if (t == 'R') s->board[i][j] = WHITE_ROOK;
            else if (t == 'B') s->board[i][j] = WHITE_BISHOP;
            else if (t == 'N') s->board[i][j] = WHITE_KNIGHT;
            else assert(0);
        }
        for (int i = 0; i < b; i++) {
            char t, c, r;
            scanf(" %c %c %c", &t, &c, &r);
            int i = r-'1', j = c-'A';
            if (t == 'Q') s->board[i][j] = BLACK_QUEEN;
            else if (t == 'R') s->board[i][j] = BLACK_ROOK;
            else if (t == 'B') s->board[i][j] = BLACK_BISHOP;
            else if (t == 'N') s->board[i][j] = BLACK_KNIGHT;
            else assert(0);
        }
        if (m % 2 == 0) m--;
        if (minimax_value(s, m) == 1) printf("YES\n");
        else printf("NO\n");
        free(s);
    }

    return 0;
}