fishery_Samsung

/*
Given:
Fishing Spots: 1 to N
3 Gates with gate position and number of fishermen waiting to get in
Distance between consecutive spots = distance between gate and nearest spot = 1 m

Fishermen are waiting at the gates to get in and occupy nearest fishing spot. Only 1 gate can be opened at a time and all fishermen of that gate must occupy spots before next gate is open.
There could be 2 spots closest to the gate. Assign only 1 spot to the last fisherman in such a way that we get minimum walking distance. For rest of the fishermen, ignore and assign any one.

Write a program to return sum of minimum distance need to walk for fishermen.

Distance is calculated as gate to nearest spot + nearest spot to closest vacant spot.
If the gate is at position 4, then fishermen occupying spot 4 will walk 1 m,
*/
#include <iostream>
#define INT_MAX 99999
using namespace std;

struct Gate{
    int loc,men;
}gate[4];

int n;
bool visited[100];
int ans=INT_MAX;

//findign nearest left position
int findLeft(int indx){
    for(int i=indx; i>0; i--)
        if(visited[i]==false) return i;
    return INT_MAX;
}

//finding nearest right position
int findRight(int indx){
    for(int i=indx+1; i<=n; i++)
        if(visited[i]==false) return i;
    return INT_MAX;
}


void solve(int x, int y, int z, int cur_pos, int cost){
    if(cost> ans) return;

    //base condition
    //when all men have went through 1 gate change gate
    if(gate[cur_pos].men == 0){
      if(cur_pos == x)cur_pos = y;
      else if(cur_pos == y)cur_pos = z;
      else{
          ans = min(ans,cost);
          return;
      }
    }

    //nearest left vacant spot
    int left = findLeft(gate[cur_pos].loc);
    int ll = abs(gate[cur_pos].loc - left) +1;

    //nearest right vacant spot
    int right = findRight(gate[cur_pos].loc);
    int rr = abs(gate[cur_pos].loc -right) +1;

    bool goLeft=true , goRight=true;

    if(ll>rr) goLeft=false;
    else if(rr>ll) goRight=false;

    //goint in the direction where the distance is less
    if(goLeft){
        gate[cur_pos].men-=1;
        visited[left]=true;
        solve(x,y,z,cur_pos,cost + ll);
        visited[left]=false;
        gate[cur_pos].men+=1;
    }
    if(goRight){
        gate[cur_pos].men-=1;
        visited[right]=true;
        solve(x,y,z,cur_pos,cost + rr);
        visited[right]=false;
        gate[cur_pos].men+=1;
    }
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;

        for(int i=1; i<=3; i++)
            cin>>gate[i].loc>>gate[i].men;

        for(int i=0; i<100; i++)
            visited[i]=false;

        ans=INT_MAX;
        //calling for all permutations of gate opening
        solve(1,2,3,1,0);
        solve(1,3,2,1,0);
        solve(2,1,3,2,0);
        solve(2,3,1,2,0);
        solve(3,1,2,3,0);
        solve(3,2,1,3,0);

        cout<<ans<<endl;
    }
    return 0;
}



/* TestCases
5
10
4 5
6 2
10 2
10
8 5
9 1
10 2
24
15 3
20 4
23 7
39
17 8
30 5
31 9
60
57 12
31 19
38 16



outputs
18
25
57
86
339
*/