TopCoder problem "NewMoneySystem" used in SRM 325 (Division I Level Three)



Problem Statement

    

You are creating the money system for a new game. The requirements are as follows:

  1. There will be exactly K different banknote values.
  2. The value of the smallest banknote will be equal to one dollar.
  3. The value of the i-th banknote will be equal to the value of the (i-1)-th banknote multiplied by 2, 3, 4 or 5.

The initial capital of a player will be N dollars, so you want to choose banknote values in such a way that minimizes the number of banknotes required to make N dollars. Assume that you have an infinite supply of banknotes for each value.

You will be given two integers N and K. Due to technical reasons, N will be given as a String with no leading zeros. Return the minimal number of banknotes required to make exactly N dollars. Note that you must minimize the number of actual banknotes, not the number of banknote values (see examples).

 

Definition

    
Class:NewMoneySystem
Method:chooseBanknotes
Parameters:String, int
Returns:long
Method signature:long chooseBanknotes(String N, int K)
(be sure your method is public)
    
 

Constraints

-N will be an integer between 1 and 1018, inclusive, with no leading zeros.
-K will be between 1 and 100, inclusive.
 

Examples

0)
    
"1025"
6
Returns: 2
The best set of banknote values is {1, 4, 16, 64, 256, 1024}.

1025 = 1024 + 1.
1)
    
"1005"
5
Returns: 3
The best set of banknote values is {1, 5, 25, 100, 500}.

1005 = 2 * 500 + 5.
2)
    
"12000"
14
Returns: 1
3)
    
"924323565426323626"
1
Returns: 924323565426323626
The answer can be rather big.
4)
    
"924323565426323626"
50
Returns: 10

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6828

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10005&pm=6828

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming