시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 29 25 43.103%

문제

김상근 교수는 수치표를 만드는 새로운 컴퓨팅 엔진을 개발했다. 이 엔진은 단일 변수 다항식 함수의 값을 계산하기 위해 만들어졌다.

다항식 함수가 f(x) = x2 + 2x + 1인 경우에 결과로 나오는 값은 1 (=f(0)), 4 (=f(1)), 9 (=f(2)), 16 (=f(3)), 25 (=f(4))가 있다.

하지만, 상근이는 음주 코딩을 하다가 실수를 하였다. 따라서, 이 엔진은 항상 하나의 특정한 값에 대해서만 결과를 잘못 출력한다. 따라서, 위의 다항식 함수를 입력했을 때, 1, 4, 9, 16, 25 대신에 1, 4, 12, 16, 25가 나올 수 있다.

상근이의 엔진이 출력한 값이 주어졌을 때, 몇 번째 결과가 잘못 계산된 것인지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 다항식의 차수 d가 주어진다. 예를 들어, 4x5 + 3x + 0.5인 경우에 다항식의 차수는 5이고, 2.4x + 3.8인 경우에는 1이다. d는 5보다 작거나 같다.

다음 d+3개 줄에는 f(0), f(1), ..., f(d+2)의 결과가 주어진다. f는 다항식 함수이고, 입력으로 주어지지 않는다. 모든 결과 값은 -100.0보다 크고, 100.0보다 작은 실수이다.

항상 잘못 계산된 값은 f(0), f(1), ..., f(d+2)중 하나이다. 올바른 값과의 오차는 1.0보다 크다. 컴퓨터로 소수점 계산을 했을 때, 오차는 피할 수 없다. 따라서, 다른 값에도 오차가 있을 수 있다. 하지만, 이 오차는 매우 작고, 10-6을 넘지 않는다.

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

출력

각 테스트 케이스에 대해서, 잘못 계산된 값이 몇 번째 값인지 출력한다. f(i)의 결과가 잘못되었다면, i를 출력한다.

예제 입력 1

2
1.0
4.0
12.0
16.0
25.0
1
-30.5893962764
5.76397083962
39.3853798058
74.3727663177
4
42.4715310246
79.5420238202
28.0282396675
-30.3627807522
-49.8363481393
-25.5101480106
7.58575761381
5
-21.9161699038
-48.469304271
-24.3188578417
-2.35085940324
-9.70239202086
-47.2709510623
-93.5066246072
-82.5073836498
0

예제 출력 1

2
1
1
6
W3sicHJvYmxlbV9pZCI6IjM4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OThcdWJhYmJcdWI0MWMgXHVhY2M0XHVjMGIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlNDBcdWMwYzFcdWFkZmMgXHVhZDUwXHVjMjE4XHViMjk0IFx1YzIxOFx1Y2U1OFx1ZDQ1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2VmNFx1ZDRlOFx1ZDMwNSBcdWM1ZDRcdWM5YzRcdWM3NDQgXHVhYzFjXHViYzFjXHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjNWQ0XHVjOWM0XHVjNzQwIFx1YjJlOFx1Yzc3YyBcdWJjYzBcdWMyMTgmbmJzcDtcdWIyZTRcdWQ1NmRcdWMyZGQgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjljY1x1YjRlNFx1YzViNFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVkNTZkXHVjMmRkIFx1ZDU2OFx1YzIxOFx1YWMwMCBmKHgpID0geDxzdXA+MjxcL3N1cD4gKyAyeCArIDFcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWNiMFx1YWNmY1x1Yjg1YyBcdWIwOThcdWM2MjRcdWIyOTQgXHVhYzEyXHVjNzQwIDEgKD1mKDApKSwgNCAoPWYoMSkpLCA5ICg9ZigyKSksIDE2ICg9ZigzKSksIDI1ICg9Zig0KSlcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NGNcdWM4ZmMgXHVjZjU0XHViNTI5XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YWMwMCBcdWMyZTRcdWMyMThcdWI5N2MgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Yzc3NCBcdWM1ZDRcdWM5YzRcdWM3NDAgXHVkNTZkXHVjMGMxIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQyYjlcdWM4MTVcdWQ1NWMgXHVhYzEyXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjljYyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjNzk4XHViYWJiIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM3MDRcdWM3NTggXHViMmU0XHVkNTZkXHVjMmRkIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWQ1ODhcdWM3NDQgXHViNTRjLCAxLCA0LCA5LCAxNiwgMjUgXHViMzAwXHVjMmUwXHVjNWQwIDEsIDQsIDEyLCAxNiwgMjVcdWFjMDAgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM1ZDRcdWM5YzRcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjIFx1YWMxMlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhODcgXHViYzg4XHVjOWY4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM3OThcdWJhYmIgXHVhY2M0XHVjMGIwXHViNDFjIFx1YWM4M1x1Yzc3OFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWQ1NmRcdWMyZGRcdWM3NTggXHVjYzI4XHVjMjE4IGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA0eDxzdXA+NTxcL3N1cD4gKyAzeCArIDAuNVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMmU0XHVkNTZkXHVjMmRkXHVjNzU4IFx1Y2MyOFx1YzIxOFx1YjI5NCA1XHVjNzc0XHVhY2UwLCAyLjR4ICsgMy44XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAxXHVjNzc0XHViMmU0LiBkXHViMjk0IDVcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIGQrM1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgZigwKSwgZigxKSwgLi4uLCBmKGQrMilcdWM3NTggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gZlx1YjI5NCBcdWIyZTRcdWQ1NmRcdWMyZGQgXHVkNTY4XHVjMjE4XHVjNzc0XHVhY2UwLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWNiMFx1YWNmYyBcdWFjMTJcdWM3NDAgLTEwMC4wXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgMTAwLjBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzJlNFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1Yzc5OFx1YmFiYiBcdWFjYzRcdWMwYjBcdWI0MWMgXHVhYzEyXHVjNzQwIGYoMCksIGYoMSksIC4uLiwgZihkKzIpXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHVjNjJjXHViYzE0XHViOTc4IFx1YWMxMlx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMS4wXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNC4gXHVjZWY0XHVkNGU4XHVkMTMwXHViODVjIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWFjYzRcdWMwYjBcdWM3NDQgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNjI0XHVjYzI4XHViMjk0IFx1ZDUzY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjJlNFx1Yjk3OCBcdWFjMTJcdWM1ZDBcdWIzYzQgXHVjNjI0XHVjYzI4XHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWM2MjRcdWNjMjhcdWIyOTQgXHViOWU0XHVjNmIwIFx1Yzc5MVx1YWNlMCwgMTA8c3VwPi02PFwvc3VwPlx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3OThcdWJhYmIgXHVhY2M0XHVjMGIwXHViNDFjIFx1YWMxMlx1Yzc3NCBcdWJhODcgXHViYzg4XHVjOWY4IFx1YWMxMlx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGYoaSlcdWM3NTggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1Yzc5OFx1YmFiYlx1YjQxOFx1YzVjOFx1YjJlNFx1YmE3NCwgaVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzgyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpbmQgdGhlIE91dGxpZXIiLCJkZXNjcmlwdGlvbiI6IjxwPlByb2Zlc3NvciBBYmFjdXMgaGFzIGp1c3QgYnVpbHQgYSBuZXcgY29tcHV0aW5nIGVuZ2luZSBmb3IgbWFraW5nIG51bWVyaWNhbCB0YWJsZXMuIEl0IHdhcyBkZXNpZ25lZCB0byBjYWxjdWxhdGUgdGhlIHZhbHVlcyBvZiBhIHBvbHlub21pYWwgZnVuY3Rpb24gaW4gb25lIHZhcmlhYmxlIGF0IHNldmVyYWwgcG9pbnRzIGF0IGEgdGltZS4gV2l0aCB0aGUgcG9seW5vbWlhbCBmdW5jdGlvbiBmKHgpID0geDxzdXA+MjxcL3N1cD4gKyAyeCArIDEsIGZvciBpbnN0YW5jZSwgYSBwb3NzaWJsZSBleHBlY3RlZCBjYWxjdWxhdGlvbiByZXN1bHQgaXMgMSAoPSBmKDApKSwgNCAoPSBmKDEpKSwgOSAoPSBmKDIpKSwgMTYgKD0gZigzKSksIGFuZCAyNSAoPSBmKDQpKS48XC9wPlxyXG5cclxuPHA+SXQgaXMgYSBwaXR5LCBob3dldmVyLCB0aGUgZW5naW5lIHNlZW1pbmdseSBoYXMgZmF1bHR5IGNvbXBvbmVudHMgYW5kIGV4YWN0bHkgb25lIHZhbHVlIGFtb25nIHRob3NlIGNhbGN1bGF0ZWQgc2ltdWx0YW5lb3VzbHkgaXMgYWx3YXlzIHdyb25nLiBXaXRoIHRoZSBzYW1lIHBvbHlub21pYWwgZnVuY3Rpb24gYXMgYWJvdmUsIGl0IGNhbiwgZm9yIGluc3RhbmNlLCBvdXRwdXQgMSwgNCwgMTIsIDE2LCBhbmQgMjUgaW5zdGVhZCBvZiAxLCA0LCA5LCAxNiwgYW5kIDI1LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHJlcXVlc3RlZCB0byBoZWxwIHRoZSBwcm9mZXNzb3IgaWRlbnRpZnkgdGhlIGZhdWx0eSBjb21wb25lbnRzLiBBcyB0aGUgZmlyc3Qgc3RlcCwgeW91IHNob3VsZCB3cml0ZSBhIHByb2dyYW0gdGhhdCBzY2FucyBjYWxjdWxhdGlvbiByZXN1bHRzIG9mIHRoZSBlbmdpbmUgYW5kIGZpbmRzIHRoZSB3cm9uZyB2YWx1ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBkYXRhc2V0cywgZWFjaCByZXByZXNlbnRpbmcgYSBjYWxjdWxhdGlvbiByZXN1bHQgaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwPkhlcmUsIGQgaW4gdGhlIGZpIHJzdCBsaW5lIGlzIGEgcG9zaXRpdmUgaW50ZWdlciB0aGF0IHJlcHJlc2VudHMgdGhlIGRlZ3JlZSBvZiB0aGUgcG9seW5vbWlhbCwgbmFtZWx5LCB0aGUgaGlnaGVzdCBleHBvbmVudCBvZiB0aGUgdmFyaWFibGUuIEZvciBpbnN0YW5jZSwgdGhlIGRlZ3JlZSBvZiA0eDxzdXA+NTxcL3N1cD4gKyAzeCArIDAuNSBpcyBmaXZlIGFuZCB0aGF0IG9mIDIuNHggKyAzLjggaXMgb25lLiBkIGlzIGF0IG1vc3QgZml2ZS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBkICsgMyBsaW5lcyBjb250YWluIHRoZSBjYWxjdWxhdGlvbiByZXN1bHQgb2YgZigwKSwgZigxKSwgLiAuIC4gLCBhbmQgZihkICsgMikgaW4gdGhpcyBvcmRlciwgd2hlcmUgZiBpcyB0aGUgcG9seW5vbWlhbCBmdW5jdGlvbi4gRWFjaCBvZiB0aGUgbGluZXMgY29udGFpbnMgYSBkZWNpbWFsIGZyYWN0aW9uIGJldHdlZW4gMTAwLjAgYW5kIDEwMC4wLCBleGNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gYXNzdW1lIHRoYXQgdGhlIHdyb25nIHZhbHVlLCB3aGljaCBpcyBleGFjdGx5IG9uZSBvZiBmKDApLCBmKDEpLCAuIC4gLiAsIGFuZCBmKGQgKyAyKSwgaGFzIGFuIGVycm9yIGdyZWF0ZXIgdGhhbiAxLjAuIFNpbmNlIHJvdW5kaW5nIGVycm9ycyBhcmUgaW5ldml0YWJsZSwgdGhlIG90aGVyIHZhbHVlcyBtYXkgYWxzbyBoYXZlIGVycm9ycyBidXQgdGhleSBhcmUgc21hbGwgYW5kIG5ldmVyIGV4Y2VlZCAxMDxzdXA+LTY8XC9zdXA+LjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCBpIGluIGEgbGluZSB3aGVuIHZpIGlzIHdyb25nLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2012 in Tokyo D번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: kipa00
  • 문제의 오타를 찾은 사람: ntopia