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

weddingcoins Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

weddingcoins.html

Problem Description

After years and years of preparation, Rar the Cat is finally getting married! Yay!

He excitedly headed towards the wedding agency, and booked the date of his wedding. He was told that the wedding would cost N cents. He opened his wallet, only to find a whole mess of coins and notes flooding out. Oh no! He would not want to give that whole floor worth of coins to the wedding agency! Looking at the floor, which was full of 1c, 5c, 10c, 50c, $1, $5, $10, $50, $100, $500, $1000, $5000 and $10000 coins and notes, he did not know which ones to give to the wedding agency. Help Rar by calculating the minimum number of coins and notes needed to pay his wedding fee of N cents by using the coins and notes he had.

Input

The input will consist of one integer, N.

Output

Your output should consist of one integer, the minimum number of coins and notes needed to form exactly N cents.

Limits

Subtask 1 (25%): 1 <= N <= 1,000,000
Subtask 2 (75%): 1 <= N <= 1,000,000,000,000,000

Sample Input 1

76

Sample Output 1

5

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
12551s64MBMinimum
27551s64MBMinimum
3011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o weddingcoins -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.