WOSS Dual Olympiad 2021 J3: Frisbee Golf

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

You are playing Frisbee Golf on your Nintendo Wii. Having gotten bored of simply playing the game, you decide to optimise your playing strategy.

You have 7 different disks, with each one assigned a special number. This number indicates its throwing distance. Because you are an expert at the game, you always throw it at that exact distance. You have also managed to find a way in every course to always throw in a direct line to the finish point.

Your 7 disks are numbered like so: \{1, 5, 10, 50, 100, 500, 1000\}.

For every course, you know the exact value of the distance from the start to the end point. Using your programming skills, your job is to find the optimal configuration of disk throws such that you reach the goal in the lowest possible amount of throws.

Constraints

1 \le D \le 10^{15}

Subtask 1 [30%]

1 \le D \le 10^5

Subtask 2 [70%]

No additional constraints.

Input Specification

The input consists of a single line, containing a single integer D, where D is the distance from the starting point to the end point for the frisbee golf course. Note that this may not fit in a 32-bit integer, so use the long data type for Java and the long long data type for C++.

Output Specification

Output will consist of 7 space separated integers. The i^\text{th} integer will represent the number of times you must throw the i^\text{th} disk in the optimal configuration. So, the first number will indicate the number of times you must throw the "1" disk, the second number will correspond to the "5" disk, the third one will correspond to the "10" disk, and so on and so forth. See the sample input case for additional clarification. Note that these may also not fit in a 32-bit integer, so use the long data type for Java and the long long data type for C++.

Sample Input 1

77

Sample Output 1

2 1 2 1 0 0 0

Sample Input 2

896

Sample Output 2

1 1 4 1 3 1 0

Sample Input 3

53467

Sample Output 3

2 1 1 1 4 0 53

Comments

There are no comments at the moment.