The well-known physicist Alfred E Neuman is working on problems that
involve multiplying polynomials of x and y. For example, he may need to
calculate
getting the answer
Unfortunately, such problems are so trivial that the great man's mind keeps
drifting off the job, and he gets the wrong answers. As a consequence,
several nuclear warheads that he has designed have detonated prematurely,
wiping out five major cities and a couple of rain forests.
You are to write a program to perform such multiplications and save the
world.
The file of input data will contain pairs of lines, with each line containing
no more than 80 characters. The final line of the input file contains a
# as
its first character. Each input line contains a polynomial written without
spaces and without any explicit exponentiation operator. Exponents are
positive non-zero unsigned integers. Coefficients are also integers, but may
be negative. Both exponents and coefficients are less than or equal to 100
in magnitude. Each term contains at most one factor in x and one in y.
Your program must multiply each pair of polynomials in the input, and print
each product on a pair of lines, the first line containing all the exponents,
suitably positioned with respect to the rest of the information, which is in
the line below.
The following rules control the output format:
- Terms in the output line must be sorted in decreasing order of powers
of x and, for a given power of x, in increasing order of powers of y.
- Like terms must be combined into a single term. For example,
40x2y3
- 38x2y3 is replaced by 2x2y3.
- Terms with a zero coefficient must not be displayed.
- Coefficients of 1 are omitted, except for the case of a constant term
of 1.
- Exponents of 1 are omitted.
- Factors of x0 and y0 are omitted.
- Binary pluses and minuses (that is the pluses and minuses connecting
terms in the output) have a single blank column both before and after.
- If the coefficient of the first term is negative, it is preceded by a
unary minus in the first column, with no intervening blank column.
Otherwise, the coefficient itself begins in the first output column.
- The output can be assumed to fit into a single line of at most 80
characters in length.
- There should be no blank lines printed between each pair of output
lines.
- The pair of lines that contain a product should be the same
length--trailing blanks should appear after the last non-blank character
of the shorter line to achieve this.
-yx8+9x3-1+y
x5y+1+x3
1
1
#
13 2 11 8 6 5 5 2 3 3
-x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y
1
一次都會輸出兩行,且兩行的長度要相同,不夠長的那一方要補空白。
因此範例輸出是錯的,參考一下就行了。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
struct F {//factor
int k, x, y;
F(int a, int b, int c):
k(a), x(b), y(c) {}
bool operator<(const F &a) const {
if(x != a.x)
return x > a.x;
return y < a.y;
}
};
vector<F> parsePoly(char s[]) {
vector<F> ret;
int i, len = strlen(s);
for(i = 0; i < len;) {
int sign = 1, k, x, y;
if(s[i] == '-')
sign = -1, i++;
if(s[i] == '+')
sign = 1, i++;
if(s[i] >= '0' && s[i] <= '9') {
k = 0;
while(s[i] >= '0' && s[i] <= '9')
k = k*10 + s[i]-'0', i++;
} else
k = 1;
x = 0, y = 0;
if(s[i] == 'x') {
i++;
if(s[i] >= '0' && s[i] <= '9') {
x = 0;
while(s[i] >= '0' && s[i] <= '9')
x = x*10 + s[i]-'0', i++;
} else
x = 1;
}
if(s[i] == 'y') {
i++;
if(s[i] >= '0' && s[i] <= '9') {
y = 0;
while(s[i] >= '0' && s[i] <= '9')
y = y*10 + s[i]-'0', i++;
} else
y = 1;
}
if(s[i] == 'x') {
i++;
if(s[i] >= '0' && s[i] <= '9') {
x = 0;
while(s[i] >= '0' && s[i] <= '9')
x = x*10 + s[i]-'0', i++;
} else
x = 1;
}
ret.push_back(F(k*sign, x, y));
}
return ret;
}
int main() {
char s[105];
while(scanf("%s", s) == 1) {
if(s[0] == '#')
break;
vector<F> A, B;
A = parsePoly(s);
scanf("%s", s);
B = parsePoly(s);
map<F, int> ret;
for(vector<F>::iterator it = A.begin();
it != A.end(); it++) {
for(vector<F>::iterator jt = B.begin();
jt != B.end(); jt++) {
int x = it->x + jt->x, y = it->y + jt->y;
F IDX(0, x, y);
ret[IDX] += it->k * jt->k;
}
}
char out[2][1005] = {};
int oidx1 = 0, oidx2 = 0;
int first = 0;
for(map<F, int>::iterator it = ret.begin();
it != ret.end(); it++) {
if(it->second == 0) continue;
if(first && it->second > 0) {
out[1][oidx2++] = ' ';
out[1][oidx2++] = '+';
out[1][oidx2++] = ' ';
}
if(it->second < 0) {
if(first) {
out[1][oidx2++] = ' ';
out[1][oidx2++] = '-';
out[1][oidx2++] = ' ';
} else {
out[1][oidx2++] = '-';
}
it->second = -(it->second);
}
first = 1;
if(it->second != 1 || (it->first.x == 0 && it->first.y == 0)) {
sprintf(out[1]+oidx2, "%d", it->second);
while(out[1][oidx2]) oidx2++;
}
if(it->first.x) {
out[1][oidx2++] = 'x';
if(it->first.x > 1) {
while(oidx1 < oidx2)
out[0][oidx1++] = ' ';
sprintf(out[0]+oidx1, "%d", it->first.x);
while(out[0][oidx1])
oidx1++;
while(oidx2 < oidx1)
out[1][oidx2++] = ' ';
}
}
if(it->first.y) {
out[1][oidx2++] = 'y';
if(it->first.y > 1) {
while(oidx1 < oidx2)
out[0][oidx1++] = ' ';
sprintf(out[0]+oidx1, "%d", it->first.y);
while(out[0][oidx1])
oidx1++;
while(oidx2 < oidx1)
out[1][oidx2++] = ' ';
}
}
while(oidx1 < oidx2)
out[0][oidx1++] = ' ';
while(oidx2 < oidx1)
out[1][oidx2++] = ' ';
}
puts(out[0]);
puts(out[1]);
}
return 0;
}
/*
-yx8+9x3-1+y
x5y+1+x3
*/
文章定位: