gomin.cpp

#include <iostream>
#include <fstream>
#include <vector>
#import <cstdlib> // khai báo để tí nữa dùng hàm abs


using namespace std;

ifstream fi ("/Users/toan/ued/18-10-2018/GOMIN.INP");
ofstream fo ("/Users/toan/ued/18-10-2018/GOMIN.OUT");

int n,t;
int x; // toa do cac n qua min
int k; // toa do qua min hen gio


struct Node
{
	vector<int> v; // mảng gồm các index toạ độ đường 
	long long length;
};

Node node;

vector<int> v; // mảng gồm các toạ độ của các quả mìn.
vector<int> startPointArr; // mảng gồm các điểm đầu
vector<Node> nodes;

/**
Tinh toan do dai 2 diem x1 -> x2
*/
int calculatePointLength(int x1, int x2){

	x1 = abs(x1);
	x2 = abs(x2);

	if(x1 > x2){
		return x1 - x2;
	}

	return x2 - x1;

}


void display(){
	for (int i = 0; i < nodes.size(); ++i){
			
			for (int j = 0; j < nodes[i].v.size(); ++j){
				cout << v[nodes[i].v[j]] << " ";
			}
			cout << " length:" << nodes[i].length;
			cout << endl;
	}
}

/*
* Liệt kê các đường đi
*/

void list(){

	int totalTime = 0;
	int timerBoomIndex = k -1;
	vector<int> pointArr; // ta chỉ lưu gia trị index


	// copy vector
	for (int i = 0; i < v.size(); ++i){
		pointArr.push_back(v[i]);
	}


	bool resolveTimerBoom = false;
	int lastPointIndex = -1;
	bool isGoingleft = true;

	for (int i = 0; i < startPointArr.size(); ++i){
		node.v.clear();
		node.length = 0;
		node.v.push_back(startPointArr[i]);

		//neu điểm đầu mà trùng với vị trí bom hẹn giờ thì ta đánh dấu là đã gỡ xong quả hẹn giờ, và chỉ việc gỡ quả khác
		if(timerBoomIndex == startPointArr[i]){
			resolveTimerBoom = true;
		}

		// ta đi về bên trái trước
		lastPointIndex = startPointArr[i];
		for (int j = startPointArr[i]; j >= 0; --j){

			/**
			vừa đi lại vừa kiểm tra nếu thời gian quay lại mà lơn hơn t thì bỏ điểm vừa đến
			*/

			int pointLength = calculatePointLength(v[lastPointIndex], v[j]);

			if((node.length + pointLength) * 2  >= t && !resolveTimerBoom){
				// không ổn, vì khi quay lại sẽ ko còn thời gian nữa, tèo rồi :D
				// tot nhat la nen quay lai

				// ta lại đổi hướng sang phải
				isGoingleft = false;

				break;
			}

			// them vi trí điểm vào mảng 
			if(pointLength > 0){
				// đồng thời tính luôn độ dài
				node.v.push_back(j);
				node.length += pointLength;

				// danh dấu là đã gỡ
				pointArr[j] = -1;

			}

			lastPointIndex = j;
		}

		// ta di ve phia ben phai 
		for (int j = lastPointIndex; j < pointArr[i]; ++j){
			/* code */
		}

		// them vao nodes
		nodes.push_back(node);

		node.v.clear();
		node.length = 0;

	}


	display();
}

int main(){

	fi >> n >> t;

	for (int i = 0; i < n; ++i){
		fi >> x;
		v.push_back(x);
	}

	fi >> k;

	// ta tim cac duong di , sao cho chon vi tri bat dau den vi tri hen gio thoa man
	// roi sau do tinh tong do dai, chon cai nao co do dai be nhat thi lay

	for (int i = 0; i < v.size(); ++i){
		/* ta liet ke tat ca cac diem bat dau thoa man yeu cau, 
		sao cho khi cham vao qua min dau tien
		thi doan noi diem bat dau toi qua min hen gio toa do k, 
		se co độ dài < t(thơi gian quả mình hẹn giờ sẽ nổ);
		*/

		// k là vị trí đếm của của mìn hẹn giờ, tuy nhiên thứ tự trong mảng sẽ là k-1
		if(calculatePointLength(v[i], v[k-1]) < t){
			/* nếu độ dài 2 điểm < thời gian quả bom hẹn giờ nổ thì thoả mãn. 
			(vì thời gian hẹn giờ bằng khoảng cách di chuyển)
			*/

			startPointArr.push_back(i);
		}
	}
	// vậy ta đã có được các điểm bắt đầu cho đường đi gỡ mìn.

	/*
	Ta đi liệt kê các đường đi tới quả mìn hẹn giờ, có thể đi sang trái hoặc phải:
	+ nếu start point index < (k -1 ) điểm đầu < điểm cần đến, nên ta đi về phía phải
	+ nếu bằng thì điểm bắt đầu trùng với toạ độ quả mìn hẹn giờ 
	+ còn lại index > (k - 1) : ta đi về phia bên trái
	*/

	list();


	return 0;
}