ICPC Regionals 2008 >> Asia - Aizu

4157.cpp

#include <stdio.h>
#include <string.h>
//#define DEBUG

int n;
int w;

int histo[12]; // since at most 10 intervals

int main() {

	while (scanf("%d %d", &n, &w) != EOF && n != 0) {
		int v;
		memset(histo, 0, sizeof(histo));

		for (int i = 0; i < n; ++i) {
			
			scanf("%d", &v);

			histo[v / w]++;
		}

		// find max height
		//      and start & end
		int highest = -1;
		int begin = 15, end = -1;
		for (int i = 0; i < 12; ++i) {
			if (histo[i] > highest) highest = histo[i];
			if (histo[i] > 0) {
				if (begin > i) begin = i;
				if (end < i) end = i;
			}
		}
		begin = 0; // force begi to 0

#ifdef DEBUG
		printf("[%d %d], highest: %d\n", begin, end, highest);
#endif
		int count = end - begin + 1;
		// calculate area
		double area = 0e0;

		for (int i = 0; i < 12; ++i) {
			area += histo[i] * (1e0 - (double)(i - begin) / (count - 1));
		}

		area /= highest;

		printf("%lf\n", area + 0.01);
	}


	return 0;
}