폴리 노미얼

국제 조류학자 연합(International Ornithologists Union)은 새의 계산 능력을 연구하는 조류 계산 임무(Avian Computation Mission, ACM)를 운영한다. 그중 가장 유명한 "폴리 노미얼(Polly Nomial)" 프로젝트에서는 앵무새들이 음이 아닌 정수 계수를 가진 한 변수 $x$의 간단한 다항식을 계산하도록 훈련받는다.

각 앵무새는 부리로 조작하는 계산기인 앵무새 디지털 도우미(Parrot Digital Assistant, PDA)를 사용한다. 이 계산기의 키는 숫자 $0$부터 $9$까지, 기호 $x$, 그리고 연산자 $+$, $\times$, $=$이다. $x$ 키는 변수를 나타내며, 검사를 위해 그 값이 내부적으로 정해지지만 앵무새는 기호 $x$만 본다.

PDA는 기본적인 즉시 실행 계산기처럼 동작한다. 별도의 메모리가 없고 연산자 우선순위도 없으며, 항상 왼쪽에서 오른쪽으로 계산한다. 각 $+$ 또는 $\times$ 연산은 입력되는 즉시 현재 화면에 표시된 값과 그다음에 입력되는 피연산자에 적용된다. 피연산자는 변수 $x$이거나, 한 자리씩 입력되는 음이 아닌 정수이다.

예를 들어 $x^3 + x + 11$을 계산하려면 앵무새는 다음과 같이 누를 수 있다.

$$x,\ \times,\ x,\ \times,\ x,\ +,\ x,\ +,\ 1,\ 1,\ =$$

이는 $((((x \times x) \times x) + x) + 11)$의 순서로 계산된다.

PDA에는 메모리가 없으므로 앵무새는 중간 결과를 따로 저장할 수 없다. 예를 들어 $x^3 + 2x^2 + 11$ 같은 다항식에서는 $x^3$을 먼저 계산해 두고 $2x^2$을 계산할 수 없다. 대신 하나의 화면만으로 답에 도달할 수 있는 연산 순서(예컨대 호너(Horner) 방식처럼 중첩된 순서)를 선택해야 한다.

계산 비용은 마지막 $=$ 키를 포함한 전체 키 입력 횟수이다. $x^3 + x + 11$에 대한 위 순서의 비용은 $11$이다. $x$ 키 4번, $\times$ 2번, $+$ 2번, 숫자 $1$ 2번, 그리고 $=$ 1번이다. 이것이 이 다항식의 최소 비용이다.

각 다항식에 대해 주어진 $x$에서의 값과 최소 키 입력 비용을 구하는 프로그램을 작성하라. 앵무새는 최고차항 계수가 $1$이 아니면 겁을 먹으므로, 최고차항의 계수는 항상 $1$이다.

각 줄은 다항식 $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ 하나를 나타낸다. 줄의 맨 앞에는 차수 $n$ ($1 \le n \le 100$)이 오고, 이어서 차수가 큰 항부터 작은 항 순서로 음이 아닌 계수 $a_n, a_{n-1}, \ldots, a_0$ ($a_n = 1$)이 $n+1$개 주어지며, 마지막으로 $x$의 정숫값이 주어진다. 이 값은 항상 $1$ 또는 $-1$이다. 입력의 끝은 두 값 0 0으로 이루어진 줄로 표시되며, 이 줄은 처리하지 않는다.

각 다항식에 대해 Polynomial i: value cost 형식의 줄을 출력한다. 여기서 i는 입력에서 그 다항식의 순서($1$부터 시작), value는 주어진 $x$에서 다항식을 계산한 값, cost는 그 다항식을 계산하는 데 필요한 최소 키 입력 횟수(마지막 $=$ 포함)이다.