288 - Arithmetic Operations With Large Integers
Moderator: Board moderators
- Christian Schuster
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 am
288 - Arithmetic Operations With Large Integers
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
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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?
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?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
- Christian Schuster
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 am
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
288 - compile error
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>
,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>
288 - Runtime Error
This problem seems to be quite easy. But my program kept getting Rutime error.
I wonder if there are some tricky input cases?
I wonder if there are some tricky input cases?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany