465 - Overflow

[Nick]

hi, soyoja!! Your sample output really helped me out.
I use 16 bit compiler running under DOS, had a hard time working on this problem since the judge is using 32 bit compiler

[soyoja]

You're welcome~ ^^;

In this problem, I believe that enough test case make accepted solution.

( Datatype boundary limits are so critical... ^^ )

[Joybo]

[c]
#include <stdio.h>
#include <string.h>

#define INT_MAX 2147483647

void main(void){
long double n1,n2;
char ch[4];

while(scanf("%lf",&n1)==1){
scanf("%s%lf",&ch,&n2);
if(n1>INT_MAX||n2>INT_MAX){
if(n1>INT_MAX) printf("first number too big\n");
if(n2>INT_MAX) printf("second number too big\n");
if(!n1&&!n2) printf("result too big\n");
}else{
if(strcmp(ch,"+")==0&&n1+n2>INT_MAX) printf("result too big\n");
if(strcmp(ch,"*")==0&&n1*n2>INT_MAX) printf("result too big\n");
}
}
}
[/c]

[Joseph Kurniawan]

if(!n1&&!n2) printf("result too big\n");

This means if n1 and n2=0, then the result will be too big???
0+0 = 0
0*0 = 0
??????

And the integers will be arbitrarily long, so I dont kknow if long double can handle these kind of integers (there could be precision errors). If long double doesn't work, try treating the integers as arrays of integers.
Good luck!!!

[gawi]

Following is my code.
I debug again and again.
plz help me , thanx


[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

#define BUF_SIZE 10000

int overflow(char *num) {
const static char *max_int="2147483647";
const static int max_len=10;
int len;

/* remove leading zeros */
while((*num)=='0') num++;
if((*num)=='\0') num--;

len=strlen(num);
if(len>max_len) {
return 1;
}
if(len==max_len && strcmp(num,max_int)>0) {
return 1;
}
return 0;
}

int main() {
char buf[BUF_SIZE],str1[BUF_SIZE],str2[BUF_SIZE],opr[2];
int num1,num2; /* when overflow, $num=-1 */
while(fgets(buf,sizeof(buf),stdin)!=NULL) {
printf("%s",buf);
sscanf(buf,"%s %s %s",str1,opr,str2);
if(overflow(str1)) {
num1=-1;
printf("first number too big\n");
} else
num1=atoi(str1);
if(overflow(str2)) {
num2=-1;
printf("second number too big\n");
} else
num2=atoi(str2);

if(opr[0]=='+') {
if(num1<0 || num2<0)
printf("result too big\n");
else {
if(INT_MAX-num1<num2)
printf("result too big\n");
}
} else if(opr[0]=='*') {
if(num1*num2!=0) { /* Neither num1 and num2 is zero */
if(num1<0 || num2<0)
printf("result too big\n");
else {
if(INT_MAX/num1<num2)
printf("result too big\n");
}
}
}
}
return 0;
}
[/c]

[Shaka_RDR]

hi... i got WA 3 times for this problem... i wonder where's my fault...

here is the sample input i use to work with :

Code: Select all

2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020

and the sample output is :

Code: Select all

2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
result too big
2147483648 * 0
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020

is there any thing wrong ? or there is another tricky input ?

[Shaka_RDR]

hi... i got WA 3 times for this problem... i wonder where's my fault...

here is the sample input i use to work with :

Code: Select all

2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020

and the sample output is :

Code: Select all

2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
result too big
2147483648 * 0
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020

is there any thing wrong ? or there is another tricky input ? thanx before

[Dmytro Chernysh]

Hi Shaka,

Yours output looks ok... But I had a mistake like this
000000000035 + 000000000035
first number too big
second number too big

But it was wrong! Just get rid of leading zeroes.

[Shaka_RDR]

i've found my mistake and i've got AC...

this is my input :

Code: Select all

2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2147483648 * 1
2147483648 + 0
2147483648 * 1
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020
2147483647*2147483647
2147483647+2147483647
1000000*1000000
1000000+1000000
5*2
6+7
0000000000000000000000034+0000000000000000000002
0000000000000000000000034*0000000000000000000002
 

and this is my output :

Code: Select all

2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
2147483648 * 0
first number too big
2147483648 * 1
first number too big
result too big
2147483648 + 0
first number too big
result too big
2147483648 * 1
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
	 350 +      20
   0000350     +    00020
2147483647*2147483647
result too big
2147483647+2147483647
result too big
1000000*1000000
result too big
1000000+1000000
5*2
6+7
0000000000000000000000034+0000000000000000000002
0000000000000000000000034*0000000000000000000002

thanx for the correction....

[Niaz Morshed]

There is an input for which most of the people get WA ! I have corrected many person's code by giving this input. I am giving it here, if any body need more help, then write here, in future i will help again.

2147483648 + -1

Yes, it is possible . Just try it with your code. First number is too big but result is not. Hopefully many of u can get accepted now.

Niaz

[mohiul alam prince]

u can chake this input

input
2147483648 + -1

output
2147483648 + -1
first number too big

prince

[_.B._]

Greetings!.

I've solved it without BigInt.

Maxim

People, try to re-think the problem without the use of BigNums.
It is WAY easier.
Ah!, and a tip, the input lines won't exceed 255 chars
Keep posting!.

[minskcity]

My code gives correct answers for every input posted here... Still WA with the judge... Any sugestions???
[cpp]#include <iostream>
#include <sstream>
#include <string>
using namespace std;

string s1, s2, ss;
char op;
long long n1, n2;
bool f, s, r;

int main(){
while(getline(cin, ss)){
long p = 0;

while(ss[p] == ' ') p++;
while(ss[p] == '0') p++;
if(ss[p] < '0' || ss[p] > '9') p--;

s1 = "";

while(ss[p] >= '0' && ss[p] <= '9')
s1 = s1 + ss[p++];

while(ss[p] == ' ')p++;

op = ss[p++];

while(ss[p] == ' ')p++;
while(ss[p] == '0') p++;
if(ss[p] < '0' || ss[p] > '9') p--;

s2 = "";

while(ss[p] >= '0' && ss[p] <= '9')
s2 = s2 + ss[p++];

f = s = r = false;
n1 = n2 = 1;
if(s1.size() > 15){
f = true;
}else{
istringstream sin(s1);
sin >> n1;
if(n1 > 0x7FFFFFFF) f = true;
}

if(s2.size() > 15){
s = true;
}else{
istringstream sin(s2);
sin >> n2;
if(n2 > 0x7FFFFFFF) s = true;
}

if(!f && !s){
if(op == '*' && n1 * n2 > 0x7FFFFFFF) r = true;
if(op == '+' && n1 + n2 > 0x7FFFFFFF) r = true;
}
r = r || f || s;

if((n1 == 0 || n2 == 0) && op == '*') r = false;

cout << ss << endl;
if(f) cout << "first number too big\n";
if(s) cout << "second number too big\n";
if(r) cout << "result too big\n";

}

return 0;
}
[/cpp]

[minskcity]

u can chake this input

input
2147483648 + -1

output
2147483648 + -1
first number too big

prince

According to problem statement "an expression consisting of two non-negative integer". Is problem description wrong????

[Guest]

Hi,
I'm getting WA for this problem. I've gone through the forum and checked for everything that I found and could think of. I usually don't submit source code, but now I'm getting very confused by all these WAs and that's why I'm submitting my code. Can anyone point out my mistake, please?

Thank you.

Code: Select all

Code Removed
July 18,2004