**Question: **

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly **n** number of cells between two placed locations of number **n.**

**Sample:**

One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

**Solution:**

We will try backtracking approach, we move from index 0 to 2N-1, at each index, we try to place a number that hasn’t been used, and then move to next index and repeat the process, if in between we find there is no number possible at some index, that means we were incorrect, and we need to backtrack. If we reach to last index, and place a number safely there, that means its possible to have such arrangement.

#include<iostream> #include<climits> #include<cstdlib> #include<cstdio> #include<ctime> #include<cstring> using namespace std; #define FOR(i,a,b) for(__typeof(b) i=(a);i<(b);++i) #define REP(i,n) for(__typeof(n) i=0;i<(n);i++) #define FILL(a,b) memset(a,b,sizeof(a)) #define SIZE 100 int N,len; int arr[SIZE]; bool numbers[SIZE]; bool permute(int pos){ /*if pos>=len , that means we have placed all the numbers from 1 to N , so we can print the array, and return */ if(pos>=len){ //nothing fancy, just printing the array printf("POSSIBLE for N = %d ----> ",N); REP(i,len){ cout<<arr[i]<<" "; } cout<<endl; return true; } //if that position is already filled, that means move on 😛 if(arr[pos]!=0){ return permute(pos+1); } //go through all numbers FOR(i,1,N+1){ //if number is not used if(!numbers[i]){ //if second place is in bound if(pos+i+1<len&&!arr[pos]&&!arr[pos+i+1]){ arr[pos]=i;//place the number i at index pos arr[pos+i+1]=i;//place the number i at index pos+i+1 numbers[i]=true;//number i used now //check if this will lead us to end if(permute(pos+1)){ return true; } //BACKTRACK arr[pos]=0;//free the index pos arr[pos+i+1]=0;//free the index pos+i+1 numbers[i]=false;//number not used now } } } return false; } void doThis(){ //N number scanf("%d",&N); // 2N places len = 2*N; //initialise array with 0 FILL(arr,0); FILL(numbers,false);//all numbers are free to be used //here we go if(permute(0)){ //if possible then no need to do anything 🙂 }else{ printf("NOT POSSIBLE for N = %d\n",N); } } int main(){ #ifdef amy freopen("C:\\A\\in.txt","r",stdin);freopen("C:\\A\\out.txt","w",stdout); #endif int t; scanf("%d",&t);//number of test cases while(t--){doThis();} #ifdef amy fprintf(stdout,"\nTIME: %.3lf sec\n",(double)clock()/(CLOCKS_PER_SEC)); #endif return 0; } /* INPUT 12 1 2 3 4 5 6 7 8 9 10 11 12 OUTPUT NOT POSSIBLE for N = 1 NOT POSSIBLE for N = 2 POSSIBLE for N = 3 ----> 2 3 1 2 1 3 POSSIBLE for N = 4 ----> 2 3 4 2 1 3 1 4 NOT POSSIBLE for N = 5 NOT POSSIBLE for N = 6 POSSIBLE for N = 7 ----> 1 4 1 5 6 7 4 2 3 5 2 6 3 7 POSSIBLE for N = 8 ----> 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8 NOT POSSIBLE for N = 9 NOT POSSIBLE for N = 10 POSSIBLE for N = 11 ----> 1 2 1 4 2 8 9 10 4 11 6 3 7 5 8 3 9 6 10 5 7 11 POSSIBLE for N = 12 ----> 1 2 1 3 2 8 9 3 10 11 12 5 7 4 8 6 9 5 4 10 7 11 6 12 TIME: 0.069 sec */

Advertisements