288 - Arithmetic Operations With Large Integers

All about problems in Volume 2. 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
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

288 - Arithmetic Operations With Large Integers

Post by Christian Schuster » Sat Apr 27, 2002 8:43 pm

Hello World,

I tried to get AC for that one several times, but no way...

I'm currently using term splitting, scanning for "+" and "-" from the right (they associate left), afterwards for "*" from the right (dito) and for "**" (which I replaced before) from the left (right associative). I'm then calling that thing recursively. If no operator is found, it's a simple number, where I remove leading zeroes and return.

My program seems to work quite correct for all of my test cases, so I'm sure there's some tricky input. BTW: What's the result of 0**0?

Could someone help me? Any hints?

Here are some (in my opinion) critical samples:
3**4**2 => 43046721
000333-0001000 => -667
3-5+2 => 0
2**9999-4**4999*2 => 0
Last edited by Christian Schuster on Sat Apr 27, 2002 9:12 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Apr 27, 2002 9:09 pm

I have to add some questions:
What about 0**0**0? And 1-2**2?
And I hope that I did understand it right that there is not a input like -2*-2.
I also print the result in a line, not in several lines like in the sample output, because the description says: "Print each test case in a different line."
I remove leading zeros all time, even directly before output, and I print 0 if the result is 0.
What could be the reason that I get Wrong Answer?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Apr 27, 2002 9:18 pm

Now I got Accepted. I forgot to store the sign correctly for the result after addition. If the mentioned cases are in the input, then:
0**0 = 1
0**0**0 = 0
1-2**2 = -3
and the other results are like Christian wrote.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Sat Apr 27, 2002 10:30 pm

I finally got AC - forgot to reset the sign flag in multiplication... :-?

Thanks for the inspiration... :D

ha_tran
New poster
Posts: 1
Joined: Sat May 04, 2002 1:30 am

Post by ha_tran » Sat May 04, 2002 1:32 am

I can't understand why I got it right with all of your results above, however, it's still not AC.
Is there any trick in the input?

bluna
New poster
Posts: 3
Joined: Mon May 27, 2002 9:09 am
Location: Slovenia

Post by bluna » Mon May 27, 2002 9:11 am

I don't know what to do!
On my computer it works just fine, but when I send it, it always, and I mean ALWAYS, come back the SIGSEGV error:
Invalid memory reference!!

Have you got any ideas, what is wrong??

Bye

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon May 27, 2002 11:52 am

I think, you are solving the problem recursively. Therefore you have to try that your recursion depth is as small as possible to avoid stack overflow.

bluna
New poster
Posts: 3
Joined: Mon May 27, 2002 9:09 am
Location: Slovenia

Post by bluna » Tue May 28, 2002 12:51 pm

I had a solution with recurision, but when I got runtime error message, I changed it into non-recursion way.

bluna
New poster
Posts: 3
Joined: Mon May 27, 2002 9:09 am
Location: Slovenia

Post by bluna » Tue May 28, 2002 12:51 pm

I had a solution with recurision, but when I got runtime error message, I changed it into non-recursion way.
10x anyway for suggestion

bbio_bibo
New poster
Posts: 1
Joined: Wed Jul 31, 2002 7:12 pm
Location: Taipei
Contact:

288 - compile error

Post by bbio_bibo » Wed Jul 31, 2002 7:24 pm

I reveived the reply telling me "Compile Error"
,but those errors occur in some *.h files
I don't quite understand how this could happen.

I have tried using "operator overload" or "member function only"
but all have error like - "const BigInteger" etc.

partial messages are as below:
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h: In instantiation of `iterator_traits<BigInteger>':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_al
go.h:257: instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h:104: no type named `iterator_category' in `class BigInteger'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h:105: no type named `value_type' in `class BigInteger'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h:106: no type named `difference_type' in `class BigInteger'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h:107: no type named `pointer' in `class BigInteger'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_it
erator.h:108: no type named `reference' in `class BigInteger'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_al
go.h: In function `int main(...)':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++3/stl_al
go.h:257: no type named `difference_type' in `struct iterator_traits<BigInteger>

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

288 - Runtime Error

Post by potato » Sat Nov 01, 2003 5:31 pm

This problem seems to be quite easy. But my program kept getting Rutime error.
I wonder if there are some tricky input cases?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu May 27, 2004 4:00 am

Sorry, I tried to solve the problem and get WA all the time.
I have passed all the input/output above.
Could someone give more tircky Input/Output? Thx :D

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu May 27, 2004 11:51 am

Perhaps the following information helps you:
There may be more than 2500 digits in a (intermediate) result, but never more than 3000 digits.
Each input line contains at most 200000 characters.
And there may be leading zeros.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Mar 26, 2006 6:53 am

So I keep getting WA. I implemented, but didn't post, a class Z which is meant to be an arbitrary precision integer class (it is meant to act like int, overloaded operaters etc.). I'm pretty sure the +,* and - work with the Z class, since I've used it on other problems. ** also seems to work (I tested it with quite a few powers of 2). Could there be a problem with the parsing?

Code: Select all

string parse(string);
Z expression(istream&);
Z term(istream&);
Z factor(istream&);

int main(){
  string s;
  while(getline(cin,s)){
    istringstream sin(parse(s));
    ostringstream sout;
    sout<<expression(sin);
    s=sout.str();
    //while(s.size()>75){ cout<<s.substr(0,75)<<"\\\\\n"; s=s.substr(75); }
    cout<<s<<'\n';
  }
}

Z expression(istream& in){
  Z a=term(in);
  char op;
  while(in>>op){
    Z b=term(in);
    if(op=='+')
      a+=b;
    else
      a-=b;
  }
  return a;
}

Z term(istream& in){
  Z a=factor(in);
  while(in.peek()=='*'){
    in.get();
    Z b=factor(in);
    a*=b;
  }
  return a;
}

Z factor(istream& in){
  Z a;
  in>>a;
  if(in.peek()=='^'){
    in.get();
    Z b=factor(in);
    a^=b;
  }
  return a;
}

string parse(string s){
  string t;
  for(int i=0;i<s.size();i++)
    if(s[i]=='*' && i+1<s.size() && s[i+1]=='*'){
      t+='^'; i++;
    }else
      t+=s[i];
  return t;
}
I'm always willing to help, if you do the same.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Mar 27, 2006 3:16 pm

I think your parsing looks good. The only thing which I can see which may cause some problems is a leading unary -, for example:
-200+1
I don't know if something like this occurs in the judge input, but my program handles it.
Edit: I just read that such a case would be invalid.

Post Reply

Return to “Volume 2 (200-299)”