// TEMA 2 TAP.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

// aici incepe problema 1

struct nod {
	string valoareCitita;
	nod * fiuStanga;
	nod * fiuDreapta;
	int numar = 0;
};

bool esteArboreDeCautare(nod * parinte, int &prev) {
	string valoareCititaTastatura;
	cin >> valoareCititaTastatura;
	if (valoareCititaTastatura != "null") {
		nod* fiuStanga = new nod;
		fiuStanga->numar = atoi(valoareCititaTastatura.c_str()); //converteste string in numar
		parinte->fiuStanga = fiuStanga;

		if (!esteArboreDeCautare(fiuStanga,prev))
			return false;
	}
	if (prev > parinte->numar)
		return false;

	prev = parinte->numar;

	cin >> valoareCititaTastatura;
	if (valoareCititaTastatura != "null") {
		nod* fiuDreapta = new nod;
		fiuDreapta->numar = atoi(valoareCititaTastatura.c_str()); //converteste string in numar
		parinte->fiuDreapta = fiuDreapta;

		return esteArboreDeCautare(fiuDreapta, prev);
	}
	return true;
}

void verificareArboreBinarCautare() {
	string valoareCititaTastatura;
	cin >> valoareCititaTastatura;
	if (valoareCititaTastatura == "null") {
		cout << "Arborele este null\n";
		return;
	}
	nod * radacina = new nod;
	radacina->valoareCitita = valoareCititaTastatura;
	radacina->numar = atoi(valoareCititaTastatura.c_str()); //converteste string in numar

	int prev=INT_MIN;
	if (esteArboreDeCautare(radacina, prev))
		cout << "da\n";
	else
		cout << "nu\n";
}

// aici incepe problema 2

struct Gaura {
	int i, j;
	Gaura(int setI=0, int setJ=0) : i(setI), j(setJ) {}
};

void acopera(int sus, int st, int latura, Gaura gauraCurenta, int & contorPiesa, vector <vector <int > > & tabla, int n) {
	//conditia pentru terminare (latura <= 2) e trecuta in fiecare caz
	//practic nu se mai reapeleaza, piesa adaugata acoperind in totalitate tabla de lungime 2

	int laturaNoua = latura >> 1; // latura / 2

	if ((gauraCurenta.i - sus) < laturaNoua) {
		//gaura este in jumatatea superioara
		if (gauraCurenta.j - st < laturaNoua) {
			//gaura este in jumatatea stanga
			//gaura este in contul stanga sus
			Gaura g1, g2, g3;
			g1.i = sus + laturaNoua;		g1.j = st + laturaNoua - 1;
			g2.i = sus + laturaNoua;		g2.j = st + laturaNoua;
			g3.i = sus + laturaNoua - 1;	g3.j = st + laturaNoua;

			tabla[g1.i][g1.j] += contorPiesa;
			tabla[g2.i][g2.j] += contorPiesa;
			tabla[g3.i][g3.j] += contorPiesa;
			++contorPiesa;

			/*for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n;++j)
			cout << setw(3) << tabla[i][j] << " ";
			cout << "\n";
			}
			cout << "\n";*/

			if (latura == 2)
				return;

			acopera(sus,				st,					laturaNoua, gauraCurenta,	contorPiesa, tabla,	n);
			acopera(sus + laturaNoua,	st,					laturaNoua,	g1,	contorPiesa, tabla, n);
			acopera(sus + laturaNoua,	st + laturaNoua,	laturaNoua, g2,	contorPiesa, tabla, n);
			acopera(sus,				st + laturaNoua,	laturaNoua, g3,	contorPiesa, tabla, n);

		}
		else {
			//gaura este in jumatatea dreapta
			//gaura este in contul dreapta sus
			Gaura g1, g2, g3;
			g1.i = sus + laturaNoua;		g1.j = st + laturaNoua - 1;
			g2.i = sus + laturaNoua;		g2.j = st + laturaNoua;
			g3.i = sus + laturaNoua - 1;	g3.j = st + laturaNoua - 1;

			tabla[g1.i][g1.j] += contorPiesa;
			tabla[g2.i][g2.j] += contorPiesa;
			tabla[g3.i][g3.j] += contorPiesa;
			++contorPiesa;

			/*for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n;++j)
			cout << setw(3) << tabla[i][j] << " ";
			cout << "\n";
			}
			cout << "\n";*/

			if (latura == 2)
				return;

			acopera(sus,				st + laturaNoua,	laturaNoua, gauraCurenta, contorPiesa, tabla, n);
			acopera(sus + laturaNoua,	st,					laturaNoua, g1, contorPiesa, tabla, n);
			acopera(sus + laturaNoua,	st + laturaNoua,	laturaNoua, g2, contorPiesa, tabla, n);
			acopera(sus,				st,					laturaNoua, g3, contorPiesa, tabla, n);
		}
	}
	else {
		//gaura este in jumatatea inferioara
		if (gauraCurenta.j - st < laturaNoua) {
			//gaura este in jumatatea stanga
			//gaura este in contul stanga jos
			Gaura g1, g2, g3;
			g1.i = sus + laturaNoua - 1;	g1.j = st + laturaNoua - 1;
			g2.i = sus + laturaNoua;		g2.j = st + laturaNoua;
			g3.i = sus + laturaNoua - 1;	g3.j = st + laturaNoua;

			tabla[g1.i][g1.j] += contorPiesa;
			tabla[g2.i][g2.j] += contorPiesa;
			tabla[g3.i][g3.j] += contorPiesa;
			++contorPiesa;

			/*for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n;++j)
			cout << setw(3) << tabla[i][j] << " ";
			cout << "\n";
			}
			cout << "\n";*/

			if (latura == 2)
				return;

			acopera(sus + laturaNoua,		st,					laturaNoua,		gauraCurenta, contorPiesa, tabla, n);
			acopera(sus,					st,					laturaNoua,		g1, contorPiesa, tabla, n);
			acopera(sus + laturaNoua,		st + laturaNoua,	laturaNoua,		g2, contorPiesa, tabla, n);
			acopera(sus,					st + laturaNoua,	laturaNoua,		g3, contorPiesa, tabla, n);
		}
		else {
			//gaura este in jumatatea dreapta
			//gaura este in contul dreapta jos
			Gaura g1, g2, g3;
			g1.i = sus + laturaNoua - 1;	g1.j = st + laturaNoua - 1;
			g2.i = sus + laturaNoua;		g2.j = st + laturaNoua - 1;
			g3.i = sus + laturaNoua - 1;	g3.j = st + laturaNoua;

			tabla[g1.i][g1.j] += contorPiesa;
			tabla[g2.i][g2.j] += contorPiesa;
			tabla[g3.i][g3.j] += contorPiesa;
			++contorPiesa;

			/*for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n;++j)
					cout << setw(3) << tabla[i][j] << " ";
				cout << "\n";
			}
			cout << "\n";*/

			if (latura == 2)
				return;

			acopera(sus + laturaNoua,	st + laturaNoua,	laturaNoua, gauraCurenta, contorPiesa, tabla, n);
			acopera(sus,				st,					laturaNoua, g1, contorPiesa, tabla, n);
			acopera(sus + laturaNoua,	st,					laturaNoua, g2, contorPiesa, tabla, n);
			acopera(sus,				st + laturaNoua,	laturaNoua, g3, contorPiesa, tabla, n);
		}
	}
}

void jocGasireGaura() {
	int putere;
	cin >> putere;

	int n = 1 << putere; //2 ^ putere

	Gaura gauraInitiala;

	cin >> gauraInitiala.i;
	cin >> gauraInitiala.j;

	vector < vector <int> > tabla;
	for (int i = 0; i <= n; ++i) {
		vector <int> nouVector(n + 1, 1);
		tabla.push_back(nouVector);
	}

	tabla[gauraInitiala.i][gauraInitiala.j] = 0;

	int contorPiesa = 0;

	acopera(1, 1, n, gauraInitiala, contorPiesa, tabla, n);

	cout << "Final\n";
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n;++j)
			cout << setw(3) << tabla[i][j] << " ";
		cout << "\n";
	}
	cout << "\n";
}

// aici incepe problema 3

struct elementPonderat {
	static double pondereTotala;
	int numar=0;
	double pondere=0;
};

double elementPonderat::pondereTotala = 0;

//gaseste al k-lea element din vectorul sortat in timp liniar worst case
//
int alKleaEl(vector <elementPonderat> &v, int st, int dr, int pozCautataK) {
	if (st==dr)
		return v[st].numar;

	//impartim vectorul nostru in grupuri de cate 5 si gasim cate o mediana pt fiecare sortandu le
	// O(n)
	vector <elementPonderat> mediane;
	int i = st;
	while (i + 5 <= dr) {
		vector <int> grupDe5;
		for (int j = 0; j < 5; ++j) {
			grupDe5.push_back(v[i+j].numar);
		}
		sort(grupDe5.begin(), grupDe5.end()); //sortarea dureaza timp constant pt 5 elemente
		elementPonderat nouElementPonderat;
		nouElementPonderat.numar = grupDe5[2];
		mediane.push_back(nouElementPonderat);
		i += 5;
	}
	if (i <= dr) {
		//pt ultimul grup (mai mic de 5) nu conteaza pe care o luam
		elementPonderat nouElementPonderat;
		nouElementPonderat.numar = v[i].numar;
		mediane.push_back(nouElementPonderat);
	}

	//alegem pivotul aplicand gasirea medianei pe medianele grupurilor de cate 5 elemente
	int pivot = alKleaEl(mediane,0,mediane.size()-1,mediane.size()/2);

	//gasim pozitia pivotului
	for (int i = st; i<dr; i++) {
		if (v[i].numar == pivot) {
			swap(v[i], v[dr]);
			break;
		}
	}

	//aplicam partitionarea dupa pivot
	int stanga = st;
	for (int i = st; i<dr; i++) {
		if (v[i].numar < pivot) {
			swap(v[i], v[stanga++]);
		}
	}
	swap(v[stanga], v[dr]);

	//Daca pivotul nu este raspunsul apelam recursiv in stanga sau in dreapta pivotului
	if (stanga == pozCautataK) {
		return pivot;
	}
	else if (stanga > pozCautataK) {
		return alKleaEl(v, st, stanga, pozCautataK);
	}
	else {
		return alKleaEl(v, stanga+1, dr, pozCautataK);
	}
}

// T(n) = T(n/2) + O(n) -> O(n) conform Master
int pozMedPond (vector <elementPonderat> & v , int st, int dr, double pondereAuxSt) {
	if (st == dr)
		return st;

	int medianaSimpla = alKleaEl(v, st, dr, (st+dr)/2); // O(n)

	// total calcul sume O(n)
	double sumStanga = 0;
	int i;
	for (i = st; v[i].numar != medianaSimpla; ++i) {
		sumStanga += v[i].pondere;
	}
	double sumDreapta = 0;
	for (int j=i; j<=dr; ++j) {
		sumDreapta += v[j].pondere;
	}

	// Reapelul se face in O(n/2)
	if (pondereAuxSt + sumStanga >= 0.5) {
		//v[i - 1].pondere += sumDreapta+v[i].pondere; //adaugam pondere pt pastrearea problemei initiale
		return pozMedPond(v, st, i - 1, pondereAuxSt);
	}
	else {
		//v[i + 1].pondere += sumStanga + v[i].pondere; //adaugam pondere pt pastrearea problemei initiale
		return pozMedPond(v, i + 1, dr, pondereAuxSt + sumStanga + v[i].pondere);
	}
}

void medianaPonderata() {
	int n;
	cin >> n;
	vector <elementPonderat> v;
	for (int i = 0; i < n; ++i) {
		elementPonderat nouElementPonderat;
		cin >> nouElementPonderat.numar;
		v.push_back(nouElementPonderat);
	}
	for (int i = 0; i < n; ++i) {
		cin >> v[i].pondere;
		elementPonderat::pondereTotala += v[i].pondere;
	}
	int mp = pozMedPond(v, 0, v.size() - 1,0);
	cout << v[mp].numar <<"\n";
}

// aici incepe problema 4

struct punct {
	int x = 0;
	int y = 0;
};

double distEuclid(punct a, punct b) {
	double x = a.x - b.x;
	double y = a.y - b.y;
	double dist;

	dist = pow(x, 2) + pow(y, 2);           //calculating distance by euclidean formula
	dist = sqrt(dist);                  //sqrt is function in math.h

	return dist;
}

bool cmpDupaX(const punct& a, const punct& b)
{
	return a.x < b.x;
}

bool cmpDupaY(const punct& a, const punct& b)
{
	return a.y < b.y;
}


double distMinPunctePlanRec(vector <punct> & puncte, int st, int dr, vector<punct> &puncteY) {
	if (dr - st == 1) {
		return 2147483647; //int_max
	}
	if (dr - st == 2) {
		if (puncteY[st].y > puncteY[st + 1].y)
			swap(puncteY[st], puncteY[st + 1]);
		return distEuclid(puncte[0], puncte[1]);
	}

	int m = (st + dr) / 2;
	double distStanga = distMinPunctePlanRec(puncte, st, m, puncteY);
	double distDreapta = distMinPunctePlanRec(puncte, m, dr, puncteY);
	double distMinStDr = min(distStanga, distDreapta);

	//sort(puncteY.begin()+st,puncteY.begin()+dr, cmpDupaY);
	vector <punct> puncteAux(dr - st);
	merge(puncteY.begin() + st, puncteY.begin() + m, puncteY.begin() + m, puncteY.begin() + dr, puncteAux.begin(), cmpDupaY);
	copy(puncteAux.begin(), puncteAux.begin() + (dr - st), puncteY.begin() + st);

	//construim banda
	vector <punct> banda;
	for (int i = st; i < dr; ++i) {
		if (abs(puncteY[i].x - puncte[m].x) <= distMinStDr)
			banda.push_back(puncteY[i]);
	}
	//rezolvam banda
	double distMinOverall = distMinStDr;
	for (int i = 0; i<banda.size(); ++i)
		for (int j = i + 1; j < banda.size() && banda[j].y - banda[i].y <= distMinStDr; ++j) {
			double distCur = distEuclid(banda[i], banda[j]);
			if (distCur < distMinOverall)
				distMinOverall = distCur;
		}

	return distMinOverall;
}

void distMinPunctePlan() {
	int n;
	cin >> n;

	vector <punct> puncte(n);
	for (int i = 0; i < n; ++i) {
		cin >> puncte[i].x;
		cin >> puncte[i].y;
	}

	sort(puncte.begin(), puncte.end(), cmpDupaX);

	vector <punct> puncteY = puncte;

	cout << fixed;
	cout << setprecision(6) << distMinPunctePlanRec(puncte, 0, puncte.size(), puncteY) << "\n";
}

int _tmain(int argc, _TCHAR* argv[])
{
	jocGasireGaura();
	return 0;
}