465 - Overflow

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

Moderator: Board moderators

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

thank you

Post by Nick » Tue Jul 29, 2003 7:59 am

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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Tue Jul 29, 2003 4:57 pm

You're welcome~ ^^;

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

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

Joybo
New poster
Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

[465]I got wa!

Post by Joybo » Tue Sep 23, 2003 12:09 pm

[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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Fri Sep 26, 2003 7:20 am

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!!! :wink: :wink:
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

gawi
New poster
Posts: 3
Joined: Sun Jul 13, 2003 10:19 am
Location: Taiwan

problem 465 why wa ?

Post by gawi » Sat Oct 18, 2003 9:38 am

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


[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]

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Nov 13, 2003 3:44 am

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 ?
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Nov 13, 2003 3:45 am

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
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Fri Nov 14, 2003 3:30 am

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.

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Sat Nov 15, 2003 10:12 am

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.... :D
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

Post by Niaz Morshed » Sun Nov 23, 2003 12:52 am

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 :o . Just try it with your code. First number is too big but result is not. Hopefully many of u can get accepted now.

Niaz :P
The Last Man Standing :-)

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sat Feb 07, 2004 4:54 pm

u can chake this input

input
2147483648 + -1

output
2147483648 + -1
first number too big

prince

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

The math way.

Post by _.B._ » Sat May 29, 2004 8:25 pm

Greetings!.
Maxim wrote: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 :D
Keep posting!.
_.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Jun 11, 2004 2:40 am

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Jul 10, 2004 6:04 am

mohiul alam prince wrote: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
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Fri Jul 16, 2004 1:59 pm

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? :cry:

Thank you.

Code: Select all

Code Removed
July 18,2004
Last edited by on Sun Jul 18, 2004 5:54 am, edited 1 time in total.

Post Reply

Return to “Volume 4 (400-499)”