Untitled
unknown
plain_text
a year ago
2.6 kB
8
Indexable
Never
#include <iostream> #include <stdio.h> using namespace std; int T, n; int ad[3][2], as[3][2], visit[1000], timet[1000], xep[3]; int visit_hv[3] = {0,0,0}, con[3]; int kq, people; void reset() { for(int i = 0; i < n; i ++) { timet[i] = 0; visit[i] = 0; } } int abs(int a) { if (a < 0) a = -a; else a = a; return a; } int dkb(int i) { if(i >= 0 && i < n) return 1; return 0; } int sumt() { int sum = 0; for(int i = 0; i < n; i ++) { sum += timet[i]; } return sum; } void cost() { int k, h, sav=0, nguoi, t; for(int i = 0; i < 3; i ++) { if(con[i] == 0) k = -1; else k = 1; h = 1; t = 1; nguoi = as[i][1]; int mid = as[i][0]-1; sav = mid; if(visit[sav] == 0 && dkb(sav)) { visit[sav] = i+1; timet[sav] = 1; nguoi--; } while(nguoi > 0) { if(visit[sav + k*h]==0 && dkb(sav + k*h)) { visit[sav + k*h]=i+1; timet[sav+ k*h] = abs(k*h) + 1; nguoi --; } if(k == -1) k = 1; else k = -1; if(k == -1 && con[i] == 0) h ++; else if(k == 1 && con[i] == 1) h++; } } } void tapcon(int ket) { if(ket == 3) { reset(); cost(); if(kq > sumt()) kq = sumt(); //for(int i = 0; i < 3; i ++) cout << con[i] << " "; //cout << endl; //for(int i = 0; i < n; i ++) cout << visit[i] << " "; //cout << endl; //cout << kq << endl; return; } for(int i = 0; i < 2; i ++) { con[ket] = i; tapcon(ket+1); con[ket] = 0; } } void hoanvi(int ket) { if(ket == 3) { for(int i = 0; i < 3; i++) { int j = xep[i]; as[i][0] = ad[j][0]; as[i][1] = ad[j][1]; } //for(int i = 0; i < 3; i ++) cout << xep[i] << " "; //cout << endl << endl; tapcon(0); return; } for(int i = 0; i < 3; i++) { if(visit_hv[i] == 0) { visit_hv[i] = 1; xep[ket] = i; hoanvi(ket+1); visit_hv[i] = 0; } } } int main() { freopen("input.txt", "r", stdin); cin >> T; for (int stt = 1; stt <= T; stt++) { people = 0; cin >> n; for(int i = 0; i < 3; i ++) { cin >> ad[i][0] >> ad[i][1]; people += ad[i][1]; visit_hv[i] = 0; con[i] = 0; } kq = 100000; reset(); hoanvi(0); //con[0] = 0; con[1] = 1; con[2] = 0; //as[0][0] = ad[0][0]; as[0][1] = ad[0][1]; //as[1][0] = ad[2][0]; as[1][1] = ad[2][1]; //as[2][0] = ad[1][0]; as[2][1] = ad[1][1]; // //cost(); //for(int i = 0; i < n; i ++) cout << timet[i] << " "; //cout << endl; //for(int i = 0; i < n; i ++) cout << visit[i] << " "; cout << "Case #" << stt << endl << kq << endl; } return 0; }