397 - Equation Elation

Moderator: Board moderators

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

397 - Equation Elation

Help me.
Please someone give the output of these cases :
1 + 1 - 1 + 1 * -1 / 1 = abcd
1 - 2 * -3 = j
-6 - -3 * -3 * -3 / -1 = l
6/-1--1*-2=p

Can the result(or while in process) be overflow from integer variable (>2147483647) ?
And, please give me another tricky inputs.

Thanx for helping me.

Regards,
angga888

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
1 + 1 - 1 + 1 * -1 / 1 = abcd
1 + 1 - 1 + 1 * -1 / 1 = abcd
1 + 1 - 1 + -1 / 1 = abcd
1 + 1 - 1 + -1 = abcd
2 - 1 + -1 = abcd
1 + -1 = abcd
0 = abcd

1 - 2 * -3 = j
1 - 2 * -3 = j
1 - -6 = j
7 = j

-6 - -3 * -3 * -3 / -1 = l
-6 - -3 * -3 * -3 / -1 = l
-6 - 9 * -3 / -1 = l
-6 - -27 / -1 = l
-6 - 27 = l
-33 = l

6/-1--1*-2=p
6 / -1 - -1 * -2 = p
-6 - -1 * -2 = p
-6 - 2 = p
-8 = p

I don't think that would be more tricky outputs ....
I don't worry about overflow ) and I got Accepted

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Still WA.
Your output is exactly same with mine, except for first line of each case. You print the equation twice before the process. Isn't that right ? I have checked with the problem, and there is only one equation to be printed before processing.
And I want to ask whether is it possible that the variable can be at left side ? example : abcde = 1+2 + 3+4
Dominik, what kind of variable did you use to store the result ("long" or "long long") ?
Because I use Pascal as my language, there's no variable like long long in Pascal.
If you use "long long", please submit it again with "long" variable in result. Still Accepted ?

Regards,
angga888

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I use long ....
Twice because I post output from command line ....

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
I have tried to modify my code and sent it again and again, but still WA.
Dominik, if you don't mind, could you send your 397.exe file to me (angga888@indosat.net.id), so I can re-check my output according to yours.
Thanks.

Regards,
angga888

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Dominik, thanks a lot for your 397.exe file. After I received your exe file, I checked again my output. And finally, I found some little bug in my output that makes my output different with yours. I fixed it and now I got Accepted
Thank you very much Dominik.

Regards,
angga888

rosynirvana
New poster
Posts: 4
Joined: Thu Oct 03, 2013 10:16 pm

Re: 397 Equation Elation - WA

It seems that unary '+' must be removed before the 1st output.

Int the 3rd and 4th example
2 * -3 + -6 - +4 = r
->
2 * -3 + -6 - 4 = r

If you parse the string and store the ops this won't be a problem. But I use a quite dumb algorithm in my code(find a operator and then scan forward and backward) and it won't remove unary '+'. I got a WA the first time. Some code removing unary '+' was added and I got AC.

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 397 - Equation Elation

Why TLE ???

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include <ctype.h>
#include<cassert>
#include <sstream>
using namespace std;

/*------- Constants---- */
#define MX 130000
#define ll long long
#define ull unsigned long long
#define mod 1000000007

/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}

char in[100],var[100];
vector<int> oprd,op;
char mappin[1000];

void print()
{
for (int i=0; i<op.size(); i++) {
printf("%d %c ",oprd[i],mappin[op[i]]);
}
printf("%d = %s\n",oprd[op.size()],var);
return;
}
int main()
{
int res=0,flag=0,sign=1,first=0;
mappin[1] = '+';
mappin[2] = '-';
mappin[3] = '*';
mappin[4] = '/';
while (gets(in)!=NULL) {
if(in[0]=='\0') break;
for (int i=0,k=0; in[i]; i++) {
if(in[i]=='-'&& in[i+1]>='0' && in[i+1]<='9') {sign=-1;continue;}
if(in[i]=='+' && in[i+1]>='0' && in[i+1]<='9') {sign=1;continue;}
if(in[i]>='0' && in[i]<='9'){
flag=1;
res = res*10 + in[i]-'0';
}
else {
if(flag)oprd.push_back(sign*res);
res=0;
sign=1;
flag=0;
if(in[i]=='+') op.push_back(1);
if(in[i]=='-') op.push_back(2);
if(in[i]=='*') op.push_back(3);
if(in[i]=='/') op.push_back(4);
if(in[i]=='=') {
for ( k=i+1; !isalpha(in[k]); k++);
for ( int p=0; ; k++,p++) {
var[p] = in[k];
if(!in[k]) break;
}
break;
}
}
}
if(first) printf("\n");
first=1;
print();
int sum=0;
while (oprd.size()>1) {
sum=0;
for (int i=0; i<op.size(); i++) {
if(op[i]==3 || op[i]==4){
if(op[i]==3) oprd[i+1] = oprd[i]*oprd[i+1];
else oprd[i+1] = oprd[i]/oprd[i+1];
op.erase(op.begin()+i);
oprd.erase(oprd.begin()+i);
print();
sum=1;
break;

}
}
if (sum==0) {
for (int i=0;op.size()>=1;) {
if(op[i]==1 || op[i]==2){
if(op[i]==1)oprd[i+1] = oprd[i]+oprd[i+1];
else oprd[i+1] = oprd[i]-oprd[i+1];
op.erase(op.begin()+i);
oprd.erase(oprd.begin()+i);
print();
break;

}
}
}

}
op.clear();
oprd.clear();
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 397 - Equation Elation

Here is how I solved it:
Read a line of input, strip all spaces, store the variable name after the =.
Strip all unary +: start of line, ++, -+, *+, or /+
Parse the line, first each constant (with or without unary -) followed by operator (except for last constant).
Print the line.
Iterate through and perform each * or / and print at each step.
Iterate through and perform each + or - and print at each step.

Try following my algorithm. Why do you have this line: "while (oprd.size()>1) {". You should only need two passes through the equation.
Check input and AC output for thousands of problems on uDebug!