Exact Change

면접 대비

시간 제한1초메모리 제한2048 MB

요약

1000 이하의 가격이 주어질 때 1, 5, 15, 30, 150달러 지폐로 정확히 그 금액을 지불하면서 지폐 수를 최소로 하는 조합을 구한다.

난이도: 쉬움10점 중 3점
유형: 그리디, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Jayden is a student at Mines, and this semester he wants to study abroad in a foreign country called Umbertoland. In addition to their language and culture, Umbertoland also has a unique currency system. The bill denominations are as follows:

$1$ dollar
$5$ dollars
$15$ dollars
$30$ dollars
$150$ dollars

Given the price of an item, help Jayden figure out how many of each bill to use in order to pay the exact amount using the fewest bills possible.

입력

The input will consist of one integer $0 \leq N \leq 1\\,000$ which is the price of the item in dollars.

출력

Print five space-seperated integers, the number of \ $1$, \\$ 5 $, \\$$15$ , \ $30$, and \\$ 150$ bills needed to pay with the fewest total bills, respectively.

예제3

예제 1
입력
```
16
```
예상 출력
```
1 0 1 0 0
```
예제 2
입력
```
44
```
예상 출력
```
4 2 0 1 0
```
예제 3
입력
```
45
```
예상 출력
```
0 0 1 1 0
```