시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 18 17 41.463%

문제

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

다항식 함수가 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를 출력한다.

예제 입력

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

예제 출력

2
1
1
6

힌트

출처

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

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: ntopia