编程介的小学生 2017-09-18 10:57 采纳率: 20.5%
浏览 619
已采纳

Polly Nomials

Description

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
x3 + x + 11

the parrot might tap the following sequence of symbols:
x, *, x, *, x, +, x, +, 1, 1, =

The PDA has no extra memory, so each * or + operation is applied to the previous contents of the display and whatever succeeding operand is entered. If the polynomial had been
x3 + 2x2 + 11

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, =

The cost of a calculation is the number of key presses. The cost of computing x3+x+11 in the example above is 11 (four presses of the x key, two presses of '*', two presses of '+', two presses of the digit '1',and the '=' key). It so happens that this is the minimal cost for this particular expression using the PDA.
You are to write a program that finds the least costly way for a parrot to compute a number of polynomial expressions. Because parrots are, after all, just bird-brains, they are intimidated by polynomials whose high-order coefficient is any value except 1, so this condition is always imposed.
Input

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.
Output

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.
Sample Input

3 1 0 1 11 1
3 1 0 2 11 -1
0 0
Sample Output

Polynomial 1: 13 11
Polynomial 2: 8 11

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-10-03 02:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 易语言把MYSQL数据库中的数据添加至组合框
  • ¥20 求数据集和代码#有偿答复
  • ¥15 关于下拉菜单选项关联的问题
  • ¥20 java-OJ-健康体检
  • ¥15 rs485的上拉下拉,不会对a-b<-200mv有影响吗,就是接受时,对判断逻辑0有影响吗
  • ¥15 使用phpstudy在云服务器上搭建个人网站
  • ¥15 应该如何判断含间隙的曲柄摇杆机构,轴与轴承是否发生了碰撞?
  • ¥15 vue3+express部署到nginx
  • ¥20 搭建pt1000三线制高精度测温电路
  • ¥15 使用Jdk8自带的算法,和Jdk11自带的加密结果会一样吗,不一样的话有什么解决方案,Jdk不能升级的情况