cau ca - NDDCoder

https://www.geeksforgeeks.org/samsung-semiconductor-institute-of-research-ssir-software-intern-fte-set-1/

#include<iostream>
using namespace std;
int NSpot;
int totalPerson;
struct Gate{
	int toado;
	int numPerson;
};
Gate gate[4];
int tc,T;
int markGate[4];
int PositionSpot[100];
int rs;
int abs(int val){
	if(val<0) return -val;
	return val;
}
void backtrack(int numGate,int numPerInGate,int total,int cnt){
	if(numGate>3) return;
	if(total>=totalPerson){
		if(cnt<rs){	
			rs = cnt;
			if(rs==18){
				for(int i=1;i<=NSpot;i++){
					cout<<PositionSpot[i]<<" ";
				}
				cout<<endl;
			}
			return;
		}
	}
	if(numPerInGate>=gate[numGate].numPerson){
		markGate[numGate] = 1;
		backtrack(numGate+1,0,total,cnt);
		markGate[numGate] = 0;
	}
	for(int i=1;i<=3;i++){
		//thu tung gate
		if(!markGate[i]){//neu cong gate chua mo thi mo de cho nguoi vao
			int numPer = gate[i].numPerson;
			for(int j=1;j<=NSpot;j++){
				if(!PositionSpot[j]){//neu vi tri cau ca con trong thi cho vao
					PositionSpot[j] = gate[numGate].toado;
					backtrack(numGate,numPerInGate+1,total+1,cnt+abs(gate[i].toado-j)+1);
					PositionSpot[j] = 0;
				}
			}
		}
	}
}
void initPosSpot(){
	for(int i=1;i<=NSpot;i++)
		PositionSpot[i] = 0;
}
int main()
{
    freopen("fishing.txt","r",stdin);
    cin>>T;
    for(tc=1;tc<=T;tc++){
    	cin>>NSpot;
    	totalPerson = 0;
    	initPosSpot();
    	rs = ~(1<<31);
    	for(int i=1;i<=3;i++){
    		markGate[i] = 0;
    		cin>>gate[i].toado;
		}
		for(int i=1;i<=3;i++){
			cin>>gate[i].numPerson;
			totalPerson+=gate[i].numPerson;
		}
		backtrack(1,0,0,0);
		cout<<rs;
	}
	return 0;
}

There are N spots for fishing in the fishing center.
The center has 3 gates, and a number of customers standing before each gate.
 
To avoid disorder, the customers must enter the center follow these rules :
 1. Only one Gate is open at a time, and it will be closed after all customers of that gate entered.
 2. When open a gate, the customers stand before that gate will enter one by one, and go to the closest & empty spot from their position.
	- The distance from a gate to the spot right above it is 1m
	- Whenever a customer goes further one spot (to left or right), it takes additionally 1m further.
	- Ex : The distance from Gate 1 to spot 4 is 1m, and to spot 3, 5 is 2m
 3. If there are 2 two spots that closest to a customer, he can choose any one of them (you should consider this case)
4. After all customers enter the gate, choose the next gate to open and proceed same as above

You should find a way so that the sum of the moving distance of all customers is minimum and print out that sum.
Ex) In above figure :
- The number of fishing spots : 10
- Gate 1 : location is 4, number of waiting customer is 5
- Gate 2 : location is 6, number of waiting customer is 2
- Gate 3 : location is 10, number of waiting customer is 2

Case 1) We open the gate by the order : Gate 1 > Gate 2 > Gate 3
 
 
 
For this case, the sum of moving distance is : 3+2+1+2+3+2+3+2+1 = 19

Case 2) We open the gate by the order : Gate 2 > Gate 1 > Gate 3
When open Gate 3, the 1st customer will go to spot 6, the second one can go to spot 5 or 7
 OR  
Case 2-1)
 
In this case, the sum is : 4+3+2+1+2+1+4+2+1 = 20

Case 2-2)
 
In this case, the sum is : 4+3+2+1+2+1+2+2+1 = 18

[Input]
- The first line given the number of test case T (T <= 50)
- For each test case:
	+ The first line given the number of spots N (10 <= N <= 60)
	+ The next three lines give the information of 3 gates :
		> Gate's position P ( 1 <= P <= N)
		> The number of customers standing before that gate C ( 1 <= C <= 20 )

[Output]
The minimum moving distance of all customers
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339