oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

moneychanger Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

moneychanger.html


Josephine the money changer was working at her kiosk one day when she realized how irritating
it was when she had to give about 20 coins to her customer. Suddenly, she had an idea.
If she could write a program to instantly tell her how many coins she needs to make the
value, then she could just refuse to serve her customers if they choose a value that
requires her to select too many coins.

Unfortunately, Josephine, being a lazy person, doesn’t want to learn programming all
by herself. Your task is to write the program for her.

Given n (1 ≤ n ≤ 100) coins where and each coin has a value
n(i) (1 ≤ n(i) &le 10,000), and a value v (1 ≤ v &le 10,000) which is also an
integer, calculate the minimum number of coins needed to make v with the n coins provided.

POINTS: 100

PROBLEM NAME: moneychanger

INPUT FORMAT:

Line 1:     The first line contains two integers, n and v, separated by a space;
Line 2...n: Each line contains one integer each, with the (i + 1)th line
			representing the value of coin n(i). 

INPUT DETAILS:

Every coin has a unique value. The values of the coins might not necessarily be
less than the value v.

SAMPLE INPUT:

6 99
1
2
5
10
25
50

OUTPUT FORMAT:

Line 1: A single integer which is the minimum number of coins needed to make the value v.
If it is impossible to make the value with the set of coins given, output -1.

SAMPLE OUTPUT:

6

OUTPUT DETAILS:

6 coins are needed to make 99: 50, 25, 10, 10, 2, 2

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o moneychanger -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.