You are not logged in. Please login at www.codechef.com to post your questions!

×

Range of int: Bytelandian Gold Coins Problem

I don't know what's the issue here: My program is working fine when I use unsigned long int but it gives WA in case of long int or int.

As far as I know range of int on 32 bit machine is 10^9... so my program should work fine using int(since range of n is <= 10^9) but it does not.

my code is

include<stdio.h>

int amt[100000] = {0}; unsigned long int max(unsigned long int n) { int val = 0; if(n <12) return n; else if (n<100000) { if(amt[n]!=0) return amt[n]; else { val = max(n/2)+max(n/3)+max(n/4); amt[n] = val; return val; } } else { val = max(n/2)+max(n/3)+max(n/4); return (n>val?n:val); } } int main() { unsigned long int n; while(scanf("%lu",&n) != EOF) { printf("%lu\n", max(n)); } return 0; }

Kindly Help.

asked 25 Sep '13, 00:55

cool_techie's gravatar image

2★cool_techie
28971218
accept rate: 22%


The answer to the input 109 is 4243218150.

This number needs 32 bits to represent the magnitude alone. So, in sign-magnitude form, it needs at least 33 bits.

The int datatype is signed 32-bit representation. It uses only 31 bits to represent magnitude. Your program would have passed, if you used unsigned int.

Now, it may amuse you that long and int are usually 32-bit long here. To get 64-bit numbers, you need to use long long (for signed) and unsigned long long (for unsigned).

the reasoon why your program got accepted is not because you used long. But, it is because you used unsigned.

link

answered 25 Sep '13, 08:04

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

The inputs are all well within range. But there is no guarantee in the question, that the output will also fit in signed integer.

(25 Sep '13, 08:05) tijoforyou2★

Thanks tijoforyou. I just want to ask one more question, as you pointed out that long and int are only 32-bit long. So what is the need of long?

(25 Sep '13, 08:44) cool_techie2★

You might be aware that there is a type short as well.

So, we have short (same as short int), int, long (same as long int) and long long. The only guarantee (and restriction to compiler writers) is that sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long).

So, in some machines, long might have larger size than int. (E.g.: Turbo C has 16-bit "int" and 32-bit "long" datatypes.)

So, the data types do exist. In the gcc versions used here, sizeof(int) is same as sizeof(long).

(25 Sep '13, 09:49) tijoforyou2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×54
×25
×3

question asked: 25 Sep '13, 00:55

question was seen: 1,358 times

last updated: 25 Sep '13, 09:53