PAYING - Paying in Byteland
There are infinitely many coin denominations in the Byteland. They have values of 2i for i=0, 1, 2 ... . We will say that set of coins c1, c2 ... ck is perfect when it is possible to pay every amount of money between 0 and c1 + ... + ck using some of them (so {4, 2, 2, 1} is perfect while {8, 1} is not). The question is - is it always possible to change given sum n into a perfect set of coins? Of course it is possible ;). Your task will be more complicated: for a sum n you should find minimal number of coins in its perfect representation.
Input
First line of input contains one integer c ≤ 50 - number of test cases. Then c lines follow, each of them consisting of exactly one integer n ≤ 101000.
Output
For each test case output minimal number of coins.
Example
Input: 5 507 29 8574 233 149 Output: 14 7 21 11 10
hide comments
nadstratosfer:
2019-07-25 22:01:45
This was fun to crack =) |
|
lotus_guy:
2016-01-19 19:59:54
loved it :D
|
|
apopa:
2015-07-01 02:55:16
@Adit Goel
|
|
Adit Goel:
2015-02-23 18:51:50
why is the answer for 507->14
|
|
Daniel Ospina Acero:
2014-11-20 00:17:20
Any problem that anyone might be facing, if the test cases are working fine, has to do with large numbers. |
|
nikhil:
2014-02-06 13:26:39
Last edit: 2014-02-06 16:54:13 |
|
Nitesh Lulla:
2013-05-31 16:06:22
is limit of n actually 10^1000. will we have to store the number in strings? |
|
Aamir Khan:
2011-11-12 13:15:24
To get the all values <=29 : I can take the coins of 1,2,4,8,16 and make all possible sum. Why the answer is 7 for this test case ?
|
|
Arun prasath:
2011-07-22 05:24:34
i want answer for this , wher can i find the code??? |
|
Radhika:
2011-05-14 12:05:55
can someone provide me more test cases..? |
Added by: | gawry |
Date: | 2004-07-07 |
Time limit: | 5.923s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |