// (C)2017 Matteo Lucarelli - matteolucarelli.altervista.org

// Complete solutions for Codility lessons in C language
// All 100% results
// https://codility.com/programmers/lessons/

// Equi, demo task: equilibrium index
// find the first i of A as sum(A[0]..A[i-1]) == sum(A[i+1]..A[N-1])
int solution(int A[], int N) {
    
    if (N==0) return -1;
    
    int i=0;
    long long lsum=0;
    long long rsum=0;
    
    for (i=1;i<N;i++) rsum+=A[i];
    
    if (rsum==0) return 0;
    
    for (i=1;i<N;i++){
        rsum -= A[i];
        lsum += A[i-1];
        if (lsum==rsum) return i;
    }
    return -1;
}

// LESSON 1 ////////////////////////////////////////////////////////////////////

// 1-Iterations : BinaryGap 
// find longest zeroes sequence between ones
int solution(int N) {
    
    int pos;
    int max=0;
    int curr=-1;
    
    for(pos=0;pos<sizeof(int)*8;pos++){
        
        if ( ( N & ( 1 << pos ) ) != 0 ){
            if (curr>max) max=curr;
            curr=0;
        }else{
            if (curr!=-1) curr++;   
        }
    }
    
    return max;
}

// LESSON 2 ////////////////////////////////////////////////////////////////////

// 2-Array : CyclicRotation 
// rotate A right K times
struct Results solution(int A[], int N, int K) {
    
    struct Results result;
    result.A = A;
    result.N = N;
    
    if ((N<2)||(K==0)||(A==0)) return result;

    int i;
    int temp;
    for(;K>0;K--){
        temp=A[N-1];
        for(i=N-1;i>0;i--){
            A[i]=A[i-1];
        }
        A[0]=temp;
    }
    
    return result;
}

// 2-Array: OddOccurrencesInArray
// find the element that cannot be paired with another that has the same value
int solution(int A[], int N) {
    
    int i=0;
    int result=0;
    for (i=0;i<N;i++) result ^= A[i];
    return result;
}

// LESSON 3 ////////////////////////////////////////////////////////////////////

// 3-Time Complexity: FrogJmp
// minimal steps D to reach or trespass Y from X 
int solution(int X, int Y, int D) {
    
    if ((Y-X)%D==0) return ((Y-X)/D);
    return ((Y-X)/D)+1;
}

// 3-Time Complexity: PermMissingElem 
// find the missing element in A[N]=1:N+1
int solution(int A[], int N) {
    
    if (N==0) return 1;
    
    int f[N+1];
    int i=0;
    
    for (i=0;i<N+1;i++){
        f[i]=0;   
    }
    
    for (i=0;i<N;i++){
        f[A[i]-1]=1;
    }
    
    for (i=0;i<N+1;i++){
        if (f[i]==0) return (i+1);
    }
    
    return N+1;
}

// 3-Time Complexity: TapeEquilibrium
// find the position p of minimum sum(a[0]
int solution(int A[], int N) {
    
    int right=0;
    int i;
    
    for (i=1;i<N;i++){
        right += A[i];   
    }
    
    int left=A[0];
    int min=abs(left-right);
    
    for (i=1;i<N-1;i++){
        
        left += A[i];
        right -= A[i];
        
        if (abs(left-right)<min){
            min=abs(left-right);
        }
    }
    return min;
}

// LESSON 4 ////////////////////////////////////////////////////////////////////

// 4-Counting Elements: MissingInteger
// return the minimal positive integer not present in A
// time:O(N), space:O(N)
int solution(int A[], int N) {
    
    int f[N];
    int i=0;
    
    for (i=0;i<N;i++){
        f[i]=0;   
    }    
    
    for (i=0;i<N;i++){
        if (((A[i]-1)<N)&&(A[i]-1>=0)) f[A[i]-1]=1;   
    }
    
    for (i=0;i<N;i++){
        if (f[i]==0) return i+1;   
    }
    
    return N+1;
}

// 4-Counting Elements: PermCheck
// return 0 if A[N] does not contains all 1:N
int solution(int A[], int N) {
    
    int i;
    int count[N];
    for(i=0;i<N;i++) count[i]=0;
    
    for(i=0;i<N;i++){
        if (A[i]>N) return 0;
        if (count[A[i]-1]>0) return 0;
        count[A[i]-1]++; 
    }
    
    for(i=0;i<N;i++){
        if (count[i]==0) return 0;
    }
    return 1;
}

// 4-Counting Elements: FrogRiverOne
// find index of A for which in A[0] to A[i] there's a complete sequence 1:X
int solution(int X, int A[], int N) {
    
    int i;
    int count[X];
    for(i=0;i<X;i++) count[i]=0;
    int full=0;
    
    for(i=0;i<N;i++){
        if (count[A[i]-1]==0){
            count[A[i]-1]=1;
            full++;
            if (full==X) return i;
        }
    }
    return -1;
}

// 4-Counting Elements: MaxCounters
// Return N counters value where A[N]<=N increase counter A[N] 
// and A[N]==N+1 set alla counters to current max
// time:O(N+M) space:O(N)
#include <strings.h>
struct Results solution(int N, int A[], int M) 
{    
    struct Results result;
    result.C = (int*)malloc(sizeof(int)*N);
    bzero(result.C,sizeof(int)*N);
    result.L = N;
    
    int i;
    int max=0;
    
    // use to apply later the max operation
    int lastappliedmax=0;
    
    for(i=0;i<M;i++) {
        
        if (A[i]<=N) {
            
            if (result.C[A[i]-1]<=lastappliedmax) {
            	// not yet applied last max operation
                result.C[A[i]-1] = lastappliedmax+1;
            }else{
            	// yet applied last max operation
                result.C[A[i]-1]++;
            }
            
            // current max
            if (result.C[A[i]-1]>max) {
                max=result.C[A[i]-1];
            }
        }else{
        	// save max to be applied later
            lastappliedmax=max;
        }
    }    
    
    for(i=0;i<N;i++){
        if (result.C[i]<lastappliedmax) result.C[i]=lastappliedmax;
    }
    
    return result;
} 

// LESSON 5 ////////////////////////////////////////////////////////////////////

// 5-Prefix Sums: PassingCars
// count pairs A[x],A[y] where x<y and A[x]==0 && A[y]==1
int solution(int A[], int N) {
    
    int i;
    int zeroes=0;
    int count=0;
    
    for (i=0;i<N;i++){
        if (A[i]==0) zeroes++;
        else if (count+zeroes<=1000000000){
            count+=zeroes;
        }else{
            return -1;
        }
    }
    return count;
}

// 5-Prefix Sums: CountDiv
// count number of integers divisible by K in the range [A..B]
// time:O(1) space:O(1)
int solution(int A, int B, int K) {

    if (A%K == 0) return  ( B/K - A/K + 1 );
    return ( B/K - A/K );
}

// 5-Prefix Sums: MinAvgTwoSlices
// find slice of A having minimum average, return firs index of slice
// time:O(N) space:O(N)
// NOTE slice longer than 3 are surely bigger because
//      avg(n,n+3) = (avg(n,n+1)+avg(n+2,n+3))/2 
int solution(int A[], int N) {
    
    int p[N+1];
    p[0]=0;
    p[1]=A[0];
    p[2]=p[1]+A[1];
    
    double minavg = p[2]/2;
    int minindex=0;

    for(int i=3;i<=N;i++){
        p[i]=p[i-1]+A[i-1];
        
        if ( ((p[i]-p[i-2])/2.0) < minavg ){
            minindex=i-2;
            minavg=(p[i]-p[i-2])/2.0;
        }
        
        if ( ((p[i]-p[i-3])/3.0) < minavg ){
            minindex=i-3;
            minavg=(p[i]-p[i-3])/3.0;
        }
    }   
    return minindex;
}

// 5-Prefix Sums: GenomicRangeQuery
// find the minimal element in M given sequence (A[P[0:M-1] to A[Q[0:M-1]]
// where 'A'=1, 'C'=2, 'G'=3, 'T'=4
#include <strings.h>
#include <strings.h>
struct Results solution(char *S, int P[], int Q[], int M) {
    
    struct Results result;
    
    result.A = (int*)(malloc(sizeof(int)*M));
    result.M = M;
    
    int i;
    int N=strlen(S);
    int count[N][4];
    int t[4]={0,0,0,0};
    
    bzero(count,sizeof(int)*N*4);
    
    for (i=0;i<N;i++){
        
       switch (*(S+i)){

            case 'A': 
                t[0]++;
                break;
            case 'C': 
                t[1]++;
                break;
            case 'G': 
                t[2]++;
                break;
            case 'T': 
                t[3]++;  
                break;
        }
        
        count[i][0]=t[0];
        count[i][1]=t[1];
        count[i][2]=t[2];
        count[i][3]=t[3];
    }
    
    int c;
    int cur;
    for (i=0;i<M;i++){
        
        result.A[i]=4;
        for(c=2;c>=0;c--){
            cur=count[Q[i]][c];
            if (P[i]>0) cur -= count[P[i]-1][c];
            if (cur>0) result.A[i]=c+1;
        }
    }
    
    return result;
}

// LESSON 6 ////////////////////////////////////////////////////////////////////

// 6-sort: Distinct
// Compute number of distinct values in an array.
void merge(int *a, int *b, int lo, int mid, int hi)
{
	int k;
	int i = lo, j = mid+1;
	for (k = lo; k <= hi; k++) {
		if (i > mid) b[k] = a[j++];
		else if (j > hi) b[k] = a[i++];
		else if ((a[j] < a[i])) b[k] = a[j++];
		else b[k] = a[i++];
	}
}
void sort(int *a, int *b, int lo, int hi)
{
	if (hi <= lo) return;
	int mid = lo + (hi - lo) / 2;
	sort(b, a, lo, mid);
	sort(b, a, mid+1, hi);
	merge(a, b, lo, mid, hi);
}
int solution(int A[], int N) 
{
    if (N==0) return 0;
    int i;
    int b[N];
    for (i=0;i<N;i++) b[i]=A[i];
    sort(A,b,0,N-1);
    int count=1;
    for (i=1;i<N;i++) if (b[i]!=b[i-1]) count++;
    return count;
}

// 6-sort: MaxProductOfThree
// Find the maximum triplet in the array (A[p]*A[q]*A[r])
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void partial_sort_higher_n(int* a, int size, int count)
{
	int i, j;
	for(j=1;j<count+1;j++){
		for(i=0;i<size-j;i++){
			if (a[i]>a[size-j]){
			    swap(a+i,a+size-j);
			}
		}	
	}
}
void partial_sort_lower_n(int* a, int size, int count)
{
	int i, j;
	for(j=0;j<count;j++){
		for(i=j;i<size;i++){
			if (a[i]<a[j]){
			    swap(a+i,a+j);
			}
		}	
	}
}
int solution(int A[], int N) {
    if (N==3) return (A[0]*A[1]*A[2]);
    partial_sort_higher_n(A, N, 3);
    partial_sort_lower_n(A, N, 2);
    int r1=A[N-1]*A[N-2]*A[N-3];
    int r2=A[N-1]*A[0]*A[1]; // numbers can be negative
    return (r1>r2?r1:r2);
}

// 6-sort: Triangle
// return 1 if there's a tringular triplet in the array
// = tree items A[p]+A[q]>A[r], A[q]+A[r]>A[p], A[r]+A[p]>A[q]
int cmpfunc(const void * a, const void * b)
{
    int A=*(int*)a;
    int B=*(int*)b;
    
    if (A>B) return 1;
    else if (A<B) return -1;
    return 0;
}
int solution(int A[], int N) 
{
    if (N<3) return 0;
    
    qsort(A, N, sizeof(int), cmpfunc);
    
    int i;
    for (i=0;i<N-2;i++){
        // A can be MAXINT so is safer to convert it to long long
        if ((long long)A[i]+(long long)A[i+1]>(long long)A[i+2]) return 1;   
    }
    return 0;
}

// 6-sort: NumberOfDiscsIntersections
// count intersections where
// A[i] represents a circle centered in i with r=A[i]
int cmpfunc(const void * a, const void * b)
{
    long long A=*(long long*)a;
    long long B=*(long long*)b;
    
    if (A>B) return 1;
    else if (A<B) return -1;
    return 0;
}

int solution(int A[], int N) 
{
    long long low[N]; // array of segmnt's starting points
    long long hig[N]; // array of segments ending points
    
    int i;
    for (i=0;i<N;i++){
        low[i]=(long long)i-A[i];
        hig[i]=(long long)i+A[i];
    }
    
    qsort(low, N, sizeof(long long), cmpfunc);
    qsort(hig, N, sizeof(long long), cmpfunc);
    
    int ret=0;    // number of intersections
    int scount=1; // segments counter
    int j=0;      // ending points index
    
    for(i=1;i<N;i++){
        
        while((j<N)&&(low[i]>hig[j])){
        	// discard a segment
            j++;
            scount--;
        }
        ret += scount;
        if (ret>10000000) return -1;
        scount++;
        
    }
    return ret;
}

// LESSON 7 ////////////////////////////////////////////////////////////////////

// 7 Stacks and queues: Brackets
// Determine whether a given string of parentheses is properly nested
int solution(char *S) 
{
	// NOTE: has not free
    char *stack=malloc(sizeof(char)*strlen(S));
    char *ps=stack;
    char *p=S;
    
    while(*p!=0){
        
        switch (*p){
            case '(':
            case '[':
            case '{':
                *ps=*p;
                ps++;
                break;
            case '}':
                if (*(ps-1)!='{') return 0;
                ps--;
                break;
            case ']':
                if (*(ps-1)!='[') return 0;
                ps--;
                break;
            case ')':
                if (*(ps-1)!='(') return 0;
                ps--;
                break;
        }
        p++;      
    }
    if (ps!=stack) return 0;
    return 1;
}

// 7 Stacks and queues: StoneWAll
// How much rectangular stones are required to build the H skyline
#define CAPACITY 100000
int stack[CAPACITY];     
int top = -1;
int isempty()
{
	if (top == -1) return 1;
	else return 0;
}
int isfull() 
{
	if (top == CAPACITY) return 1;
	else return 0;
}
int pop() 
{
	int data=0;
	if (!isempty()) {
		data = stack[top];
		top--;
	} 
	return data;
}
void push(int data) 
{
	if (!isfull()) {
		top++;
		stack[top] = data;
	}
}
int solution(int H[], int N) {
    
    int count=0;
    int i;
    int found=0;
    for (i=0;i<N;i++){
        
        found=0;
        while(!isempty()){
            if (stack[top]<H[i]) break;
            else if (stack[top]>H[i]) pop();
            else if (stack[top]==H[i]){
                found=1;
                pop();
                break;
            }
        }
        push(H[i]);
        if (!found) count++;
    }
    return count;
}

// 7 Stacks and queues: Nesting
// test if given string of parentheses is properly nested
int solution(char *S) 
{
    int count=0;
    while(*S!=0){
        if (*S=='(') count++;
        else count--;
        if (count<0) return 0;
        S++;
    }
    return (count==0?1:0);
}

// 7 Stack and queues: Fish
// N voracious fish are moving along a river. Calculate how many fish are alive. 
int capacity;
int *stack;     
int top = -1;            
int isempty() 
{
	if (top == -1) return 1;
	else return 0;
}
int isfull() 
{
	if (top == capacity) return 1;
	else return 0;
}
int pop() 
{
	int data=0;
	if (!isempty()) {
		data = stack[top];
		top--;
	} 
	return data;
}
void push(int data) 
{
	if (!isfull()) {
		top++;
		stack[top] = data;
	}
}
int solution(int A[], int B[], int N) {
    
    int count=0;
    int i=0;
    stack = malloc(sizeof(int)*N);
    capacity=N;
    
    while(i<N){
        if (B[i]==1){
            push(A[i]);
            i++;
        }else{
            while((!isempty())&&(i<N)){
                if (stack[top]<A[i]) pop();
                else{
                    i++;
                    break;
                }
            }
            if (isempty()){
                count++;
                i++;
            }
        }
    }
    
    return (count+top+1);
}

// LESSON 8 ////////////////////////////////////////////////////////////////////

// 8-Leader: Dominator
// return one of the indexes of the leader or -1
int solution(int A[], int N) 
{
	if (N==0) return -1;
	if (N==1) return A[0];

	int k;
	int stacksize=0;
	int value;
	
	for(k=0;k<N;k++){
	
		if (stacksize==0){
			stacksize++;
			value=A[k];
		}else if(value!=A[k]){
			stacksize--;
		}else{
			stacksize++;
		}
	}
	
	if (stacksize<=0) return -1;
	
	int count=0;
	int index=-1;
	for(k=0;k<N;k++){
		if (A[k]==value){
	        count++;
	        index=k;
		}
	}
	if (count>N/2) return index;
	return -1;
}

// 8-Leader: EquiLeader
// count of equileader: points that divide the sequence 
// in two sequences having the same leaders
int solution(int a[], int size) {
   
	if (size==1) return 0;

	int k;

	int stacksize=0;
	int value;

	for(k=0;k<size;k++){
	
		if (stacksize==0){
			stacksize++;
			value=a[k];
		}else if(value!=a[k]){
			stacksize--;
		}else{
			stacksize++;
		}
	}
	
	if (stacksize<=0) return 0;
	
	int count=0;
	for(k=0;k<size;k++){
		if (a[k]==value) count++;
	}
	if (count<=size/2) return 0;
	
	int pcount=0;
	int ret=0;
	
	for(k=0;k<size;k++){
		if (a[k]==value) pcount++;
		if ((pcount>(k+1)/2.0)&&(count-pcount>(size-k-1)/2.0)) ret++;
	}	
   
    return ret;
}

// LESSON 9 ////////////////////////////////////////////////////////////////////

// 9-Maximum slice problem: MaxProfit 
// return maximum possible profit with A[]:daily prices of a stock share
int solution(int A[], int N) {
    
    if (N<=1) return 0;
    
    int a[N-1];
    int k;
    
    for(k=0;k<N-1;k++){
        a[k]=A[k+1]-A[k];
    }
    
    int max_ending=0;
	int max_slice=0;
	
	for(k=0;k<N-1;k++){
		max_ending=((0>(max_ending+a[k]))?0:(max_ending+a[k]));
		if (max_ending>max_slice) max_slice=max_ending;
	}

	return max_slice;
}

// 9-Maximum slice problem: MaxSliceSum
// return max non null slice in array
int solution(int A[], int N) {
    
    int max_ending=0;
	int max_slice=0;
	
	int k;
	for(k=0;k<N;k++){
		max_ending=((0>(max_ending+A[k]))?0:(max_ending+A[k]));
		if (max_ending>max_slice) max_slice=max_ending;
	}
	
	if (max_slice==0){
	    max_slice=A[0];
	    for(k=0;k<N;k++){
	        if (A[k]>max_slice) max_slice=A[k];
	    }
	}

	return max_slice;
}

// 9-Maximum slice problem: MaxDoubleSliceSum
// find the max of double slice where A<B<C = sum(a[A+1]:a[B-1])+sum(a[B+1]:a[C-1])
int solution(int A[], int N) {
    
    int k;
    int max_until[N];
    max_until[0]=0;
    max_until[1]=0;

	for(k=2;k<N;k++){
		max_until[k]=((0>(max_until[k-1]+A[k-1]))?0:(max_until[k-1]+A[k-1]));
	}
	
    int max_from[N];
    max_from[N-1]=0;
    max_from[N-2]=0;
    
    for(k=N-3;k>=0;k--){
        max_from[k]=((0>(max_from[k+1]+A[k+1]))?0:(max_from[k+1]+A[k+1]));
    }
    
    int max_double=0;
    for(k=1;k<N-1;k++){
        if (max_until[k]+max_from[k]>max_double) max_double=max_until[k]+max_from[k];
    }
    
    return max_double;
}

// LESSON 10 ///////////////////////////////////////////////////////////////////

// 10-Prime and composite numbers: CountFactors
// count factors of given number n. 
int solution(int N) {
    
    int i=1;
	int count=0;
	while(((long long)i*i)<N){
		if (N%i==0) count+=2;
		i++;
	}
	if ((long long)i*i==N) count++;
	return count;
}

// 10-Prime and composite numbers: MinPerimeterRectangle
// Find the minimal perimeter of any rectangle whose area equals N
int solution(int N) {
    
    int i=1;
	int min=2*(N+1);
	
	while(((long long)i*i)<N){
		if (N%i==0){
		    if (2*(i+N/i)<min) min=2*(i+N/i);
		}
		i++;
	}
	if ((long long)i*i==N){
	    if ((4*i)<min) min=4*i;
	}
	return min;
}

// 10-Prime and composite numbers: Flags
// How many flags can be put on the peaks
int solution(int A[], int N) {
    
    if (N<3) return 0;
    
    int k;
    int pcount=0;
    int peak[N/2];
    
    for(k=1;k<N-1;k++){
        if ((A[k-1]<A[k])&&(A[k+1]<A[k])){
            peak[pcount]=k;
            pcount++;
        }
    }
    
    if (pcount<3) return pcount;
    
    int max=2;
    int count;
    int p;
    int flag;
    for(k=2;k<=pcount;k++){
        
        count=1;
        flag=0;
        
        for(p=1;(p<pcount)&&(count<k);p++){
            if (peak[p]-peak[flag]>=k){
                count++;
                flag=p;
            }
        }
        if (count>max) max=count;
        else if (count<max) break;
    }
    return max;
}

// 10-Prime and composite numbers: Peaks
// Divide an array into the maximum number of same-sized blocks
// Each block must contains at least one peak
int solution(int A[], int N) 
{
    int k;
    int pcount=0;
    int peaks[N];
    
    peaks[0]=0;
    for(k=1;k<N-1;k++){
        if ((A[k-1]<A[k])&&(A[k+1]<A[k])){
            pcount++;
        }
        peaks[k]=pcount;
    }
    peaks[N-1]=pcount;
    
    if (pcount<1) return 0;
    if (pcount==1) return 1;

    int blockcount;
    int blocksize;
    int p;
    int prevcount;
    int found=0;
    
    for (blockcount=pcount;(blockcount>0)&&(found==0);blockcount--){
        
        if (N%blockcount!=0) continue;
        blocksize=N/blockcount;
        prevcount=0;
        found=1;
        
        for(p=blocksize-1;(p<N)&&(found==1);p+=blocksize){
            if (peaks[p]<=prevcount) found=0;
            prevcount=peaks[p];
        }
    }
    return blockcount+1;
}

// LESSON 11 ///////////////////////////////////////////////////////////////////

// 11-Sieve of Eratosthenes: CountSemiprimes
// cont semiprimes (=two prime factors) in each P-Q interval
#include <string.h>
struct Results solution(int n, int P[], int Q[], int M) {
    
    struct Results result;
    
	int F[n];
	memset(F,0,sizeof(int)*n);
	
	// build the sieve
	int i=2;
	int k;
	while(i*i<=n){
		if (F[i-1]==0){
			k=i*i;
			while(k<=n){
				if (F[k-1]==0) F[k-1]=i;
				k += i;
			}
		}
		i++;
	}
	
	int semiprimesacc[n];
	int num;
	int primefactcount;
	int sempiprimestot=0;
	for(k=0;k<n;k++){
	    
	    num=k+1;
	    
    	// count prime factors using sieve
    	primefactcount=1;
    	while(F[num-1]>0){
    		primefactcount++;
    		num/=F[num-1];
    	}
    	
    	if (primefactcount==2) sempiprimestot++;
    	semiprimesacc[k]=sempiprimestot;
	}

    result.A = (int*)malloc(sizeof(int)*M);
    result.M = M;	
	
	for(k=0;k<M;k++){
	    result.A[k]=semiprimesacc[Q[k]-1]-semiprimesacc[P[k]-2];
	}

    return result;
}

// 11-Sieve of Eratosthenes: CountNonDivisible
// Calculate the number of elements of an array that are not divisors of each element
struct Results solution(int A[], int N) {
    
    int k;
    struct Results result;
    
    int max=0;
    for(k=0;k<N;k++){
        if (A[k]>max) max=A[k];
    }
    
    // suppose each num in set has N divisors inside the array
    int dcount[max];
    for(k=0;k<max;k++) dcount[k]=N;
    
    // decrease div counters for each multiple of numbers in the array
    int n;
    for(k=0;k<N;k++){
        for(n=A[k];n<=max;n+=A[k]){
            if (dcount[n-1]>0) dcount[n-1]--;   
        }
    }
    
    result.C = (int*)malloc(sizeof(int)*N);
    result.L = N;
    
    // result is the counter
    for(k=0;k<N;k++){
        result.C[k]=dcount[A[k]-1];
    }
    
    return result;
}

// LESSON 12 ///////////////////////////////////////////////////////////////////

// 12-Euclidean Algorithm: ChocolatesByNumbers
// There are N chocolates in a circle. 
// Count the number of chocolates you will eat
// proceeding by M steps until a empty place
long long gcd(long long a, long long b)
{
	if (a%b==0) return b;
	return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
	return (a*b)/gcd(a,b);
}
int solution(int N, int M) 
{
    if (N==0) return 0;
    if (M==0) return 1;
    
    return lcm(N,M)/M;
}

// 12-Euclidean Algorithm: CommonPrimeDivisors 
// return count of pairs in arrays having the same prime factors
int gcd(int a, int b)
{
	if ((a==0)||(b==0)) return 0;
	if (a%b==0) return abs(b);
	return gcd(b,a%b);
}
int same_prime_factors(int a, int b)
{
	int init_gcd=gcd(a,b);

	int aux_gcd=init_gcd;
	while (aux_gcd != 1){
		a /= aux_gcd;        
		aux_gcd = gcd(a, aux_gcd);
	}
	if (a != 1) return 0;

	aux_gcd = init_gcd;
	while (aux_gcd != 1){
		b /= aux_gcd;        
		aux_gcd = gcd(b, aux_gcd);
	}
	if (b != 1) return 0;

	return 1;  
}
int solution(int A[], int B[], int Z) 
{
    int k;
    int count=0;
    for (k=0;k<Z;k++){
        count +=  same_prime_factors(A[k],B[k]);
    }
    return count;
}

// LESSON 13 ///////////////////////////////////////////////////////////////////

// 13-Fibonacci: Ladder
// Count the number of different ways of climbing to 
// the top of a ladder with 1 or 2 steps 
typedef unsigned long long ull;
struct Results solution(int A[], int B[], int L) {
    
    ull k;
	ull fib[L+1];
	fib[0]=0;
	fib[1]=1;
	
	// ull can reach 92-th fibonacci num
	// so overflow is assured here
	for(k=2;k<L+2;k++){
		fib[k]=fib[k-1]+fib[k-2];
	}

    struct Results result;
	result.C=(int*)malloc(sizeof(int)*L);
    result.L=L;
    
	int mod;
	for (k=0;k<L;k++){
        mod=1<<B[k];
        // we can ignore overflow because the answer
        // is modulo(2^B)
        result.C[k]=fib[A[k]+1]%mod;
	}

    return result;
}

// 13-Fibonacci: FibFrog
// return fibonacci jumps count from -1 to N
#include <alloca.h>
#include <memory.h>
#include <limits.h>
int solution(int A[], int N) 
{
    //for N = 0, 1, 2, the distance to jump from `-1' (the origin)
    //can be 1, 2, 3. then we know these a fibonacci number.
    if (N <= 2) return 1;
    
    //each reached[i] cell remembers the minimum jumps made to reach there so far.
    int* reached = (int*)alloca(sizeof(int) * N);
    memset(reached, 0x00, sizeof(int) * N);
    
    //these two cells can be reached when there are leaves there.
    //since 0 and 1 can be reached by the first jump, we only care if 
    //there is a leaf or not.
    reached[0] = A[0]; 
    reached[1] = A[1];
    
    //we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
    //we only have to generate 25 fibonacci numbers.
    int* fibN = (int*)alloca(26 * sizeof(int));
    fibN[0] = 0;
    fibN[1] = 1;
    int i = 2;
    while (i < 26){
        fibN[i] = fibN[i - 1] + fibN[i - 2];
        //if one jump is enough, we can simply return here.
        if (fibN[i] == N+1) return 1;
        //we also mark the position that can be reached by the first jump.
        if (fibN[i] - 1 < N && A[fibN[i] - 1] == 1) reached[fibN[i] - 1] = 1;
        i++;
    }
    
    //let's check each cell
    int min = INT_MAX;
    
    for (i = 0; i < N; i++){
    
        //if the cell is not reachable, we can neglect it.
        if (reached[i] == 0) continue;

        int min_jumps_to_here = reached[i];
        int j;
        
        for (j = 2; j < 26; j++){
        
            int next_pos = i + fibN[j];
            
            //if we can reach the other bank (the position N),
            // update min if necessary.
            if (next_pos == N){
                min = min_jumps_to_here + 1 < min ? min_jumps_to_here + 1 : min;
                break;
            }
            
            //if the next jump is too large, or there is no leaf there,
            //we can neglect this jump.
            if (next_pos > N || A[next_pos] == 0) continue;
                        
            //if we have never reached to the next position before, or we can reach 
            //the next position with less jumps, update the min number of jumps
            // at the position.
            if (reached[next_pos] == 0 || reached[next_pos] > min_jumps_to_here + 1){
                reached[next_pos] = min_jumps_to_here + 1;
            }
        }
    }
    
    if (min!=INT_MAX) return min;
    return -1;
}

// LESSON 14 ///////////////////////////////////////////////////////////////////

// 14-Binary Search: NailingPlanks
// how many nails C (used in sequence) are required to fix all planks A-B
int solution(int A[], int B[], int N, int C[], int M) {
    
    // accumulators for all C values
    int nail_acc[2*M+2];
    // partial sums of all accumulators
    int nail_acc_psum[2*M+2];
    
    // index for binary search
    int nhig=M-1;
    int nlow=0;
    int nmid;
    
    // answer
    int ncountmin=-1;
    
    int i;
    int count;
    
    while(nlow<=nhig){
        
        // binary search
        nmid=(nhig+nlow)/2;;
        
        // fill accumulators until C[nmid]
        for (i=0;i<2*M+2;i++) nail_acc[i]=0;
        for (i=0;i<=nmid;i++) nail_acc[C[i]]++;
        
        // fill partial sums of accumulators
        nail_acc_psum[0]=nail_acc[0];
        for (i=1;i<2*M+2;i++) nail_acc_psum[i]=nail_acc_psum[i-1]+nail_acc[i];
        
        // test all planks
        count=0;
        for (i=0;i<N;i++){
            if (nail_acc_psum[B[i]]-nail_acc_psum[A[i]-1]>0){
            	count++;
            }
        }
        
        if (count==N){
            ncountmin=nmid+1;
            nhig=nmid-1;
        }else{
            nlow=nmid+1;
        }
    }
    
    return ncountmin;
}

// 14-Binary Search: MinMaxDivision
// Divide array A into K blocks and minimize the largest sum of any block
int test_subarray(int A[], int size, int maxslicecount, int maxslicesum)
{
	// test if array can be divided in maxslicecount of maxslicesum

	int i;
	int sum=0;
	int slicecount=1;
	
	for (i=0; i<size; i++){
		
		if (A[i]>maxslicesum) return 0;
	
		sum += A[i];
		if (sum > maxslicesum){
		    slicecount++;
		    if (slicecount>maxslicecount) return 0;
		    sum = A[i];
		}
	}
	
	if (slicecount>maxslicecount) return 0;
	return 1;
}
int solution(int K, int M, int A[], int N) {
    
    int i;
    int min=0;
    int max=0;
    int med;
    for (i=0;i<N;i++) max+=A[i];
    
    int res=max;
    
	while(min<=max){
	    
		med=(min+max)/2;
		
		if (test_subarray(A, N, K, med)==1){
		    if (med<res) res=med;
		    max=med-1;
		}else{
		    min=med+1;
		}
	}
	return res;
}

// LESSON 15 ///////////////////////////////////////////////////////////////////

// 15-CaterpillarMethod: CountDistinctSlices
// Count the number of distinct slices (containing only unique numbers)
int solution(int M, int A[], int N) {
    
	unsigned long long count=0;
	int acc[M+1];
	int i;
	for(i=0;i<M+1;i++) acc[i]=-1;
    
	int front=0;
	int back=0;
	
	while(front<N){
	
		if (acc[A[front]]>=back){
			back=acc[A[front]]+1;
		}else{
			acc[A[front]]=front;
			count+=front-back+1;
			if (count>1000000000) return 1000000000;
			front++;
		}
	}
	return count;
}

// 15-CaterpillarMethod: AbsDistinct
// Compute number of distinct absolute values of sorted array elements
int solution(int A[], int N) {
    
    if (N==1) return 1;
    
    int count=1;
    
    if (A[0]>=0 || A[N-1]<=0){

        int i;
        for (i=1;i<N;i++){
            if (A[i]!=A[i-1]) count++;
        }
        return count;
    }
    
    int beg=0;
    int end=N-1;
    
    unsigned int ab,ae;
    
    while(beg!=end){
        
        ab=abs(A[beg]);
        ae=abs(A[end]);
        
        if (ab!=ae) count++;
        
        if (ab>ae && A[beg+1]<=0){
            
            beg++;
            while(A[beg]==A[beg-1] && A[beg+1]<=0) beg++;
            
        }else if (ab<ae && A[end-1]>=0){;
         
            end--;
            while(A[end]==A[end+1] && A[end-1]>=0) end--;
            
        }else{
            
            if (A[beg+1]<=0) beg++;
            else if (A[end-1]>=0) end--;
            else return count; 
        }
    }
    
    return count;
}

// 15-CaterpillarMethod: CountTriangles
// Count the number of triangles that can be built from a given set of edges
int cmpfunc(const void * a, const void * b)
{
    int A=*(int*)a;
    int B=*(int*)b;
    
    if (A>B) return 1;
    else if (A<B) return -1;
    return 0;
}
int solution(int A[], int N) 
{
	if (N<3) return 0;

	qsort(A, N, sizeof(int), cmpfunc);

	int count=0;
	int x,y,z;
	for(x=0; x<N; x++){

		z=x+2;
		for(y=x+1; y<N; y++){
			while((z<N) && ((A[x]+A[y])>A[z])){
				z++;
			}
			count+=z-y-1;
		}
	}
	return count;
}

// 15-CaterpillarMethod: MinAbsSumOfTwo
//Find the minimal absolute value of a sum of two elements
int cmpfunc(const void * a, const void * b)
{
    int A=*(int*)a;
    int B=*(int*)b;
    
    if (A>B) return 1;
    else if (A<B) return -1;
    return 0;
}
int solution(int A[], int N) {

	int min=abs(A[0]+A[0]);
	if (N==1) return min;

	qsort(A, N, sizeof(int), cmpfunc);
	
	int end=0;
	while (end<N && A[end]<0) end++;

	if (end==0) return 2*A[0];
	if (end==N) return -2*A[N-1];

	int beg=end-1;
	int curr;

	while ( beg>=0 && end<N ){
	
        curr=abs(A[beg]+A[end]);
        if (curr<min) min=curr;
        
        if (min==0) break;

		if (A[end]+A[beg]<0) end++;
		else beg--;
	}
	return min;    
}

// LESSON 16 ///////////////////////////////////////////////////////////////////

// 16 - Greedy algorithms: TieRopes
// Tie adjacent ropes to achieve the maximum number of ropes of length >= K. 
int solution(int K, int A[], int N) {
    
    int count=0;
    unsigned int len=0;
    int i;
    
    for(i=0;i<N;i++){
        len+=A[i];
        if (len>=K){
            count++;
            len=0;
        }
    }

    return count;
}

// 16 - Greedy algorithms: MaxNonoverlappingSegments
// Find a maximal set of non-overlapping segments
// NOTE: segments are ordered by B (end point)
int solution(int A[], int B[], int N) {
    
    if (N<2) return N;
        
	int count = 1;
	int end = B[0];

	int i;
	for (i = 1; i < N; i++) {
		if (A[i] > end) {
			count++;
			end = B[i];
		}
	}

	return count;
}

// LESSON 17 ///////////////////////////////////////////////////////////////////

// 17 - Dynamic Programming: NumberSolitaire
// In a given array, find the maximal sum of subset in which 
// the distance between consecutive elements is at most 6. 
int solution(int A[], int N) {
    
    int i=0;
	int p;
    int sum;
    
    for (i=1;i<N;i++){
		
		sum = A[i] + A[i-1];
		
		for(p=2; p<=6 && i-p>=0;p++){
			if (A[i]+A[i-p] > sum){ 
				sum = A[i]+A[i-p];
			}
		}
		
		A[i]=sum;
    }

    return A[N-1];
}

// 17 - Dynamic Programming: MinAbsSum
// Given array of integers, find the lowest absolute sum of elements
// correct:100% performance:80%
int solution(int A[], int N) {
    
    int i,j;
    int max=0;
    int sum=0;
    for (i=0;i<N;i++){
        A[i]=abs(A[i]);
        if (A[i]>max) max=A[i];
        sum += A[i];
    }
    
    int C[max+1];
    for (i=0;i<max+1;i++) C[i]=0;
    for (i=0;i<N;i++) C[A[i]]++;

    int R[sum+1];
    for(i=1;i<sum+1;i++) R[i]=-1;
    R[0]=0;
    
    for(i=1;i<max+1;i++){
    	if (C[i]>=0){
		    for(j=0;j<=sum;j++){
				if (R[j]>=0) R[j]=C[i];
				else if (j>=i && R[j-i]>0) R[j] = R[j-i]-1;
		    }
        }
    }
    
    int upper=sum;
    int half = sum/2.0+0.5;
    
    for(i=0;i<half;i++){
        if (R[half+i]>=0){
        	upper=half+i;
        	break;
        }
    }
    
    return 2*upper-sum;
}