问题1676--【USACO】Grazing Sets

1676: 【USACO】Grazing Sets

时间限制: 1 Sec  内存限制: 64 MB
提交: 6  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

Farmer John's N (4 <= N <= 10,000) cows live at various points within a circular field. FJ wants to partition his cows by building K (3 <= K <= 1000) fences radially outward from the center of the field at evenly-spaced angles (each measuring 360/K degrees). Depending on how he rotates this system of fences, he can partition the cows into K subsets, each containing a different subset of cows (potentially an empty subset). Define the RANGE of this partition as the number of cows in the largest set minus the number of cows in the smallest set. Determine the minimum attainable RANGE value for a given set of cows. Of course, no cow can straddle a fence. Cows must be in one partition or the other. To avoid problems with rounding, the input data will not contain cows that are very close to an integer multiple of 360/K degrees apart.

输入

* Line 1: Two integers: N and K * Lines 2..N+1: Each line contains a single double that tells the angle at which a cow is grazing. Angles are expressed in degrees, 0 <= angle < 360.

输出

A single line with the integer that is the minimum attainable RANGE value for the set of cows.

样例输入 复制

4 3 30 60 150.003 240

样例输出 复制

1

来源/分类


[提交] [状态]