Computer Science

Dynamic Programming

Dynamic Programming: Level 4 Challenges


Candice enjoys candy like any other girl her age. One day, she asks her mother to lend her money to buy candy.

Her mother agrees and lends her $40\$40 but specifies a few rules first.

  • Candice needs to use all $40 \$40 and should not have any remaining money.
  • Her mother doesn't want her to get carried away so Candice can buy a minimum of 1 and a maximum of 10 candies in total.
  • Candice can buy as many of each type of candy she wants provided the above conditions are satisfied.

She agrees and heads over to the candy shop.Over there she notices that the shop offers candies of 4 different types, which are priced at $1,$2,$5 and $10 \$1 , \$2, \$5 \text{ and } \$10 respectively.

If Candice picks each candy one at a time, In how many ways can Candice make her selection?

Details and Assumptions

  • As an explicit example, Candice can buy 4 candies of $10\$10 each so that she would be left with no money extra.
  • Order of purchase matters. If Candice buys the candies as (5,5,10,10,10) (5,5,10,10,10) and (5,10,10,10,5) (5,10,10,10,5) both should be considered.
Image Courtsey : animekida
Check out Candice's Other Adventures!

Several vaults were broken into last night! Police have strong evidence to believe that the culprit was the infamous Algorithmic Burglar - an efficient and swift robber.

7 different vaults were robbed. Police discovered that the vaults are missing the following amounts of metal: 1739 lbs, 72 lbs, 212 lbs, 55 lbs, 511 lbs, 1239 lbs, and 99 lbs.

Here are the weights and dollar values for the different bars in the vaults:

Material    Weight  Value
Gold        2 lbs   $57
Platinum    5 lbs   $191
Silver      14 lbs  $417
Expensivium 17 lbs  $231
Rhodium     19 lbs  $741
Osmium      13 lbs  $139
Aluminum    1 lbs   $28
Silicon     3 lbs   $117
Iron        5 lbs   $13
Titanium    11 lbs  $9
Potassium   19 lbs  $18

Before the robbery, each vault contained at least 2000 lbs of each metal. Assume the burglar stole whole bars, not fractions of a bar.

Let V be the greatest possible value in dollars of the stolen material. What are the last three digits of V?

Jenny is the operator of a large garbage disposal machine. It is a fairly simple machine and constitutes of only three buttons: One green \color{#20A900} {\text{green}} button, one blue \color{#3D99F6} {\text{blue}} button and one red \color{#D61F06} {\text{red}} button.

Given that initially nn items are put in the machine, it will only destroy garbage in the three following ways:

  • The green \color{#20A900} {\text{green}} button, if pressed destroys 12\frac{1}{2} of the items,leaving n2\frac{n}{2} of the items, but it only works if the number of items nn is divisible by 2.2.
  • The blue \color{#3D99F6} {\text{blue}} button,if pressed destroys 23\frac{2}{3} of the items,leaving n3\frac{n}{3} items, but it only works if the number of items nn is divisible by 3.3.
  • The red \color{#D61F06} {\text{red}} button always works and destroys only 11 item leaving n1n-1 if pressed.

Since Jenny is a lazy operator she wants to minimize the number of times she presses the buttons? What is the minimum number of times Jenny has to press the buttons in order to completely destroy 466559466559 items?

As explicit examples for n=10n=10 items Jenny would have to do 44 button presses (red \color{#D61F06} {\text{red}} ,blue \color{#3D99F6} {\text{blue}} , blue \color{#3D99F6} {\text{blue}} ,red \color{#D61F06} {\text{red}} ) to minimize the number of presses as shown below.
101=910-1=9 \longrightarrow 93=39\diagup 3=3 \longrightarrow 33=13\diagup3=1 \longrightarrow 11=01-1=0

For n=6n=6 items the optimal solution is 33 presses (blue \color{#3D99F6} {\text{blue}} , green \color{#20A900} {\text{green}} ,red \color{#D61F06} {\text{red}} ) or (blue \color{#3D99F6} {\text{blue}} ,red \color{#D61F06} {\text{red}} ,red \color{#D61F06} {\text{red}} )
632211=06\diagup 3 \longrightarrow 2 \diagup 2 \longrightarrow 1 - 1=0 or 632111=06\diagup 3 \longrightarrow 2 - 1 \longrightarrow 1 - 1=0


Problem Loading...

Note Loading...

Set Loading...