UVa 815

Flooded!.cpp

#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;

void inputRegions(int quantityOfRegions, vector<int> &regions)
{
	regions.resize(quantityOfRegions, 0);
	for (auto i = 0; i < quantityOfRegions; i++)
	{
		scanf("%d", &regions[i]);
		regions[i] *= 100;
	}
	sort(regions.begin(), regions.end());
}

vector<int> calculateAllRegionWaterCapability(std::vector<int> regions)
{
	auto waterCapability = vector<int>(regions.size(), 0);
	for (auto i = 1; i < regions.size(); i++)
	{
		waterCapability[i] = waterCapability[i - 1] + (regions[i] - regions[i - 1]) * i;
	}
	return waterCapability;
}

int findClosestNotFullCapabilityIndex(int flood, vector<int> &waterCapability)
{
	for (auto index = 1; index < waterCapability.size(); index++)
	{
		if (waterCapability[index] >= flood)
		{
			return index;
		}
	}
	return waterCapability.size();
}

int main()
{
	auto regions = vector<int> {};
	auto m = 0, n = 0, flood = 0, T = 1;
	while (~scanf("%d%d", &m, &n))
	{
		if (m == 0 && n == 0)
		{
			break;
		}

		inputRegions(m * n, regions);
		scanf("%d", &flood);

		auto waterCapability = calculateAllRegionWaterCapability(regions);
		auto index = findClosestNotFullCapabilityIndex(flood, waterCapability);
		auto restOfFlood = flood - waterCapability[index - 1];

		auto waterLevel = regions[index - 1] + static_cast<double>(restOfFlood) / index;
		auto areaPercentageUnderFlood = static_cast<double>((restOfFlood > 0) ? index : index - 1) / regions.size();

		printf("Region %d\n", T++);
		printf("Water level is %.2lf meters.\n", waterLevel / 100.0);
		printf("%.2lf percent of the region is under water.\n\n", areaPercentageUnderFlood * 100.0);
	}
	return 0;
}