← 返回 citadel 的题目列表Statistics from a 256-Bucket Frequency Array
类型：online_judge
Problem: Compute Statistics from a 256-Bucket Frequency Array
You are given a frequency array count of length 256, where count[i] represents how many times value i appears in the original data. The possible values are fixed to 0..255.
Compute the following statistics of the original data:
minimum
maximum
mean
median
mode
population standard deviation
If there are multiple modes, return the smallest value.
The standard deviation is defined as:
[ std = \sqrt{\frac{\sum count[i] \times (i - mean)^2}{N}} ]
where N = sum(count).
Input Format
For testing purposes, stdin uses a sparse representation:
The first line contains an integer m, the number of non-zero buckets.
The next m lines each contain two integers value count, meaning value appears count times.
This is equivalent to a frequency array of length 256, with all omitted buckets having frequency 0.
Output Format
Print one line:
minimum maximum mean median mode stddev
where:
minimum, maximum, and mode are integers;
mean, median, and stddev are printed with exactly 5 digits after the decimal point.
Constraints
0 <= value <= 255
count > 0
1 <= m <= 256
There is at least one data point: sum(count) > 0
The total frequency can be large, so do not expand the original data array.
Example
Input
3
0 2
1 5
2 8
Output
0 2 1.40000 2.00000 2 0.71181
Example
Input
3
0 2
1 5
2 8
Output
0 2 1.40000 2.00000 2 0.71181