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

lifttokens Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

lifttokens.html

Problem Description

Rar the Cat is stuck at floor N of a very very tall building. In order to get down back to floor 0, he needs to purchase "lift tokens". Each lift token can bring him down a certain number of levels. For example, a lift token that is of type 5 will bring him down 5 levels, say, from level 6 to level 1.

There are many types of lift tokens that can bring Rar the Cat down a number of levels, namely 1, 5, 10, 17, 50, 100, 500, 1000, 5000 and 10000 levels. Each lift token costs 1 dollar. Given N, which is the floor that Rar the Cat is stuck on, output the minimum number of dollars Rar the Cat has to spend in getting down.

Input

The first line of input will consist of one integer, N.

Output

The output should contain one line with one integer, the minimum number of dollars needed to bring Rar the Cat down to EXACTLY floor 0.

Limits

Subtask 1 (10%): 1 ≤ N ≤ 10
Subtask 2 (15%): 1 ≤ N ≤ 1000
Subtask 3 (25%): 1 ≤ N ≤ 1000000
Subtask 4 (50%): 1 ≤ N ≤ 1000000000

Sample Input 1

18

Sample Output 1

2

Sample Input 2

20

Sample Output 2

2

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110101s32MBMinimum
215101s32MBMinimum
325101s32MBMinimum
450101s32MBMinimum
5021s32MBMinimum

Judge Compile Command

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