397 - Equation Elation

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

Moderator: Board moderators

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

397 - Equation Elation

Post by angga888 » Thu Feb 13, 2003 2:29 pm

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

Regards,
angga888

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Feb 13, 2003 2:59 pm

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)

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

Post by angga888 » Fri Feb 14, 2003 6:14 am

Still WA. :cry:
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:

Post by Dominik Michniewski » Fri Feb 14, 2003 10:59 am

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)

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

Post by angga888 » Sat Feb 15, 2003 5:53 am

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

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

Post by angga888 » Tue Feb 18, 2003 3:30 pm

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

Post by rosynirvana » Thu Nov 07, 2013 11:48 am

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

Post by Repon kumar Roy » Sat Aug 16, 2014 12:10 am

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

Post by brianfry713 » Thu Aug 21, 2014 11:20 pm

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!

Post Reply

Return to “Volume 3 (300-399)”