HugoXepHinh

 avatar
ptrdung
plain_text
a year ago
4.3 kB
4
Indexable
#include <iostream>
using namespace std;
typedef long long ll;


const int CAPACITY = 1e6, inf = 1e7, MAX = 101, CANT = -1;
template<typename T> class MyDeque{
private:
    T arr[CAPACITY];
    int frontId, backId;
    int addOne(int num){
        num ++;
        if (num >= CAPACITY){
            num = 0;
        }
        return num;
    }
    int minusOne(int num){
        num --;
        if (num < 0){
            num = CAPACITY-1;
        }
        return num;
    }
public:
	void clean(){
        frontId = 1;
        backId = 0;
    }
	MyDeque(){
        frontId = 1;
        backId = 0;
    }
    T back(){
        return arr[backId];
    }
    T front(){
        return arr[frontId];
    }
    void push_front(T val){
        frontId = minusOne(frontId);
        arr[frontId] = val;
    }
    void push_back(T val){
        backId = addOne(backId);
        arr[backId] = val;
    }
    void pop_back(){
        if (size()) {
            backId = minusOne(backId);
        }
    }
    void pop_front(){
        if (size()){
            frontId = addOne(frontId);
        }
    }
    bool isEmpty(){
        return size() == 0;
    }
    int size(){
        return ((backId - frontId + 1) + CAPACITY) % CAPACITY;
    }
};

ll n, res;
int pos[4], cntPeople[4];
int order[4];
int saveId[MAX];

void input(){
	cin >> n;
	for (int i=1; i<=3; i++){
		cin >> pos[i] >> cntPeople[i];
	}
}

void resetData(){
	res = inf;
}

bool checkInBoard(int id){
	return id>0 && id<=n;
}

void resetSaveId(){
	for (int i=0; i<=n; i++){
		saveId[i] = 0;
	}
}

int _abs(int a){
	return a>0 ? a : -a;
}

void checkResult(){
	int sum = 0;
	for (int i=0; i<=n; i++){
		if (saveId[i] != 0){
			sum ++;
			sum += _abs(pos[saveId[i]] - i);
		}
	}

	//for (int i=0; i<=n; i++){
	//	cout << saveId[i] << " ";
	//}
	//cout << endl << sum << endl;
	if (sum < res){
		cout << saveId[26] << " " << saveId[27] << " " << saveId[28] << endl; 
		res = sum;
	}
}



void Try(int idOrder, int left, int right, int cnt){
	if (idOrder>3){
		checkResult();
		return;
	}
	// order[idOrder]]: id cua
	if (cnt >= cntPeople[order[idOrder]]){
		return Try(idOrder+1, pos[order[idOrder+1]], pos[order[idOrder+1]], 0);	
	}

	while (checkInBoard(left) && saveId[left]!=0) {
		left--;
	}
	while (checkInBoard(right) && saveId[right]!=0) {
		right++;
	}

	if (checkInBoard(left) && checkInBoard(right)){
		int root = pos[order[idOrder]];
		if (_abs(left - root) < _abs(right - root) ){
			saveId[left] = order[idOrder];
			Try(idOrder, left, right, cnt+1);
			saveId[left] = 0;
		}
		else if (_abs(left - root) > _abs(right - root) ){
			saveId[right] = order[idOrder];
			Try(idOrder, left, right, cnt+1);	
			saveId[right] = 0;
		}
		else {
				// ====================== cat tia
			if (left!=right && cntPeople[order[idOrder]] - cnt > 2){
				saveId[right] = saveId[left] = order[idOrder];
				Try(idOrder, left, right, cnt+2);
				
				saveId[right] = saveId[left] = 0;
			}
			else {
				// =======================
				saveId[right] = order[idOrder];
				Try(idOrder, left, right, cnt+1);	
				saveId[right] = 0;

				saveId[left] = order[idOrder];
				Try(idOrder, left, right, cnt+1);
				saveId[left] = 0;
			}
		}
	}
	else {
		if (checkInBoard(left)){
			saveId[left] = order[idOrder];
			Try(idOrder, left, right, cnt+1);
			saveId[left] = 0;
		}
		else {
			saveId[right] = order[idOrder];
			Try(idOrder, left, right, cnt+1);	
			saveId[right] = 0;
		}
	}

}

void gen3HoanVi(int step){
	if (step == 4){
		//solve
		resetSaveId();
		Try(1, pos[order[1]], pos[order[1]], 0);
		return;
	}
	for (int i=1; i<=3; i++){
		bool check = true;
		for (int j=step-1; j>0; j--){
			if (order[j] == i){
				check = false;
			}
		}
		if (check ){
			order[step] = i;
			gen3HoanVi(step+1);
		}
	}
}


void solve() {
	resetData();
	input();
	gen3HoanVi(1);
}

int main() {
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	freopen("input.txt", "r", stdin);
	int test;
	cin >> test;
	for (int i=1; i<=test; i++) {
		solve();
		cout << "Case #" << i << "\n" << res << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment