HugoXepHinh
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