시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB366624125.309%

문제

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

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

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

입력

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

출력

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

예제 입력 1

4 3
30
60
150.003
240

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjE3MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHViMDk4XHViMjA0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YzgxMFx1YjRlNFx1Yzc3NCBcdWM2ZDBcdWM3NTggXHViMGI0XHViZDgwXHVjNWQwIFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM2ZDBcdWM3NDQgS1x1YWMxY1x1Yzc1OCBcdWJkODBcdWNjNDRcdWFmMzRcdWI4NWMgXHViNGYxXHViZDg0XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHViZDgwXHVjYzQ0XHVhZjM0XHVjNzU4IFx1YzkxMVx1YzJlY1x1YWMwMVx1Yzc3NCAzNjBcL0tcdWIzYzRcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViZDgwXHVjYzQ0XHVhZjM0XHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWIwOThcdWIyMDRcdWIyOTBcdWIwZDBcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YWMwMSBcdWJkODBcdWNjNDRcdWFmMzRcdWM1ZDAgXHVjYzBkXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YjJlY1x1Yjc3Y1x1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzgxMFx1YjRlNFx1Yzc3NCBcdWNjMGRcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YWMwMVx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzgxMFx1Yzc3NCBcdWNjMGRcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YmQ4MFx1Y2M0NFx1YWYzNFx1YzVkMCBcdWNjMGRcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAsIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjODEwXHVjNzc0IFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHViZDgwXHVjYzQ0XHVhZjM0XHVjNWQwIFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIFx1YmQ4MFx1Y2M0NFx1YWYzNFx1Yzc1OCBcdWQxNGNcdWI0NTBcdWI5YWNcdWM1ZDAgXHVjODEwXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDMgJmxlOyBOICZsZTsgMTAsMDAwKSwgSygzICZsZTsgSyAmbGU7IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZTRcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YWMwMVx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YjNjNFx1YjI5NCAwXHVjNzc0XHVjMGMxIDM2MFx1YmJmOFx1YjljY1x1Yzc3NFx1YmE3MCwgXHVjMmU0XHVjMjE4IFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWI5N2MgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCAzNjBcL0tcdWM3NTggXHVjODE1XHVjMjE4XHViYzMwXHVjNWQwIFx1YWRmY1x1YzgxMVx1ZDU1YyBcdWFjMDFcdWIzYzRcdWI4NWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZDgwXHVjYzQ0XHVhZjM0XHVjNWQwIFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNzIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JhemluZyBTZXRzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBOICg0ICZsdDs9IE4gJmx0Oz0gMTAsMDAwKSBjb3dzIGxpdmUgYXQgdmFyaW91cyBwb2ludHMgd2l0aGluIGEgY2lyY3VsYXIgZmllbGQuIEZKIHdhbnRzIHRvIHBhcnRpdGlvbiBoaXMgY293cyBieSBidWlsZGluZyBLICgzICZsdDs9IEsgJmx0Oz0gMTAwMCkgZmVuY2VzIHJhZGlhbGx5IG91dHdhcmQmbmJzcDtmcm9tIHRoZSBjZW50ZXIgb2YgdGhlIGZpZWxkIGF0IGV2ZW5seS1zcGFjZWQgYW5nbGVzIChlYWNoIG1lYXN1cmluZyAzNjBcL0sgZGVncmVlcykuIERlcGVuZGluZyBvbiBob3cgaGUgcm90YXRlcyB0aGlzIHN5c3RlbSBvZiBmZW5jZXMsIGhlIGNhbiBwYXJ0aXRpb24gdGhlIGNvd3MgaW50byBLJm5ic3A7c3Vic2V0cywgZWFjaCBjb250YWluaW5nIGEgZGlmZmVyZW50IHN1YnNldCBvZiBjb3dzIChwb3RlbnRpYWxseSBhbiBlbXB0eSBzdWJzZXQpLiZuYnNwO0RlZmluZSB0aGUgUkFOR0Ugb2YgdGhpcyBwYXJ0aXRpb24gYXMgdGhlIG51bWJlciBvZiBjb3dzIGluIHRoZSBsYXJnZXN0IHNldCBtaW51cyZuYnNwO3RoZSBudW1iZXIgb2YgY293cyBpbiB0aGUgc21hbGxlc3Qgc2V0LiAmbmJzcDtEZXRlcm1pbmUgdGhlIG1pbmltdW0gYXR0YWluYWJsZSBSQU5HRSB2YWx1ZSZuYnNwO2ZvciBhIGdpdmVuIHNldCBvZiBjb3dzLjxcL3A+XHJcblxyXG48cD5PZiBjb3Vyc2UsIG5vIGNvdyBjYW4gc3RyYWRkbGUgYSBmZW5jZS4gJm5ic3A7Q293cyBtdXN0IGJlIGluIG9uZSBwYXJ0aXRpb24gb3IgdGhlIG90aGVyLjxcL3A+XHJcblxyXG48cD5UbyBhdm9pZCBwcm9ibGVtcyB3aXRoIHJvdW5kaW5nLCB0aGUgaW5wdXQgZGF0YSB3aWxsIG5vdCBjb250YWluIGNvd3MgdGhhdCBhcmUgdmVyeSZuYnNwO2Nsb3NlIHRvIGFuIGludGVnZXIgbXVsdGlwbGUgb2YgMzYwXC9LIGRlZ3JlZXMgYXBhcnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIGludGVnZXJzOiBOIGFuZCBLPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogRWFjaCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGRvdWJsZSB0aGF0IHRlbGxzIHRoZSBhbmdsZSBhdCB3aGljaCBhIGNvdyBpcyBncmF6aW5nLiAmbmJzcDtBbmdsZXMgYXJlIGV4cHJlc3NlZCBpbiBkZWdyZWVzLCAwICZsdDs9IGFuZ2xlICZsdDsgMzYwLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSB3aXRoIHRoZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG1pbmltdW0gYXR0YWluYWJsZSBSQU5HRSB2YWx1ZSZuYnNwO2ZvciB0aGUgc2V0IG9mIGNvd3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO Winter 2002 Contest > Green 4번

  • 문제를 번역한 사람: author5