Một hệ thống tiền tệ có các mệnh giá: 1, 2, 5, 10, 20, 50, 100, 200, 500. Cho số tiền \(N\).

Yêu cầu:

Hãy tìm số tờ tiền ít nhất để có tổng bằng \(N\).

Input:

Một số nguyên duy nhất \(N\) (\(1 \le N \le 10^9\)).

Output:

Một số nguyên là số tờ tiền ít nhất.

125

3 (gồm 1 tờ 100, 1 tờ 20, 1 tờ 5).

Cho một dãy số có \(N\) số tự nhiên \((N < 1000)\)

Yêu cầu

Sắp xếp dãy số thành dãy tăng dần theo chữ số cuối cùng của mỗi số, in ra dãy sau khi sắp xếp

Dữ liệu vào

Dòng \(1\): Ghi số \(N ( N ≤ 1000)\)
Dòng \(2\): Ghi \(N\) số nguyên không âm, mỗi số cách nhau một kí tự trắng, giá trị mỗi số không vượt quá \(10^{12}\)

Dữ liệu ra

Dòng \(1\): Ghi các số sau khi sắp xếp, nếu các số có chữ số cuối bằng nhau, thì ưu tiên sắp xếp số nhỏ hơn đứng trước

6
12 32 22 4 3 24

12 22 32 3 4 24

Một số tự nhiên lớn hơn \(0\) được gọi là số may mắn nếu tổng các chữ số của nó bằng \(9\).
Cho số nguyên dương \(N\)

Yêu cầu

Hãy in ra tổng các chữ số của nó và cho biết nó có phải là số may mắn không?

Dữ liệu vào

Dòng \(1\): Ghi số \(N ( N ≤ 10^{18})\);

Dữ liệu ra

Dòng \(1\): Ghi tổng các chữ số của \(N\)
Dòng \(2\): Ghi YES nếu là số may mắn, ghi NO nếu không phải số may mắn

10

1
NO

27

9
YES

“Thí sinh có số điểm bằng hoặc cao hơn điểm của người xếp hạng thứ \(k\) sẽ được vào vòng tiếp theo, miễn là thí sinh đó đạt được điểm số dương…” — trích từ luật cuộc thi.

Tổng cộng có \(n\) thí sinh tham gia cuộc thi \((n ≥ k)\), và bạn đã biết điểm số của họ. Hãy tính xem có bao nhiêu thí sinh sẽ được vào vòng tiếp theo.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k (1 ≤ k ≤ n ≤ 50)\), cách nhau bởi một dấu cách.

Dòng thứ hai chứa \(n\) số nguyên \(a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 100)\), trong đó \(aᵢ\) là số điểm của thí sinh xếp hạng thứ \(i\). Dãy số được cho theo thứ tự không tăng (tức là với mọi \(i\) từ \(1\) đến \(n − 1\), ta có \(aᵢ ≥ aᵢ₊₁\)).

Dữ liệu ra

In ra số lượng thí sinh được vào vòng tiếp theo.

Sample Input 1

8 5
10 9 8 7 7 7 5 5

Sample Output 1

6

Sample Input 2

4 2
0 0 0 0

Sample Output 2

0