Minh đi mua sắm tại cửa hàng SS. Cửa hàng có các mệnh giá tiền: 1$, 5$, 10$, 50$, 100$, 500$. Minh mua một số mặt hàng trong cửa hàng và trả số tiền là 1000$. Nhiệm vụ của bạn là tìm ra cách trả lại tiền thừa cho Minh bằng số lượng tờ tiền ít nhất.

Input:

Dữ liệu đầu vào là nhiều dòng, trong đó dòng đầu tiên biểu thị số lượng lần mua. N dòng tiếp theo mỗi dòng biểu thị duy nhất một số nguyên N (1 ≤ N ≤ 999) là tổng giá trị của các mặt hàng Minh đã mua.

Output:

Dữ liệu đầu ra là các dòng, mỗi dòng là một số nguyên duy nhất, biểu thị số lượng tờ tiền ít nhất mà cửa hàng phải trả lại.

Giải thích:

Với 380 cửa hàng cần trả lại 620$ bằng cách sử dụng 1 tờ 500$, 1 tờ 100$, và 2 tờ 10$. Nên kết quả là 4

Ví dụ :

Input:

2
380
1

Output:

4
15

Đoàn tàu hỏa chở khách du lịch ở một địa điểm nổi tiếng có n toa, toa thứ i có có ai người, i= 1....n. Khi đến nơi mọi người đều nóng lòng muốn ra. Để tránh ùn tắc và gây lộn xộn trên sân ga cứ mỗi đơn vị thời gian người ta có thể cho tất cả hành khách ở một toa xuống hoặc cho mỗi toa một người xuống.

Hãy xác định thời gian tối thiểu để mọi hành khách xuống được ga.

Đầu vào:

Dòng đầu tiên chứa một số nguyên

Dòng thứ hai chứa n số nguyên

Đầu ra:

Một số nguyên là thời gian tối thiểu tính được.

Ràng buộc:

1 ≤ n ≤ 2.10^5

0 ≤ ai ≤ 10^9

Ví dụ:

Input:

3
1 2 1

Output:

2

Có n quyển sách, và Kotivalo cùng Justiina sẽ đọc hết tất cả chúng. Với mỗi quyển sách, bạn biết thời gian cần để đọc hết nó.

Cả hai sẽ đọc toàn bộ mỗi quyển sách từ đầu đến cuối, nhưng không thể đọc cùng một quyển cùng lúc. Nhiệm vụ của bạn là xác định tổng thời gian tối thiểu cần thiết để cả hai đọc hết tất cả các quyển sách.

Input:

Dòng đầu tiên chứa một số nguyên n — số lượng quyển sách.

Dòng thứ hai chứa n số nguyên t₁, t₂, …, tₙ — thời gian đọc từng quyển sách.

Output:

In ra một số nguyên: tổng thời gian tối thiểu cần thiết để đọc hết tất cả các quyển sách.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~1 \le t_i \le 10^9~

Ví dụ :

Input:

3
2 8 3

Output:

16

Bạn được cho hai số nguyên a và b (a ≤ b). Xét tất cả các giá trị nguyên c thỏa mãn a ≤ c ≤ b, hãy tìm giá trị nhỏ nhất của biểu thức sau:

(c-a)+(b-c)

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 55) - số lượng bộ test.

Mỗi bộ test gồm hai số nguyên a và b (1 ≤ a ≤ b ≤ 10).

Dữ liệu ra:

Với mỗi bộ test, in ra một số nguyên là giá trị nhỏ nhất của biểu thức

Ví dụ :

Input:

3
1 2
3 10
5 5

Output:

1
7
0

Bạn được cho một dãy số gồm n số nguyên a1 , a2, ..., an. Một thao tác được ghi nhận khi bạn thực hiện tăng hoặc giảm giá trị của bất kỳ số ai nào trong dãy lên 1 đơn vị (tức là ai = ai + 1 hoặc ai = ai - 1) và bạn có thể lặp đi lặp lại thao tác này vô số lần.

Thầy giáo muốn bạn hãy thực hiện các thao tác tăng giảm giá trị đó để thu được một dãy số mới sao cho tích của các phần tử trong dãy số mới này bằng 1.

Ví dụ: với n = 3 và dãy số gồm 3 phần tử là [1,-3,0] chúng ta có thể thực hiện tăng 2 lần số -3 (tức a2) đế trở thành - 1 và giảm 1 lần số 0 (tức a3) đế trở thành -1. Lúc này ta sẽ thu được dãy số mới là [1, -1, - 1] và tích các phần tử trong dãy số này bằng 1. Như vậy, bạn sẽ mất tông cộng 3 thao tác đề thực hiện ba lần tăng/giảm giá trị. Có nhiều cách khác nhau để thực hiện việc tăng giảm để dãy mới thu được có tích bằng 1, tuy nhiên sẽ không tồn tại cách nào ít hơn ba thao tác.

Yêu cầu: Cho dãy số a gồm n số nguyên, hãy tìm ra chi phí ít nhất để biến đổi dãy số a đã cho trở thành dãy mới với tích các phần tử trong dãy bằng 1.

Dữ liệu vào:

Dòng đầu là số nguyên dương n.

Dòng thứ 2 gồm n số nguyên a; (-10^9 ≤ ai ≤ 10^9) với mỗi số được cách nhau bởi một dấu cách.

Dữ liệu ra:

Chi phí ít nhất để biến đổi dãy số đã cho để trở thành dãy có tích các phần tử bằng 1.

Ràng buộc:

Có 50% số test của bài có 0 < n ≤ 100

Có 50% số test còn lại của bài có 0 < n ≤ 10^5

Ví dụ:

Input 01:

2
-1 1

Output 01:

2

Input 02:

5
-5 -3 5 3 0

Output 02:

13

Cho N công việc. Mỗi công việc được biểu diễn như một bộ 3 số nguyên dương, trong đó JobID là mã của việc, Deadline là thời gian kết thúc của việc, Profit là lợi nhuận đem lại nếu hoàn thành việc đó đúng thời gian. Thời gian để hoàn toàn mỗi công việc là 1 đơn vị thời gian. Hãy cho biết lợi nhuận lớn nhất có thể thực hiện các việc với giả thiết mỗi việc được thực hiện đơn lẻ.

Đầu vào: Dòng thứ 1 chứa số nguyên dương N; N dòng tiếp theo mô tả id, deadline, profit của N công việc

Ràng buộc: 1<=N<=10^5；1<JobID<N；1<=Deadline<=N；1<=Profit<=1000</p>

Đầu ra:

Input 01:

4
1 4 20
2 1 10
3 1 40
4 1 30

Output 01:

60

Input 02:

9
1 7 50    
2 7 100
3 6 200
4 6 100
5 3 50
6 2 100
7 2 90
8 2 80
9 1 180

Output 02:

780