The Avian Computation Mission of the International Ornithologists Union is dedicated to the study of intelligence in birds, and specifically the study of computational ability. One of the most promising projects so far is the "Polly Nomial" project on parrot intelligence, run by Dr. Albert B. Tross and his assistants, Clifford Swallow and Perry Keet. In the ACM, parrots are trained to carry out simple polynomial computations involving integers, variables, and simple arithmetic operators.
When shown a formula consisting of a polynomial with non-negative integer coefficients and one variable x, each parrot uses a special beak-operated PDA, or "Parrot Digital Assistant," to tap out a sequence of operations for computing the polynomial. The PDA operates much like a calculator. It has keys marked with the following symbols: the digits from 0 through 9, the symbol 'x', and the operators '+','*', and '='. (The x key is internally associated with an integer constant by Al B. Tross for testing purposes, but the parrot sees only the 'x'.)
For instance, if the parrot were presented with the polynomial
then the parrot would not have been able to \save" the value of x3 while calculating the value of 2x2.Instead, a different order of operations would be needed, for instance:
x, +, 2, , x, *, x, +, 1, 1, =
Input consists of a sequence of lines, each containing a polynomial and an x value. Each polynomial
anxn+an-1xn-1+...+a0 is represented by its degree followed by the non-negative coefficients an , ... , a0 of decreasing powers of x, where an is always 1. Degrees are between 1 and 100. The coefficients are followed on the same line by an integer value for the variable x, which is always either 1 or -1. The input is terminated by a single line containing the values 0 0.
For each polynomial, print the polynomial number followed by the value of the polynomial at the given integer value x and the minimum cost of computing the polynomial; imitate the formatting in the sample output.
3 1 0 1 11 1 3 1 0 2 11 -1 0 0
Polynomial 1: 13 11 Polynomial 2: 8 11
Migrated from old NTUJ.
East Central North America 2003
| No. | Testdata Range | Score |
|---|