Connection Status:
Competition Arena > NewMoneySystem

NewMoneySystem

SRM 325 · 2006-11-02 · by Andrew_Lazarev

SRM 325 · 2006-11-02 · by Andrew_Lazarev · Dynamic Programming
Class Name: NewMoneySystem
Return Type: long
Method Name: chooseBanknotes
Arg Types: (string, int)
Problem Statement

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).

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

Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NewMoneySystem with a public method long long chooseBanknotes(string N, int K) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous