시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB227584937.405%

문제

다각형의 모든 꼭짓점이 한 원의 위에 있을 때, 그 다각형은 내접한다고 한다. 원에 내접하는 다각형이 주어진다. 이때, 이 다각형이 정다각형이 되기 위해서 지워야 하는 꼭짓점의 개수를 구하는 프로그램을 작성하시오. 정다각형이란, 모든 각의 크기가 같고, 변의 길이가 같은 다각형을 말한다.

다각형에서 꼭짓점 v를 제거하려면, 먼저, 그 꼭짓점과 연결된 꼭짓점 w1과 w2를 찾아야 한다. 그 다음, w1과 w2를 이어, 새로운 변을 만들면 된다.

아래 그림 (a)는 꼭짓점의 수가 10개인 원에 내접하는 다각형이고, (b)는 (a)에서 꼭짓점 다섯 개를 제거해, 정오각형을 만든 그림이다.

다각형의 변의 개수는 적어도 세 개이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 내접 다각형의 꼭짓점의 수 N이 주어진다. (3 ≤ N ≤ 104) 둘째 줄에는 N개의 정수 Xi가 주어진다. (1 ≤ Xi ≤ 103) Xi는 내접 다각형의 각 꼭짓점 사이의 호의 길이이다. 즉, i번 꼭짓점과 (i+1) mod N번 꼭짓점 사이의 호의 길이이고, 시계 방향으로 주어진다. 호는 현과 다르다. 

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스에 대해서, 정다각형으로 만들기 위해 제거해야 하는 꼭짓점의 최소 개수를 출력한다. 만약, 정다각형을 만들 수 없다면, -1을 출력한다. 

예제 입력 1

3
1000 1000 1000
6
1 2 3 1 2 3
3
1 1 2
10
10 40 20 30 30 10 10 50 24 26
0

예제 출력 1

0
2
-1
5
W3sicHJvYmxlbV9pZCI6IjU3MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWNkOTVcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViYWE4XHViNGUwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWQ1NWMgXHVjNmQwXHVjNzU4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YjBiNFx1YzgxMVx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzZkMFx1YzVkMCBcdWIwYjRcdWM4MTFcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YzgxNVx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0MThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHViNzgwLCBcdWJhYThcdWI0ZTAgXHVhYzAxXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjMTlcdWFjZTAsIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1YWMwMVx1ZDYxNVx1YzVkMFx1YzExYyBcdWFmMmRcdWM5ZDNcdWM4MTAgdlx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWI4MjRcdWJhNzQsIFx1YmEzY1x1YzgwMCwgXHVhZGY4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZjJkXHVjOWQzXHVjODEwIHcxXHVhY2ZjIHcyXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIHcxXHVhY2ZjIHcyXHViOTdjIFx1Yzc3NFx1YzViNCwgXHVjMGM4XHViODVjXHVjNmI0IFx1YmNjMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIChhKVx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIDEwXHVhYzFjXHVjNzc4IFx1YzZkMFx1YzVkMCBcdWIwYjRcdWM4MTFcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHVhY2UwLCAoYilcdWIyOTQgKGEpXHVjNWQwXHVjMTFjJm5ic3A7XHVhZjJkXHVjOWQzXHVjODEwIFx1YjJlNFx1YzEyZiBcdWFjMWNcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0LCBcdWM4MTVcdWM2MjRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGUwIFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb2x5KDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NnB4OyB3aWR0aDozODZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViY2MwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVjMTM4IFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwYjRcdWM4MTEgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwPHN1cD40PFwvc3VwPikgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBYPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgWDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+MzxcL3N1cD4pIFg8c3ViPmk8XC9zdWI+XHViMjk0IFx1YjBiNFx1YzgxMSBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YWYyZFx1YzlkM1x1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVkNjM4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBpXHViYzg4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YWNmYyAoaSsxKSBtb2QgTlx1YmM4OCBcdWFmMmRcdWM5ZDNcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1ZDYzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWFjZTAsIFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ2MzhcdWIyOTQgXHVkNjA0XHVhY2ZjIFx1YjJlNFx1Yjk3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTcyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNocmlua2luZyBQb2x5Z29ucyIsImRlc2NyaXB0aW9uIjoiPHA+QSBwb2x5Z29uIGlzIHNhaWQgdG8gYmUgaW5zY3JpYmVkIGluIGEgY2lyY2xlIHdoZW4gYWxsIGl0cyB2ZXJ0aWNlcyBsaWUgb24gdGhhdCBjaXJjbGUuIEluIHRoaXMgcHJvYmxlbSB5b3Ugd2lsbCBiZSBnaXZlbiBhIHBvbHlnb24gaW5zY3JpYmVkIGluIGEgY2lyY2xlLCBhbmQgeW91IG11c3QgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiB2ZXJ0aWNlcyB0aGF0IHNob3VsZCBiZSByZW1vdmVkIHRvIHRyYW5zZm9ybSB0aGUgZ2l2ZW4gcG9seWdvbiBpbnRvIGEgcmVndWxhciBwb2x5Z29uLCBpLmUuLCBhIHBvbHlnb24gdGhhdCBpcyBlcXVpYW5ndWxhciAoYWxsIGFuZ2xlcyBhcmUgY29uZ3J1ZW50KSBhbmQgZXF1aWxhdGVyYWwgKGFsbCBlZGdlcyBoYXZlIHRoZSBzYW1lIGxlbmd0aCkuPFwvcD5cclxuXHJcbjxwPldoZW4geW91IHJlbW92ZSBhIHZlcnRleCB2IGZyb20gYSBwb2x5Z29uIHlvdSBcdWZiMDFyc3QgcmVtb3ZlIHRoZSB2ZXJ0ZXggYW5kIHRoZSBlZGdlcyBjb25uZWN0aW5nIGl0IHRvIGl0cyBhZGphY2VudCB2ZXJ0aWNlcyB3MSBhbmQgdzIsIGFuZCB0aGVuIGNyZWF0ZSBhIG5ldyBlZGdlIGNvbm5lY3RpbmcgdzEgYW5kIHcyLiBGaWd1cmUgKGEpIGJlbG93IGlsbHVzdHJhdGVzIGEgcG9seWdvbiBpbnNjcmliZWQgaW4gYSBjaXJjbGUsIHdpdGggdGVuIHZlcnRpY2VzLCBhbmQgXHVmYjAxZ3VyZSAoYikgc2hvd3MgYSBwZW50YWdvbiAocmVndWxhciBwb2x5Z29uIHdpdGggXHVmYjAxdmUgZWRnZXMpIGZvcm1lZCBieSByZW1vdmluZyBcdWZiMDF2ZSB2ZXJ0aWNlcyBmcm9tIHRoZSBwb2x5Z29uIGluIChhKS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb2x5KDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NnB4OyB3aWR0aDozODZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHdlIGNvbnNpZGVyIHRoYXQgYW55IHBvbHlnb24gbXVzdCBoYXZlIGF0IGxlYXN0IHRocmVlIGVkZ2VzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE4gaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIHRoZSBpbnNjcmliZWQgcG9seWdvbiAoMyAmbGU7IE4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBYPHN1Yj5pPFwvc3ViPiBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyAoMSAmbGU7IFg8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjM8XC9zdXA+LCBmb3IgMCAmbGU7IGkgJmxlOyBOICZtaW51czsgMSkuIEVhY2ggWGkgcmVwcmVzZW50cyB0aGUgbGVuZ3RoIG9mIHRoZSBhcmMgZGVcdWZiMDFuZWQgaW4gdGhlIGluc2NyaWJpbmcgY2lyY2xlLCBjbG9ja3dpc2UsIGJ5IHZlcnRleCBpIGFuZCB2ZXJ0ZXggKGkgKyAxKSBtb2QgTi4gUmVtZW1iZXIgdGhhdCBhbiBhcmMgaXMgYSBzZWdtZW50IG9mIHRoZSBjaXJjdW1mZXJlbmNlIG9mIGEgY2lyY2xlOyBkbyBub3QgbWlzdGFrZSBpdCBmb3IgYSBjaG9yZCwgd2hpY2ggaXMgYSBsaW5lIHNlZ21lbnQgd2hvc2UgZW5kcG9pbnRzIGJvdGggbGllIG9uIGEgY2lyY2xlLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBvbmx5IG9uZSB6ZXJvLjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgbXVzdCBiZSByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgeW91ciBwcm9ncmFtIG11c3QgcHJpbnQgYSBzaW5nbGUgbGluZSwgY29udGFpbmluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgdmVydGljZXMgdGhhdCBtdXN0IGJlIHJlbW92ZWQgZnJvbSB0aGUgZ2l2ZW4gcG9seWdvbiB0byBmb3JtIGEgcmVndWxhciBwb2x5Z29uLiBJZiBpdCBpcyBub3QgcG9zc2libGUgdG8gZm9ybSBhIHJlZ3VsYXIgcG9seWdvbiwgdGhlIGxpbmUgbXVzdCBjb250YWluIG9ubHkgdGhlIHZhbHVlIC0xLjxcL3A+XHJcblxyXG48cD5UaGUgb3V0cHV0IG11c3QgYmUgd3JpdHRlbiB0byBzdGFuZGFyZCBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Latin America > South America Regional Contests 2008 K번