시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 154 39 31 38.272%

문제

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

다각형에서 꼭지점 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
W3sicHJvYmxlbV9pZCI6IjU3MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWNkOTVcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViYWE4XHViNGUwIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc3NCBcdWQ1NWMgXHVjNmQwXHVjNzU4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YjBiNFx1YzgxMVx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzZkMFx1YzVkMCBcdWIwYjRcdWM4MTFcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzc0IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4MTVcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHViNDE4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM5YzBcdWM2Y2NcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzgxNVx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1Yjc4MCwgXHViYWE4XHViNGUwIFx1YWMwMVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzE5XHVhY2UwLCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM1ZDBcdWMxMWMgXHVhZjJkXHVjOWMwXHVjODEwIHZcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViODI0XHViYTc0LCBcdWJhM2NcdWM4MDAsIFx1YWRmOCBcdWFmMmRcdWM5YzBcdWM4MTBcdWFjZmMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWYyZFx1YzljMFx1YzgxMCB3MVx1YWNmYyB3Mlx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCB3MVx1YWNmYyB3Mlx1Yjk3YyBcdWM3NzRcdWM1YjQsIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJjYzBcdWM3NDQgXHViOWNjXHViNGU0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliYyAoYSlcdWIyOTQgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCAxMFx1YWMxY1x1Yzc3OCBcdWM2ZDBcdWM1ZDAgXHViMGI0XHVjODExXHVkNTU4XHViMjk0IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1YWNlMCwgKGIpXHViMjk0IChhKVx1YzVkMFx1YzExYyZuYnNwO1x1YWYyZFx1YzljMFx1YzgxMCBcdWIyZTRcdWMxMmYgXHVhYzFjXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU3NCwgXHVjODE1XHVjNjI0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlMCBcdWFkZjhcdWI5YmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG9seSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6Mzg2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmNjMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1YzEzOCBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMGI0XHVjODExIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggWDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFg8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjM8XC9zdXA+KSBYPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWIwYjRcdWM4MTEgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMwMSBcdWFmMmRcdWM5YzBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1ZDYzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgaVx1YmM4OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWFjZmMgKGkrMSkgbW9kIE5cdWJjODggXHVhZjJkXHVjOWMwXHVjODEwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWQ2MzhcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHVhY2UwLCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNjM4XHViMjk0IFx1ZDYwNFx1YWNmYyBcdWIyZTRcdWI5NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzgxNVx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzgxNVx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCwgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU3MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaHJpbmtpbmcgUG9seWdvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcG9seWdvbiBpcyBzYWlkIHRvIGJlIGluc2NyaWJlZCBpbiBhIGNpcmNsZSB3aGVuIGFsbCBpdHMgdmVydGljZXMgbGllIG9uIHRoYXQgY2lyY2xlLiBJbiB0aGlzIHByb2JsZW0geW91IHdpbGwgYmUgZ2l2ZW4gYSBwb2x5Z29uIGluc2NyaWJlZCBpbiBhIGNpcmNsZSwgYW5kIHlvdSBtdXN0IGRldGVybWluZSB0aGUgbWluaW11bSBudW1iZXIgb2YgdmVydGljZXMgdGhhdCBzaG91bGQgYmUgcmVtb3ZlZCB0byB0cmFuc2Zvcm0gdGhlIGdpdmVuIHBvbHlnb24gaW50byBhIHJlZ3VsYXIgcG9seWdvbiwgaS5lLiwgYSBwb2x5Z29uIHRoYXQgaXMgZXF1aWFuZ3VsYXIgKGFsbCBhbmdsZXMgYXJlIGNvbmdydWVudCkgYW5kIGVxdWlsYXRlcmFsIChhbGwgZWRnZXMgaGF2ZSB0aGUgc2FtZSBsZW5ndGgpLjxcL3A+XHJcblxyXG48cD5XaGVuIHlvdSByZW1vdmUgYSB2ZXJ0ZXggdiBmcm9tIGEgcG9seWdvbiB5b3UgXHVmYjAxcnN0IHJlbW92ZSB0aGUgdmVydGV4IGFuZCB0aGUgZWRnZXMgY29ubmVjdGluZyBpdCB0byBpdHMgYWRqYWNlbnQgdmVydGljZXMgdzEgYW5kIHcyLCBhbmQgdGhlbiBjcmVhdGUgYSBuZXcgZWRnZSBjb25uZWN0aW5nIHcxIGFuZCB3Mi4gRmlndXJlIChhKSBiZWxvdyBpbGx1c3RyYXRlcyBhIHBvbHlnb24gaW5zY3JpYmVkIGluIGEgY2lyY2xlLCB3aXRoIHRlbiB2ZXJ0aWNlcywgYW5kIFx1ZmIwMWd1cmUgKGIpIHNob3dzIGEgcGVudGFnb24gKHJlZ3VsYXIgcG9seWdvbiB3aXRoIFx1ZmIwMXZlIGVkZ2VzKSBmb3JtZWQgYnkgcmVtb3ZpbmcgXHVmYjAxdmUgdmVydGljZXMgZnJvbSB0aGUgcG9seWdvbiBpbiAoYSkuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG9seSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6Mzg2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB3ZSBjb25zaWRlciB0aGF0IGFueSBwb2x5Z29uIG11c3QgaGF2ZSBhdCBsZWFzdCB0aHJlZSBlZGdlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBjb250YWlucyBvbmUgaW50ZWdlciBOIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiB0aGUgaW5zY3JpYmVkIHBvbHlnb24gKDMgJmxlOyBOICZsZTsgMTA8c3VwPjQ8XC9zdXA+KS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgWDxzdWI+aTxcL3N1Yj4gc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgKDEgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD4zPFwvc3VwPiwgZm9yIDAgJmxlOyBpICZsZTsgTiAmbWludXM7IDEpLiBFYWNoIFhpIHJlcHJlc2VudHMgdGhlIGxlbmd0aCBvZiB0aGUgYXJjIGRlXHVmYjAxbmVkIGluIHRoZSBpbnNjcmliaW5nIGNpcmNsZSwgY2xvY2t3aXNlLCBieSB2ZXJ0ZXggaSBhbmQgdmVydGV4IChpICsgMSkgbW9kIE4uIFJlbWVtYmVyIHRoYXQgYW4gYXJjIGlzIGEgc2VnbWVudCBvZiB0aGUgY2lyY3VtZmVyZW5jZSBvZiBhIGNpcmNsZTsgZG8gbm90IG1pc3Rha2UgaXQgZm9yIGEgY2hvcmQsIHdoaWNoIGlzIGEgbGluZSBzZWdtZW50IHdob3NlIGVuZHBvaW50cyBib3RoIGxpZSBvbiBhIGNpcmNsZS48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25seSBvbmUgemVyby48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IG11c3QgYmUgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHlvdXIgcHJvZ3JhbSBtdXN0IHByaW50IGEgc2luZ2xlIGxpbmUsIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHZlcnRpY2VzIHRoYXQgbXVzdCBiZSByZW1vdmVkIGZyb20gdGhlIGdpdmVuIHBvbHlnb24gdG8gZm9ybSBhIHJlZ3VsYXIgcG9seWdvbi4gSWYgaXQgaXMgbm90IHBvc3NpYmxlIHRvIGZvcm0gYSByZWd1bGFyIHBvbHlnb24sIHRoZSBsaW5lIG11c3QgY29udGFpbiBvbmx5IHRoZSB2YWx1ZSAtMS48XC9wPlxyXG5cclxuPHA+VGhlIG91dHB1dCBtdXN0IGJlIHdyaXR0ZW4gdG8gc3RhbmRhcmQgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==