10494 - If We Were a Child Again

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

10494 - If We Were a Child Again

Post by Subeen » Thu May 29, 2003 8:05 am

I got WA in this problem. But can't find bugs in my programs. :(
Someone please give me some test input/output to test my program.
thanks...

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Thu May 29, 2003 9:49 am

input :

Code: Select all

234098720432984729 / 234923845
24324 / 2342
output :
check with calculator.

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

Post by Dominik Michniewski » Thu May 29, 2003 11:58 am

try also input which are longer than i.e. 20 characters and second input number is near to 2^31

Best regards
DM
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)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu May 29, 2003 3:39 pm

"The first one (number) may be arbitrarily long."

How long will it approximately be? 100 chrs? Or more?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Dominik Michniewski » Thu May 29, 2003 3:52 pm

I assume that not longer that 2048 digits .... :)

Best regards
DM
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 May 30, 2003 6:22 am

1000 is enough.

Try for these input :

Code: Select all

0 / 2147483647 = 0
0 % 2147483647 = 0
2147483646 % 2147483647 = 2147483646
Good Luck :D


angga888

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Fri May 30, 2003 10:50 am

Note that 32-bit integer is not enough to solve this problem. If B = 2^31 - 1, then the dividend could be too larger for a 32-bit integer to handle.

So, check this out:
99999999999999999999 / 2147483647

Result should be:
46566128752

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri May 30, 2003 10:51 pm

finally got accepted using long long int type variable.

thanks to all for their help :lol:

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

Post by sunhong » Sun Jun 08, 2003 6:54 am

I got several WA at this problem! But I can't find anything wrong in my program. And here is my code, please tell me what is incorrect. Thank you!

Code: Select all

#include <iostream.h>
#include <math.h>
#include <iomanip.h>

int main()
 {long double a,b,result;
  char ch;
  while (cin>>a)
   {cin>>ch;
    while (ch!='/' && ch!='%') cin>>ch;
    cin>>b;
    if (ch=='/') result=a/b;
    else result=fmod(a,b);
    cout<<setiosflags(ios::fixed);
    cout<<setprecision(0)<<result<<endl;
   }
  return 1;
 }   

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jun 08, 2003 7:00 am

Your program is surely wrong. -_-;

The input specifies that the first number to be arbitrarily large (Actually I think the test case contains numbers up to 1000 digits or so), but the long double variable's precision is not up to that.

You should implement bigint operation here. Read what is written so far.
JongMan @ Yonsei

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

Post by sunhong » Sun Jun 08, 2003 12:19 pm

Thank you for your reply, but I'm not familiar with the bigint operation. So I don't know which datatype I should use to caculate the result, can you tell me please?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jun 08, 2003 1:14 pm

Sure, why not. :)

You should use arrays to simulate the array as big integers. (when a[0] = 123 and a[1] = 456, these can be interpreted as 123456)
In case using strings as numbers are feasible, too.

Of course C or Pascal syntaxes do not support operations like these, so you should implement your own calculating functions like addition, subtraction, multiplication, .. etc.

There are algorithms to do operations of bigints faster than simulating hand operations (I believe there is one at Knuth's book), but in most cases, brute force operations are feasible.

For further info, try a search in this board using 'bigint' as the keyword.
Hope this helps.
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jul 11, 2003 12:53 pm

Excuse me...

Can the result be stored in any data type (except BigInt)? :-?


(I should think no........)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Jul 12, 2003 8:40 am

I didn't use a full BigInt class for this (because in a real contest, I wouldn't have brought one..)

But basically, you read in the first number as a string, the second number as an unsigned int, and then just output the thing in place.. it's pretty simple, since for %, it's obvious that the solution can fit in unsigned int, while you can use normal division rule..

User avatar
babor
New poster
Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm
Contact:

10494

Post by babor » Mon Sep 15, 2003 11:15 am

Hai guies I am fool at wa of 10494.
is my function wrong or where is wrong handling.
My code is
/*
/* @JUDGE_ID: XXXXXX 10494 C++ */
#include <stdio.h>
#include <string.h>
#define MAX 100000

unsigned long Modulas(char a[],unsigned long denomi)
{

unsigned long rim,len,i;
rim = (a[0] - 48 )%denomi;
len = strlen(a);
for(i=1;i<len;i++)
rim = ( 10*rim + (a - 48) )%denomi;
return rim;
}


char* String_divide(char a[],unsigned long denomi)
{
char res[MAX];
unsigned long rim,len,i,start,q=0;
rim =a[0]-48;
len = strlen(a);
for(i=1;i<len;i++)
{
rim = rim*10 + a-48;
if(rim>=denomi)
{
start = i;
break;
}
}

res[q++] = (rim/denomi) + 48;
rim = rim%denomi;
for(i=start+1;i<len;i++)
{
rim = ( 10*rim + (a - 48) );
res[q++] = (rim/denomi) + 48;
rim = rim%denomi;
}
res[q]=0;
return res;

}

void main()
{

char a[MAX],sign[3],result[MAX];
unsigned long rim,denomi;
while(scanf("%s %s %lu",a,sign,&denomi)==3)
{

if(strcmp(sign,"%")==0)
{

rim = Modulas(a,denomi);
printf("%lu\n",rim);
}
else
{
strcpy(result,String_divide(a,denomi));
printf("%s\n",result);
}

}

}
/*@END_OF_SOURCE_CODE*/




*/
babor

Post Reply

Return to “Volume 104 (10400-10499)”