Write all the numbers from 1 to 1000 in base-two representation. These numbers require ten bits since 2^10 = 1024
. Your boxes are powers of two up to 2^8
, and 489
for the last box (2^0
to 2^8
and 489
gives you ten boxes and 2^0 + 2^1 + ... + 2^8 + 489 = 2^9 - 1 + 489 = 511 + 489 = 1000
), and the bit representations give you proof that you can write any number of to 1000 as a combination of these boxes (clearly anything up to 511 is okay, for anything greater than 511, subtract 489 and then note that you can write the remainder as a combination of the other 8 boxes since it is guaranteed to be less than or equal to 511).
Algorithmic Puzzle [closed]
题
How to distribute 1000$ in ten boxes so that any amount of money between $1 and $1000(both inclusive) can be given as some combinations of these boxes.
Please provide any hints on how to approach this.I tried but couldn't make any solution.
解决方案 2
其他提示
have you ever did binary to decimal conversion ? Take any number between 1 and 1000 and try converting it into binary. You'll figure out that you are dealing in powers of 2.
Distribute in powers of 2 and then for whatever amount you need, just convert it into binary and pick those boxes for which bit is set to 1.
不隶属于 StackOverflow