/*
TASK: KROKODILAIV
LANG: C++
*/

#include <iostream>
#include <fstream>

using namespace std;

#define inputFile		"KROKO.DAT"
#define outputFile		"KROKO.REZ"
#define dviHipotezes	true

// tikslumas - 4 skaičiai po kablelio (arba dešimt tūkstantųjų)
#define tikslumas	10000
// kiek yra skirtingų agresyvių (arba neagresyvių) krokodilų
#define skirtingu	(100 * tikslumas + 1)
// maksimalus krokodilų skaičius
#define maks		3000000

// susumuojama distribucija, kad vienu kreipiniu į masyvą būtų galima rasti
// didesniu arba lygiu už pasirinktą slenkstį elementų kiekį
void suma(int *sumos, int *distribucija, int viso)
{
	sumos[0] = 0;
	for (int t = 1; t < viso; ++t)
		sumos[t] = distribucija[t - 1] + sumos[t - 1];
}

// surandamas minimalus slenkstis, kuriuo agresyvūs krokodilai atskiriami
// nuo neagresyvių darant mažiausiai klaidų
int slenkstis(int *sumos, int *distribucija, int viso, int *klaida)
{
	int gerSlenkstis = -1;
	int klaidos = 0;
	
	*klaida = maks;
	for (int i = viso - 1; i >= 0; --i)
	{
		klaidos += distribucija[i];
		if (klaidos + sumos[i] <= *klaida)
		{
			//if (klaidos + sumos[i] < *klaida)
			//	cout << i << "\t" << klaidos + sumos[i] << endl;
			*klaida = klaidos + sumos[i];
			gerSlenkstis = i;
		}
	}

	return gerSlenkstis;
}

int main()
{
	int *agresyvus = new int[skirtingu];
	int *neagresyvus = new int[skirtingu];

	memset(agresyvus, 0, sizeof(int) * skirtingu);
	memset(neagresyvus, 0, sizeof(int) * skirtingu);

	// nuskaitome pradinius duomenis. uždaviniui išspręsti nereikia saugoti
	// kiekvieno krokodilo atskirai, užtenka saugoti tik, kiek ir kokių
	// krokodilų buvo suskaičiuota: krokodilus skirstome į agresyvius ir
	// neagresyvius ir nurodytu sąlygoje tikslumus skaičiuojame jų kiekius.
	int k = 0;
	ifstream input(inputFile);
	input >> k;
	for (int i = 0; i < k; ++i)
	{
		float proc;
		int agresyvumas;

		input >> proc >> agresyvumas;
		if (1 == agresyvumas)
			++agresyvus[(int) (proc * tikslumas + 0.5)];
		else
			++neagresyvus[(int) (proc * tikslumas + 0.5)];
	}
	input.close();

	// salygoje pasufleruota, kad iš viso yra galima du variantai:
	//   1) arba dauguma agresyviųjų krokodilų yra labiau žali negu balti;
	//   2) arba dauguma agresyviųjų krokodilų yra labiau balti negu žali.

	int *sumos = new int[skirtingu];

	// tikriname pirmąją hipotezę
	suma(sumos, agresyvus, skirtingu);
	int klaida1 = maks;
	int slenkstis1 = slenkstis(sumos, neagresyvus, skirtingu, &klaida1);
	
	// jei reikia, tikriname antrąją hipotezę
	int klaida2 = maks;
	int slenkstis2 = -1;
	if (dviHipotezes) {
		// apsukame duomenis, t.y. saugome krokodilu kiekius ne žalios spalvos
		// atžvilgiu, o baltos
		for (int i = 0; i < skirtingu / 2; ++i) {
			int tmp;

			tmp = agresyvus[i];
			agresyvus[i] = agresyvus[skirtingu - i - 1];
			agresyvus[skirtingu - i - 1] = tmp;

			tmp = neagresyvus[i];
			neagresyvus[i] = neagresyvus[skirtingu - i - 1];
			neagresyvus[skirtingu - i - 1] = tmp;
		}

		// kartojame slenksčio paiešką
		suma(sumos, agresyvus, skirtingu);
		klaida2 = -1;
		slenkstis2 = slenkstis(sumos, neagresyvus, skirtingu, &klaida2);
	}

	delete[] sumos;
	delete[] neagresyvus;
	delete[] agresyvus;


	// išvedame hipotezės, kuri daro mažiausiai klaidų, rezultatus
	ofstream output(outputFile);
	output.precision(4);
	if (!dviHipotezes)
		output << fixed << (float) slenkstis1 / (float) tikslumas << " " << klaida1 << endl;
	else {
		if (klaida1 < klaida2)
			output << "1 " << fixed << (float) slenkstis1 / (float) tikslumas << " " << klaida1 << endl;
		else
			output << "0 " << fixed << (float) slenkstis2 / (float) tikslumas << " " << klaida2 << endl;
	}
	output.close();

	/**
	cout.precision(4);
	if (klaida1 < klaida2)
		cout << "spalva=1, slenkstis1=" << fixed << (float) slenkstis1 / (float) tikslumas << ", klaida1=" << klaida1 << endl;
	else
		cout << "spalva=0, slenkstis2=" << fixed << (float) slenkstis2 / (float) tikslumas << ", klaida2=" << klaida2 << endl;
	/**/

	return 0;
}