126 - The Errant Physicist

[fommil]

it is OK!! i found the bug. my array was 100x100, but of course the maximum output can have exponents up to 200, so i just made the standard size of my array larger. accepted

[ImLazy]

In the problemset it is said :"blanks should appear after the last non-blank character of the shorter line to achieve this". However, there is no more blank at the end of the first line of the sample output.
Moreover, there is one blank at the end of the second line of sample output.
Is that all right?

[ImLazy]

No reply again. But that doesn't matter. I have got AC so the sample output is proved to be wrong.

[GVahe]

Can you give me some test cases for this problem?

[Jan]

Hey Farid Ahmadov, try the following input set..

Input:

Code: Select all

x2
y-y
x2y2+3xy-4
x2-3x3+x5
24x-67xy7
-x5
x32+y21+2x3y42-1
-x
x0y0
1
-x6y6
x8y8+x7y9+x2-98
#

And the output is
Output:

Code: Select all

0
 7 2     6      5     5 2     4     4 2      3     3      2
x y  + 3x y - 4x  - 3x y  - 9x y + x y  + 12x  + 3x y - 4x
    6      6 7
-24x  + 67x y
  33     4 42         21
-x   - 2x y   + x - xy

1
  14 14    13 15    8 6      6 6
-x  y   - x  y   - x y  + 98x y

Hope it helps .

[anala_sridhar]

Hi Jan,
you sure are a great helper.
your sample input set helped me fix the bug and got the solution "accepted" but with "presentation error". dunno why?

anyways, thanks a ton.

[enyangh]

Hi, I have no idea on why my program keeps getting WA. Can anyone help? Or putting some extreme testing cases?

For input
-----------------------------
-yx8+9x3-1+y
x5y+1+9x3
1
1
99x99+99y99
99x99-99y99
99x99+99y99
99x99+99y99
-yx8+7x7y5-8x3-2x2
x5y+1+4x3
3yx-2xy
-x5y-4x3+8x100y100
-1x1
-x100
x2
y-y
x2y2+3xy-4
x2-3x3+x5
24x-67xy7
-x5
x32+y21+2x3y42-1
-x
x0y0
1
-x6y6
x8y8+x7y9+x2-98
0
22
#
------------------------------
My output is
-----------------------------
13 2 11 8 6 5 5 2 3
-x y - 9x y + 8x y + 81x - x y + x y + 9x y - 1 + y

1
198 198
9801x - 9801y
198 99 99 198
9801x + 19602x y + 9801y
13 2 12 6 11 10 5 8 7 7 5 6 5 3 2
-x y + 7x y - 4x y + 28x y - 9x y - 2x y + 7x y - 32x - 8x - 8x - 2x
101 101 6 2 4
8x y - x y - 4x y
101
x


7 2 6 5 5 2 4 4 2 3 3 2
x y + 3x y - 4x - 3x y - 9x y + x y + 12x + 3x y - 4x
6 6 7
-24x + 67x y
33 4 42 21
-x - 2x y + x - xy

1
14 14 13 15 8 6 6 6
-x y - x y - x y + 98x y

----------------------------------------------

My code is:

-----------------------------------------------

#include <iostream>
#include <map>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
using namespace std;


map<pair<int,int>,int> eqMap;


int isNum(char c){
return (c>=48&&c<=57);

}

class term{
public:
int x,y,coe;
term(int x1, int y1, int coe1){
x=x1; y=y1;coe=coe1;
}
};

vector<term> world[2];



void parse(string s, int in){
// cout<<"str:["<<s<<"]"<<endl;
int x=0,y=0,coe=1;
for(int i=0;i<s.size();){
// cout<<"i:"<<i<<endl;
if(s=='-'){
coe*= -1;
i++;
}else if(s=='+'){
coe *= 1;
i++;
}else if(s=='x'){
x=1;
i++;
if(isNum(s)){x=0;}
while(i<s.size() && isNum(s)){
x=x*10+(s-'0');
i++;
}
}else if(s=='y'){
y=1;
i++;
if(isNum(s)){y=0;}
while(i<s.size() && isNum(s)){
y=y*10+(s-'0');
i++;
}
}else{
assert(isNum(s[i]));
//cout<<"["<<s[i]<<"]"<<endl;
int absCoe = 0;
while(i<s.size() && isNum(s[i])){
absCoe=absCoe*10+(s[i]-'0');
i++;
}
// cout<<"abscod:"<<absCoe<<" "<<i<<" "<<s.size()<<endl;
coe *= absCoe;
}
}
world[in].push_back(term(x,y,coe));

// cout<<"coe:"<<coe<<" "<<x<<" "<<y<<endl;
}



int readLine(int in){
char l[90];
cin.getline(l,90);
string s(l);

if(s=="#"){return 0;}

string seg;
for(int i=0;i!=s.size();i++){
seg.push_back(s[i]);
if(s[i+1]=='+' || s[i+1]=='-' || i+1==s.size()){
parse(seg,in);
seg="";
}
}
return 1;
}


int read(){
if(!readLine(0)){return 0;}
if(!readLine(1)){return 0;}
return 1;
}

void mul(term & t1, term & t2, int &x, int &y, int &coe){
coe = t1.coe*t2.coe;
x=t1.x+t2.x;
y=t1.y+t2.y;
}

int cmp(term a, term b){
if(a.x<b.x){return 0;}
else if(a.x>b.x){return 1;}
else{
assert(a.x==b.x);
if(a.y<b.y){return 1;}
else{return 0;}
}
}

void dig(){
for(int i=0;i!=world[0].size();i++){
for(int j=0;j!=world[1].size();j++){
int x,y,coe;
mul(world[0][i],world[1][j],x,y,coe);
pair<int,int> xy(x,y);
if(eqMap.find(xy)==eqMap.end()){
if(coe!=0){
eqMap.insert(pair<pair<int,int>,int >(xy,coe));
}
}else{
eqMap.find(xy)->second +=coe;
if(eqMap.find(xy)->second==0){eqMap.erase(eqMap.find(xy));}
}
}
}

vector<term> t;
for(map<pair<int,int>,int>::iterator i=eqMap.begin();i!=eqMap.end();++i){
t.push_back(term(i->first.first,i->first.second,i->second));
}

sort(t.begin(),t.end(),cmp);
stringstream ss;
for(vector<term>::iterator i=t.begin();i!=t.end();++i){
if(i->coe<0){
if(i->coe==-1){
if(i->x==0&&i->y==0){ss<<" - 1";}
else if(i!=t.begin()){ss<<" - ";}
else{ss<<"-";}
}else{
if(i==t.begin()){ss<<i->coe;}
else{ss<<" - "<<abs(i->coe);}
}
}else{
if(i->coe==1){
if(i->x==0&&i->y==0 && i!=t.begin()){ss<<" + 1";}
else if(i->x==0&&i->y==0 && i==t.begin()){ss<<i->coe;}
else if(i==t.begin()){}
else{ss<<" + ";}
}else{
if(i!=t.begin()){
ss<<" + "<<i->coe;
}else{
ss<<i->coe;
}
}
}



if(i->x>=1){
ss<<"x";
if(i->x>1){
ss<<i->x;
}
}

if(i->y>=1){
ss<<"y";
if(i->y>1){
ss<<i->y;
}
}
}

char c;
int state = 0;
for(int i=0;i!=ss.str().size();i++){
c = ss.str()[i];
if(c=='+' || c=='-'){state = 0;}
else if((c=='x' || c=='y')){state = 1;}
if(isNum(c) && state==1){cout<<c;}
else{cout<<" ";}
}
cout<<endl;


state = 0;
for(int i=0;i!=ss.str().size();i++){
c = ss.str()[i];
if(c=='+' || c=='-'){state = 0;}
else if((c=='x' || c=='y')){state = 1;}
if(isNum(c)&&state==1){cout<<" ";}
else{cout<<c;}
}
// if(t.size()==0){cout<<0;}

cout<<endl;

// cout<<t.size()<<" "<< t.front().x<<" "<<t.front().y<<" "<<t.front().coe<<endl;


eqMap.clear();
world[0].clear();
world[1].clear();
}
int main(){
while(read()){
dig();
}
}
;

[Jan]

Search the board first. Don't open a new thread if there is one already. And when posting a code use code tags.

[Ron]

Some input cases :-

1
1+x0
99x99+99y99
99x99-99y99
-1x1
-x100+0
6x1
3y-3y
x-x
y
x2y3+1
0
0
x2-2x3y0+x5
x2-2x3y0+x5
1
x0
1
#


Output of my accepted program :-

2
198 198
9801x - 9801y
101
x
0
0
0
0
5 3 2
x - 2x + x

1


Hope it will help you...........

Surendra Kumar Meena

[Hikari9]

For everyone getting Presentation Error,
apparently the judge program doesn't trim any trailing spaces... the heck -_-

I hope that the judge would fix their mistake.
In any case, matching this input/output would help

Sample Input:

Code: Select all

x2
y-y
x2y2+3xy-4
x2-3x3+x5
24x-67xy7
-x5
x32+y21+2x3y42-1
-x
x0y0
1
-x6y6
x8y8+x7y9+x2-98
-yx8+9x3-1+y
x5y+1+x3
1
1
0
0
#

Sample Output:

Code: Select all

 
0
 7 2     6      5     5 2     4     4 2      3     3      2
x y  + 3x y - 4x  - 3x y  - 9x y + x y  + 12x  + 3x y - 4x 
    6      6 7
-24x  + 67x y 
  33     4 42         21
-x   - 2x y   + x - xy  
 
1
  14 14    13 15    8 6      6 6
-x  y   - x  y   - x y  + 98x y 
  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
 
0

[rafastv]

Just so somebody else knows, my code do not print zeros (as the problem states and got AC'd). And my solution got AC when I increased the numbers' range that my code is able to handle, regardless of what the problem says.