2020년 4분기

백준 1726 - 로봇 

 

#include<cstdlib>
#include <iostream>
#include <vector>
#include <queue>

//#define _CRTDBG_MAP_ALLOC
//#include <stdlib.h>
//#include <crtdbg.h>

using namespace std;
// Priority Queue 저장용
class Node
{
public:
	int x, y, dir, score;
	Node(int x, int y, int dir, int score) : x{ x }, y{ y }, dir{ dir }, score{ score } {}
	Node() = default;
};

// Node 비교용
class CompareNode
{
public:
	bool operator() (Node a, Node b)
	{
		return a.score > b.score;
	}
};

// 하나의 칸을 동서남북으로 나누는 용도
class Cell
{
public:

	int * scoreByDirs = nullptr; // 동서남북 0123
	Cell() = default;

	// 길인 경우에만 동서남북 메모리 할당
	void SetPath(bool isPath)
	{
		m_isPath = isPath;
		if (m_isPath)
		{
			scoreByDirs = new int[4];
			for (int i = 0; i < 4; ++i)
				scoreByDirs[i] = -1;
		}
	}
	bool IsPath()
	{
		return m_isPath;
	}
	~Cell()
	{
		if (scoreByDirs != nullptr)
		{
			delete[] scoreByDirs;
			scoreByDirs = nullptr;
		}
	}
private:
	bool m_isPath;
};

class RobotSolver
{
public:
	RobotSolver() = default;
	~RobotSolver()
	{
		freeMap();
	}
	int Solve()
	{
		readInput();
		aStar();
		freeMap();
		return answer;
	}
private:
	Cell ** map = nullptr;
	int W, H, startX, startY, startDir, endX, endY, endDir;
	int answer = 0;

	void readInput()
	{
		cin >> H >> W;

		map = new Cell *[H];
		int pathInfo;
		for (int i = 0; i < H; ++i)
		{
			map[i] = new Cell[W];
			for (int j = 0; j < W; ++j)
			{
				cin >> pathInfo;
				map[i][j].SetPath(pathInfo == 0);
			}
		}
		cin >> startY >> startX >> startDir >> endY >> endX >> endDir;

		// 0부터 시작하는 인덱스로 맞춰줌
		--startX;
		--startY;
		--startDir;
		--endX;
		--endY;
		--endDir;
		answer = 0;
		map[startY][startX].scoreByDirs[startDir] = 0;
	}

	//휴리스틱 점수를 반환 => 멘하튼 거리 반환
	//백준은 통과하는데 안되는 테스트 케이스가 있어서 0반환
	int getHeuristic(int x, int y)
	{
		return 0;
		//return (abs(endX - x) + abs(endY - y))/3;
	}

	int abs(int val)
	{
		return	val > 0 ? val : -val;
	}

	//메모리 해제
	void freeMap()
	{
		if (map != nullptr)
		{
			for (int i = 0; i < H; ++i)
			{
				if (map[i] != nullptr)
					delete[] map[i];
			}
			delete[] map;
		}
		map = nullptr;
	}

	void aStar()
	{

		//Astar 안쓰면 그냥 queue로 바꿔도됨
		priority_queue<Node, vector<Node>, CompareNode> pq;
		pq.push(Node(startX, startY, startDir, 0));
		while (pq.size() > 0 && answer == 0)
		{
			Node node = pq.top();
			pq.pop();
			int dist = map[node.y][node.x].scoreByDirs[node.dir] + 1;

			//현재 방향에서 인접한 방향 넣어줌
			if (node.dir <= 1)
			{
				pushNode(&pq, node.x, node.y, 2, dist);
				pushNode(&pq, node.x, node.y, 3, dist);
			}
			else
			{
				pushNode(&pq, node.x, node.y, 0, dist);
				pushNode(&pq, node.x, node.y, 1, dist);
			}

			// 현재 방향에서 3칸까지 넣어줌 
			for (int i = 1; i <= 3; ++i)
			{
				int x = node.x;
				int y = node.y;
				switch (node.dir)
				{
				case 0:
					x += i;
					break;
				case 1:
					x -= i;
					break;
				case 2:
					y += i;
					break;
				case 3:
					y -= i;
					break;
				}

				if (x < 0 || x >= W || y < 0 || y >= H || false == map[y][x].IsPath() || answer != 0)
					break;
				pushNode(&pq, x, y, node.dir, dist);
			}
		}
	}

	void pushNode(priority_queue<Node, std::vector<Node>, CompareNode> * const pq, int x, int y, int dir, int dist)
	{
		if (x < 0 || x >= W || y < 0 || y >= H || false == map[y][x].IsPath() || answer != 0)
			return ;
		if (map[y][x].scoreByDirs[dir] != -1 && map[y][x].scoreByDirs[dir] <= dist)
			return ;

		if (x == endX && y == endY && dir == endDir)
		{
			answer = dist;
		}
		pq->push(Node(x, y, dir, dist + getHeuristic(x, y)));
		map[y][x].scoreByDirs[dir] = dist;
	}
};

int main()
{
	RobotSolver solver;
	cout << solver.Solve();
	//_CrtDumpMemoryLeaks();
	return 0;
}

 

백준 5676 - 음주 코딩 (세그먼트 트리)

#include <iostream>
#include <vector>
#include <string>
#include <memory>
using namespace std;
//세그먼트 트리용 노드
class Node
{
public:
	Node * parent = nullptr;
	std::unique_ptr<Node> left = nullptr;
	std::unique_ptr<Node> right = nullptr;
	int _start, _end, _pivot;
	int val; // -1, 0, 1 셋 중 하나임

	Node(int start, int end, vector<Node*> & leafVectors, vector<int> & X) : _start{ start }, _end{ end }
	{
		// 리프노드라면 리프리스트에 추가하고 값 초기화
		if (start == end)
		{
			leafVectors.push_back(this);
			val = X[leafVectors.size() - 1];
		}
		// 아니라면 좌우 생성하고 값 초기화	
		else
		{
			_pivot = (start + end) / 2;
			left = std::make_unique<Node>(start, _pivot, leafVectors, X);
			right = std::make_unique<Node>(_pivot + 1, end, leafVectors, X);
			left->parent = right->parent = this;
			val = left->val * right->val;
		}
	}

	int FindVal(int start, int end)
	{
		//구간 일치하면 자신의 값
		if (this->_start == start && this->_end == end)
			return this->val;
		//아니면 분배
		else
		{
			int answer = 1;

			int pivot = min(_pivot, end);
			if (start <= pivot)
				answer *= left->FindVal(start, pivot);

			pivot = max(_pivot + 1, start);
			if (pivot <= end)
				answer *= right->FindVal(pivot, end);
			return answer;
		}
	}

	int max(int a, int b)
	{
		return a > b ?  a : b;
	}

	int min(int a, int b)
	{
		return a < b ? a : b;
	}

	void changeVal(int newVal)
	{
		if (newVal > 0)
			newVal = 1;
		else if (newVal < 0)
			newVal = -1;

		//값이 똑같으면 부모로 전파하지 않아도 됨
		if (val == newVal)
			return;
		//다르다면 부모 재 계산
		else
		{
			val = newVal;
			parent->Recalc();
		}
	}

	void Recalc() 	// 자신의 값을 다시 계산함
	{
		int newVal = left->val * right->val;
		if (newVal == val)
			return;

		//값이 바뀌었다면 부모도 재계산
		else
		{
			val = newVal;
			if(parent!=nullptr)
				parent->Recalc();
		}
	}
	void PrintThis()
	{
		cout << "[" << _start << ", " << _end << "](" << val << ")";
	}
};

class SegmentTree
{
public:
	SegmentTree(vector<int> & X)
	{
		leafVectors.reserve(X.size());
		root = std::make_unique<Node>(0, X.size() - 1, leafVectors, X); //루트생성하면 알아서 초기화됨
	}

	char FindVal(int start, int end)
	{
		int val = root->FindVal(start, end);
		if (val == 0)
			return '0';
		else if (val < 0)
			return '-';
		else if (val > 0)
			return '+';

		return '?';
	}

	void ChangeLeaf(int idx, int val)
	{
		leafVectors[idx]->changeVal(val);
	}

private:
	std::unique_ptr<Node> root;
	vector<Node*> leafVectors; //change 연산을 빠르게 하기 위함.
};

class Order
{
public:
	enum OrderType
	{
		Unknown = -1,
		Change,
		Product,
		MAX,
	};
	Order() = default;
	Order(OrderType type, vector<int> && params) : _type{ type }, _params{ std::move(params) } {}

	static OrderType GetOrderType(char ch)
	{
		switch (ch)
		{
		case 'C':
			return Change;
		case 'P':
			return Product;
		default :
			return Unknown;
		}
	}

	static int GetOrderLength(OrderType type)
	{
		switch (type)
		{
		case Order::Change:
		case Order::Product:
			return 2;
		default:
			return 0;
		}
	}

	void Do(SegmentTree & seg, string & answer) const
	{
		switch (_type)
		{
		case Change:
			seg.ChangeLeaf(_params[0] - 1, _params[1]);
			break;

		case Product:
			answer += seg.FindVal(_params[0] - 1, _params[1] - 1);
			break;
			
		default:
			break;
		}
	}

private :
	OrderType _type;
	vector<int> _params;
};

int main()
{
	int N, K;

	//하나의 테스트케이스
	while (cin >> N >> K)
	{
		//수열 초기화
		vector<int> X(N);
		for (int i = 0; i < N; ++i)
		{
			int x; 
			cin >> x;
			if (x > 0)
				x = 1;
			else if (x < 0)
				x = -1;
			X[i] = x;
		}
		//세그먼트트리 만듦
		SegmentTree seg(X);

		//명령어 리스트 초기화
		vector<Order> orders;
		orders.reserve(K);
		for (int i = 0; i < K; ++i)
		{
			char type;
			cin >> type;
			Order::OrderType oType = Order::GetOrderType(type);
			int len = Order::GetOrderLength(oType);
			vector<int> params(len);
			for (int i = 0; i < len; ++i)
				cin >> params[i];
			orders.emplace_back(oType, std::move(params));
		}

		//답을 구한다
		string answer;
		answer.reserve(K);
		
		for (const auto & order : orders)
		{
			order.Do(seg, answer);
		}
		cout << answer << endl;
	}

	//_CrtDumpMemoryLeaks();
	return 0;
}

 

백준 1197 - 최소 스패닝 트리 (최소 신장 트리)

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

class Edge
{
public :
	int weight, v1, v2;

	Edge(int weight, int v1, int v2) : weight{ weight }, v1{ v1 }, v2{ v2 }
	{
	}
};

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int V, E;

	cin >> V >> E;
	
	auto comparer = [](Edge* a, Edge* b) {return a->weight > b->weight; };
	priority_queue<Edge*, vector<Edge*>, decltype(comparer)> pq(comparer);

	vector < vector<Edge*> > vertices(V+1);

	vector<Edge> edges;
	edges.reserve(E);

	int weight, v1, v2;

	for (int i = 0; i < E; ++i)
	{
		cin >> v1>>v2>>weight;
		edges.emplace_back(weight, v1, v2);
		vertices[v1].push_back(&edges[i]);
		vertices[v2].push_back(&edges[i]);
	}

	int numPushedVertices = 0;

	vector<bool> checkList(V+1);
	for (auto v : checkList)
		v = false;

	checkList[1] = true;
	++numPushedVertices;
	for (auto edge : vertices[1])
		pq.push(edge);

	int answer = 0;

	while (numPushedVertices < V)
	{
		auto edge = pq.top();
		pq.pop();

		if (true == checkList[edge->v1] &&
			true == checkList[edge->v2])
		{
			continue;
		}

		int newVertex = checkList[edge->v1] == false ? edge->v1 : edge->v2;
		checkList[newVertex] = true;
		++numPushedVertices;
		answer += edge->weight;

		for (auto e : vertices[newVertex])
			pq.push(e);
	}

	cout << answer;

	return 0;
}

 

백준 2805 - 나무 자르기 (이분 탐색) .

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	vector<int> trees(N);

	for (int i = 0; i < N; ++i)
		cin >> trees[i];

	sort(trees.begin(), trees.end(), greater<int>()); // 내림차순으로 정렬

	int low, high, mid;
	low = 0;
	high = trees[0] - 1;
	int answer = 0;
	while (true)
	{
		mid = (high + low) / 2 + (high+low)%2;
		long long sum = 0;
		for (int i = 0; i < N; ++i)
		{
			if (mid < trees[i])
				sum += trees[i] - mid;
			else
				break;
		}
		if (sum == M)
		{
			answer = mid;
			break;
		}

		if (sum > M)
		{
			low = mid + 1;
			if (mid > answer)
				answer = mid;
		}
			
		else
			high = mid - 1;
		if (low > high)
		{
			mid = low;
			break;
		}

	}
	cout << answer;

	return 0;
}

 

백준 1987 - 알파벳 (백트래킹)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class BackTracker
{
private :
	vector<bool> currentAlphabet; //밟은? 알파벳 검사용
	bool ** visited = nullptr;
	int ** map = nullptr;
	int H, W;
	int answer;

	void Visit(int y, int x, int length) //DFS로 방문
	{
		if (false == IsValid(y, x))
			return;

		length++;
		if (answer < length)
			answer = length;

		visited[y][x] = true;
		currentAlphabet[map[y][x]] = true;

		for (int i = 0; i < 4; ++i)
			Visit(y + DIRS[i][0], x + DIRS[i][1], length);

		visited[y][x] = false;
		currentAlphabet[map[y][x]] = false;
	}

	bool IsValid(int y, int x) //경계, 이미 방문했는지, 알파벳 겹치는지 체크
	{
		if (y < 0 || x < 0 || y >= H || x >= W)
			return false;
		if (true == visited[y][x])
			return false;
		if (true == currentAlphabet[map[y][x]])
			return false;

		return true;
	}

public :
	const int DIRS[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };

	BackTracker()
	{
		currentAlphabet.assign(26, false);
	}
	~BackTracker()
	{
		if (visited != nullptr)
		{
			for (int i = 0; i < H; ++i)
			{
				delete[] visited[i];
				delete[] map[i];
			}
			delete[] visited;
			delete[] map;
		}
	}
	
	BackTracker * Read() // 인풋 읽음
	{
		int R, C;
		cin >> R >> C;
		this->H = R;
		this->W = C;

		visited = new bool *[R];
		map = new int *[R];
		for (int i = 0; i < R; ++i)
		{
			visited[i] = new bool[C];
			map[i] = new int[C];

			for (int j = 0; j < C; ++j)
			{
				char alphabet;
				cin >> alphabet;
				visited[i][j] = false;
				map[i][j] = alphabet - 'A';
			}
		}

		return this;
	}

	int Solve() // 풀기
	{
		this->answer = 0;
		Visit(0, 0, 0);
		return this->answer;
	}
};

int main()
{
	BackTracker solver;
	cout << solver.Read()->Solve() << endl;
	return 0;
}

 

백준 8986 - 전봇대 (삼분 탐색)

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

ll GetSum(ll dist, const vector<int> * const poles)
{
	ll sum = 0;
	for (int i = 0; i < poles->size(); ++i)
	{
		ll diff = dist * i - (ll)(*poles)[i];
		sum += diff > 0 ? diff : -diff;
	}
	return sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;

	cin >> N;

	vector<int> poles;
	poles.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> poles[i];

	int low, high, p1, p2; //거리
	low = 0;
	high = poles[N - 1];

	//while(3 <= high - low) //......... 이걸로하면 왜 86%에서 안됨...??????????
	while (low + 3 <= high)
	{
		p1 = (low * 2 + high) / 3;
		p2 = (low + high * 2) / 3;

		if (GetSum(p1, &poles) < GetSum(p2, &poles)) //각각 오른쪽, 왼쪽 제거
			high = p2;
		else
			low = p1;
	}

	ll answer = GetSum(low, &poles);
	for (int i = low; i <= high; ++i)
	{
		auto sum = GetSum(i, &poles);
		if (sum < answer)
			answer = sum;
	}
	cout << answer;
	return 0;
}

 

백준 1194 - 달이 차오른다, 가자. .

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ushort = unsigned short;

struct Node
{
	int y, x, dist;
	ushort key;

	Node(int y, int x, int dist, ushort key) : y{ y }, x{ x }, dist{ dist }, key{ key }
	{

	}
};


int N, M;
vector <vector<char>> maps;
vector < vector<vector<bool>>> visited;

int startX, startY;


int dirs[4][2] { {0,1},{0,-1},{-1,0},{1,0} }; // 동서남북
int answer = -1;

bool canOpen(ushort key, char door)
{
	ushort doorKey = 1 << (door - 'A');
	return (key & doorKey) > 0;
}

ushort AddKey(ushort old, char key)
{
	ushort newKey = 1 << (key - 'a');
	return old | newKey;
}

//return : 답 찾았는지 여부
bool Visit(Node node, queue<Node> & visitQ)
{
	if (node.y < 0 || node.x < 0 || node.y >= N || node.x >= M || maps[node.y][node.x] == '#' || visited[node.y][node.x][node.key] == true) //못가는 곳
		return false;

	char val = maps[node.y][node.x];

	if ('a' <= val && val <= 'f') // 열쇠를 찾음
	{
		visited[node.y][node.x][node.key] = true;
		ushort key = AddKey(node.key, val);
		for (int i = 0; i < 4; ++i) // 동서남북 방문
			visitQ.emplace(node.y + dirs[i][0], node.x + dirs[i][1], node.dist + 1, key);
	}
	else if ('A' <= val && val <= 'F') // 문을 만남
	{  
		if (canOpen(node.key, val))
		{
			visited[node.y][node.x][node.key] = true;
			for (int i = 0; i < 4; ++i) // 동서남북 방문
				visitQ.emplace(node.y + dirs[i][0], node.x + dirs[i][1], node.dist + 1, node.key);
		}
	}
	else if (val == '1') // 목표를 찾음
	{
		answer = node.dist;
		return true;
	}
	else // 그 외 ( '.' 이랑 '0' )
	{
		visited[node.y][node.x][node.key] = true;
		for (int i = 0; i < 4; ++i) // 동서남북 방문
			visitQ.emplace(node.y + dirs[i][0], node.x + dirs[i][1], node.dist + 1, node.key);
	}
	return false;
		
}

void read()
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		maps.emplace_back();
		visited.emplace_back();
		maps[i].resize(M);
		visited[i].resize(M);
		for (int j = 0; j < M; ++j)
		{
			cin >> maps[i][j];
			if (maps[i][j] == '0')
			{
				startX = j;
				startY = i;
			}
			visited[i][j].resize(1 << 6, false);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	queue<Node> visitQ;
	visitQ.emplace(startY, startX, 0, 0);
	while (false == visitQ.empty())
	{
		auto node = visitQ.front();
		visitQ.pop();
		if (Visit(node, visitQ))
			break;
	}

	cout << answer;
	return 0;
}

 

백준 6549 - 히스토그램에서 가장 큰 직사각형 (슬라이딩 윈도우)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

vector<int>* ReadTestCase()
{
	int n;
	cin >> n;

	if (n == 0)
		return nullptr;

	auto testCase = new vector<int>(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> (*testCase)[i];
	
	return testCase;
}

long long solve(vector<int> * pTestCase)
{
	stack<int> stack;
	stack.push(0);
	long long answer = 0;
	for (int i = 1; i < pTestCase->size(); ++i)
	{
		auto val = (*pTestCase)[i];

		{
			auto top = stack.top();
			long long topVal = (*pTestCase)[top];

			while (val < topVal)
			{
				stack.pop();
				int start = stack.empty() ? -1 : stack.top();
				int end = i - 1;

				answer = max(answer, (end - start) * topVal);

				if (stack.empty())
					break;

				top = stack.top();
				topVal = (*pTestCase)[top];
			}
		}

		if (false == stack.empty() &&
			val == (*pTestCase)[stack.top()])
			stack.pop();

		stack.push(i);
	}
	int end = stack.top();
	while (false == stack.empty())
	{
		int top = stack.top();
		long long topVal = (*pTestCase)[top];
		stack.pop();

		int start = stack.empty() ? -1 : stack.top();

		answer = max(answer, (end - start) * topVal);
	}

	return answer;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (true)
	{
		auto testCase = ReadTestCase();
		if (testCase == nullptr)
			break;

		cout << solve(testCase) << endl;
	}

	return 0;
}

 

백준 2457 - 공주님의 정원 (그리디)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int TOTALDAY = 275; // 3월 1일부터 11월 30일까지의 날짜

using ushort = unsigned short;
/*
날짜(int) : 3월 1일부터 몇 번째 날짜인지. (3월 1일은 0, 4월 1일은 31)
*/
struct Flower
{
	ushort start, end; //개화 날짜, 지는 날짜

	Flower(ushort start, ushort end) : start{ start }, end{ end }
	{
	}

	static bool Compare(Flower a, Flower b)
	{
		return a.start < b.start;
	}
};


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<Flower> flowers;
	flowers.reserve(N);


	////////////////////////////////////////////////////////////
	// greedy. 꽃이 핀 시기를 시작순으로 정렬한다. 시작점부터 제일 많이 커버할 수 있는 애를 고르고, 시작점을 커버한 만큼 옮김. 반복
	
	////////////////////////////////////////////////////////////
	// 1. 꽃 리스트 읽어서 시작 날짜 순으로 정렬

	{
		int days[10]{ 31,30,31,30,31,31,30,31,30 }; //3월~11월까지의 날짜들
		int accumDays[9]; //3월 1일부터 (N + 3)월 1일은 며칠이나 지났는지
		accumDays[0] = 0;
		for (int i = 1; i < 9; ++i)
			accumDays[i] = accumDays[i - 1] + days[i - 1];

		ushort startMonth, startDay, endMonth, endDay;
		ushort start, end;
		for (int i = 0; i < N; ++i)
		{
			cin >> startMonth >> startDay >> endMonth >> endDay;

			if (startMonth > 11 || endMonth < 3)
			{
				flowers.emplace_back(0, 0);
			}
			else
			{
				// 3월 이전 => 3월 1일에 피는걸로
				if (startMonth < 3)
					start = 0;
				else
					start = accumDays[startMonth - 3] + startDay - 1;

				//12월 넘음 => 12월 1일에 지는걸로
				if (endMonth > 11)
					end = TOTALDAY;
				else
					end = accumDays[endMonth - 3] + endDay - 1;

				flowers.emplace_back(start, end);
			}
		}

		std::sort(flowers.begin(), flowers.end(), Flower::Compare);
	}

	////////////////////////////////////////////////////////////
	// 2. 시작점부터 제일 많이 커버하는애를 찾는다. 시작점을 커버하지 못하는 애가 나온다면 가장 많이 커버하는애를 고르고 시작점을 옮긴다.

	int answer = 0;
	ushort coveredDays = 0;
	ushort startDay = 0;

	for (int i = 0; i < N; ++i)
	{
		if (flowers[i].start > startDay)
		{
			startDay = coveredDays;
			answer++;
		}
		if (flowers[i].start <= startDay)
		{
			coveredDays = max(coveredDays, flowers[i].end);

			//다 커버했음 => 답 찾음
			if (coveredDays >= TOTALDAY)
			{
				answer++;
				break;
			}
		}

		//중간에 구멍있음
		else
			break;
	}
	if (coveredDays >= TOTALDAY)
		cout << answer;
	else
		cout << 0;

	return 0;
}