시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 88 19 15 26.316%

문제

N개의 점들이 원의 내부에 찍혀 있다. 이 원을 K개의 부채꼴로 등분하려 한다. 즉, 각 부채꼴의 중심각이 360/K도가 되어야 한다. 부채꼴을 어떻게 나누느냐에 따라서 각 부채꼴에 찍혀 있는 점의 개수가 달라질 수 있다.

N개의 점들이 찍혀 있는 각도가 주어졌을 때, 가장 많은 점이 찍혀 있는 부채꼴에 찍혀 있는 점의 개수와, 가장 적은 점이 찍혀 있는 부채꼴에 찍혀 있는 점의 개수의 차이의 최소값을 구하는 프로그램을 작성하시오.

단, 부채꼴의 테두리에 점이 포함되어서는 안 된다.

입력

첫째 줄에 N(3≤N≤10,000), K(3≤K≤1,000)가 주어진다. 다음 N개의 줄에는 실수로 나타나는 각도가 주어진다. 각도는 0이상 360미만이며, 실수 연산의 오차를 막기 위해 360/K의 정수배에 근접한 각도로 떨어져 있는 점은 없다.

출력

첫째 줄에 부채꼴에 찍혀 있는 점의 최대 개수와 최소 개수의 차이의 최솟값을 출력한다.

예제 입력

4 3
30
60
150.003
240

예제 출력

1

힌트

출처

  • 문제를 번역한 사람: author5