126 - The Errant Physicist

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fommil
New poster
Posts: 2
Joined: Mon Jul 26, 2004 12:11 pm
Location: Edinburgh
Contact:

Post by fommil » Mon Jul 26, 2004 1:38 pm

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 :D

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

#126. Is the sample output right?

Post by ImLazy » Tue Feb 15, 2005 1:22 pm

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?
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Wed Feb 23, 2005 9:12 am

No reply again. But that doesn't matter. I have got AC so the sample output is proved to be wrong.
I stay home. Don't call me out.

User avatar
GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:

Post by GVahe » Fri Feb 25, 2005 11:19 am

Can you give me some test cases for this problem?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jul 17, 2005 1:36 am

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 :D .
Ami ekhono shopno dekhi...
HomePage

anala_sridhar
New poster
Posts: 4
Joined: Thu Jul 08, 2004 12:53 pm
Contact:

Post by anala_sridhar » Wed Nov 29, 2006 5:06 am

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. :D :D

enyangh
New poster
Posts: 1
Joined: Wed Apr 25, 2007 10:09 am

126 [The Errant Physicist] WA on 10 trials

Post by enyangh » Wed May 02, 2007 4:29 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 02, 2007 7:31 pm

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

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Post by Ron » Sat Aug 18, 2007 9:30 am

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

:D Surendra Kumar Meena :D

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 126 The Errant Physicist

Post by Hikari9 » Thu Aug 22, 2013 7:08 pm

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 :D

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
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 126 - The Errant Physicist

Post by rafastv » Sat Jun 24, 2017 8:42 am

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.

Post Reply

Return to “Volume 1 (100-199)”